Research PaperNo Access

Continuous-time quantum hash function based on one-dimensional cycle lattice

Wei-Min shi

https://orcid.org/0000-0001-5431-5276

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

E-mail Address: shiweimin@bjut.edu.cn

Corresponding author.

Search for more papers by this author

Shou Wang

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

Search for more papers by this author

Tian Pan

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

Search for more papers by this author

Yu-Guang Yang

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

Search for more papers by this author

, and

Yi-Hua Zhou

College of Computer Science and Technology, Beijing University of Technology, Beijing 100124, China

Beijing Key Laboratory of Trusted Computing, Beijing 100124, China

Search for more papers by this author

https://doi.org/10.1142/S0217984921502419Cited by:4 (Source: Crossref)

Abstract

The proposed quantum hash function (QHF) based on the discrete-time quantum walk (DTQW) structure requires enlarging the coin state space and the preparation of continuous quantum states is less difficult. Hence, a new construction method of QHF is proposed based on the continuous-time quantum walk (CTQW) of the one-dimensional (1D) lattice with boundary constraints and without additional coin space. In the scheme, the input of the QHF is an arbitrary binary string message which is used to control the selected Hamiltonian of CTQW at each time interval, and the output of the QHF is the final probability distribution of CTQW. Under the same computing environment, simulation and analysis indicate that our QHF can satisfy the same security requirements such as sensitivity, diffusion and confusion, collision, birthday attack, but the collision rate is reduced by 40% without reducing effectiveness.

Keywords:

References

1. R. Merkle , One way hash functions and DES, in Advances in Cryptology-Crypto’89, Lecture Notes in Computer Science, Vol. 435 (1990), pp. 428–446. Crossref, Google Scholar
2. I. Damg , A design principle for hash functions, in Advances in Cryptology-Crypto’89, Lecture Notes in Computer Science, Vol. 435 (1989), pp. 416-427. Google Scholar
3. R. L. Rivest , The MD4 message digest algorithm, in Advances in Cryptology-Crypto’90, (Springer-Verlag, Berlin, 1990). Crossref, Google Scholar
4. R. L. Rivest, The MD5 message digest algorithm. Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force, 1992. Google Scholar
5. Federal Information Processing Standards Publication 180, SECURE HASH STANDARD, 1993. Google Scholar
6. Federal Information Processing Standards Publication 180-1, SECURE HASH STANDARD, 1995. Google Scholar
7. Federal Information Processing Standards Publication 180-2, SECURE HASH STANDARD, 2004. Google Scholar
8. Y. Zheng, J. Pieprzyk and J. Seberry , Haval-A one-way hashing algorithm with variable length of output, in Advances in Cryptology, Aus-crypto’92, (Springer-Verlag, New York, 1992), pp. 83-104. Google Scholar
9. H. Dobbertin , J. Cryptol. 10 (1997) 51. Crossref, Web of Science, Google Scholar
10. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition, NIST, 2012. Google Scholar
11. X. Wang, D. Feng, X. Lai and H. Yu, Collisions for hash functions MD4, MD5, HAVAL-128and RIPEMD, in Rump Session of Crypto’04, E-print 2004, p. 199. Google Scholar
12. X. Wang, X. Lai, D. Feng, et al., Cryptanalysis of the hash functions MD4 and RIPEMD, in Proc. Eurocrypt’05, Aarhus, Denmark, 2005, pp. 1–18. Crossref, Google Scholar
13. X. Wang and H. Yu , How to break MD5 and other hash functions, in Proc. Eurocrypt’05, Aarhus, Denmark, 2005, pp. 19–35. Crossref, Google Scholar
14. M. Stevens, E. Bursztein, P. Karpman, A. Albertini and Y. Markov , The first collision for full SHA-1, in Advances in Cryptology–CRYPTO 2017, Lecture Notes in Computer Science, Vol. 10401, eds. J. Katz and H. Shacham (Springer, Cham, 2018). Google Scholar
15. I. Mironov , Hash functions: From Merkle-Damg to Shoup, in Proc. 20th Annual Int. Conf. Theory and Applications of ryptographic Techniques, ed. B. Pfitzmann , Innsbruck, Austria, 2001, pp. 166–181. Crossref, Google Scholar
16. M. Liskov , Constructing an ideal hash function from weak ideal compression functions, in Proc. 13th Int. Workshop on Selected Areas in Cryptography, eds. E. Biham and A. M. Youssef , Montreal, Canada, 2006, pp. 358–375. Google Scholar
17. S. Lucks , A failure-friendly design principle for hash functions, in Asiacrypt 2005, Lecture Notes in Computer Science, Vol. 3788 (2005), pp. 474-494. Crossref, Google Scholar
18. E. Biham and O. Dunkelman, A framework for iterative hash functions—HAIFA, Cryptology ePrint Archive: Report 2007/278 (2007). Google Scholar
19. G. Bertoni, J. Daemen, M. Peeters and G. V. Assche , Sponge functions, ECRYPT Hash Workshop, 2007. Google Scholar
20. Y.-J. Yang, F. Chen, X.-M. Zhang, J.-P. Yu and P. Zhang , Wireless Pers. Commun. 94(4) (2017) 2969. Crossref, Web of Science, Google Scholar
21. D. Gottesman and I. Chuang, Quantum digital signatures, Technical Report Cornell University Library, arXiv:quant-ph/0105032. Google Scholar
22. A. S. Holevo , Probl. Pered. Inf. 9(3) (1973) 3. Google Scholar
23. E. Kashefi and I. Kerenidis , Theor. Comput. Sci. 378(1) (2007) 101. Crossref, Web of Science, Google Scholar
24. H. Buhrman, R. Cleve, J. Watrous and R. de Wolf , Phys. InImage 2018-11-07 10:03:01-9-Rev. Lett. 87(16) (2001) 167902. Google Scholar
25. D. Gavinsky and T. Ito , Quantum Inf. Comput. 13(7–8) (2013) 583. Web of Science, Google Scholar
26. R. T. Horn, S. A. Babichev, K. P. Marzlin, A. I. Lvovsky and B. C. Sanders , Phys. Rev. Lett. 95(15) (2005) 150502. Crossref, Web of Science, ADS, Google Scholar
27. J. M. Arrazola and N. Lüthenhaus , Phys. Rev. A 89(6) (2014) 062305. Crossref, Web of Science, ADS, Google Scholar
28. N. Kumar, E. Diamanti and I. Kerenidis , Phys. Rev. A 95(3) (2017) 032337. Crossref, Web of Science, ADS, Google Scholar
29. M. Jachura, M. Lipka, M. Jarzyna and K. Banaszek , Opt. Exp. 25(22) (2017) 27475. Crossref, Web of Science, Google Scholar
30. J. F. Du, P. Zou, X. H. Peng, D. K. L. Oi, L. C. Kwek, C. H. Oh and A. Ekert , Phys. Rev. A 74(4) (2006) 042319. Crossref, Web of Science, ADS, Google Scholar
31. F. Xu, J. M. Arrazola, K. Wei, W. Wang, P. Palacios-Avila, C. Feng, S. Sajeed, N. Lüthenhaus and H.-K. Lo , Nat. Commun. 6 (2015) 8735. Crossref, Web of Science, ADS, Google Scholar
32. J. Y. Guan, F. H. Xu, H. L. Yin, Y. Li, W. J. Zhang, S. J. Chen, X. Y. Yang, L. Li, L. X. You, T. Y. Chen, Z. Wang, Q. Zhang and J. W. Pan , Phys. Rev. Lett. 116(24) (2016) 240502. Crossref, Web of Science, ADS, Google Scholar
33. F. Ablayev and A. Vasiliev , Laser Phys. Lett. 11(2) (2014) 025202. Crossref, Web of Science, Google Scholar
34. F. Ablayev and M. Ablayev , Laser Phys. Lett. 12(12) (2015) 125204. Crossref, Web of Science, ADS, Google Scholar
35. F. Ablayev and M. Ablayev, Quantum hashing via classical $𝜀$ -universal hashing constructions, Technical Report, Cornell University Library, arXiv:quant-ph/1404.1503v2. Google Scholar
36. F. Ablayev, M. Ablayev and A. Vasiliev , J. Phys. Conf. Ser. 681 (2016) 012019. Crossref, Google Scholar
37. M. Ziatdinov, Quantum hashing. Group approach, arXiv:quant-ph/1412.5135. Google Scholar
38. M. Ziatdinov, From graphs to keyed quantum hash functions, arXiv:quant-ph/1606.00256v1. Google Scholar
39. A. Vasiliev, Quantum hashing for finite abelian groups, arXiv:quant-ph/1603.02209. Google Scholar
40. D. Li, J. Zhang, F.-Z. Guo, W. Huang, Q.-Y. Wen and H. Chen , Quantum Inf. Process. 12(3) (2013) 1501. Crossref, Web of Science, ADS, Google Scholar
41. D. Li, J. Zhang, X. W. Ma, W. W. Zhang and Q. Y. Wen , Quantum Inf. Process. 12(6) (2013) 2167. Crossref, Web of Science, ADS, Google Scholar
42. Y.-G. Yang, P. Xu, R. Yang, Y. H. Zhou and W. M. Shi , Sci. Rep. 6 (2016) 19788. Crossref, Web of Science, ADS, Google Scholar
43. D. Li, Y.-G. Yang, J.-L. Bi, J.-B. Yuan and J. Xu , Sci. Rep. 8 (2018) 225. Crossref, Web of Science, ADS, Google Scholar
44. Y.-G. Yang, Y.-C. Zhang, G. Xu, X.-B. Chen, Y.-H. Zhou and W.-M. Shi , Sci. China-Phys. Mech. Astron. 61(3) (2018) 030312. Crossref, Web of Science, Google Scholar
45. Y.-G. Yang, J.-L. Bi, X.-B. Chen, Z. Yuan, Y.-H. Zhou and W.-M. Shi , Quantum Inf. Process. 17(8) (2018) UNSP 189. Crossref, Web of Science, Google Scholar
46. W. F. Cao, Y.-C. Zhang, Y.-G. Yang, Dan Li, Y.-H. Zhou and W.-M. Shi , Quantum Inf. Process. 17(7) (2018) UNSP 156. Crossref, Web of Science, ADS, Google Scholar
47. Y.-G. Yang, J.-L. Bi, D. Li, Y.-H. Zhou and W.-M. Shi , Int. J. Theor. Phys. 58 (2019) 1861. Crossref, Web of Science, Google Scholar
48. E. Farhi, J. Goldstone and S. Gutmann , Theory Comput. 4 (2008) 169. Crossref, Google Scholar
49. E. Farhi and S. Gutmann , Phys. Rev. A 58 (1998) 915. Crossref, Web of Science, ADS, Google Scholar
50. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman , Exponential algorithmic speedup by a quantum walk, in Proc. 35th Annual ACM Symp. Theory of Computing, STOC ’03 (ACM, New York, NY, USA, 2003) pp. 59–68. Crossref, Google Scholar
51. A. M. Childs , Phys. Rev. Lett. 102 (2009), 180501. Crossref, Web of Science, ADS, Google Scholar
52. G. H. Weiss , Aspects and Applications of the Random Walk (North-Holland, 1994). Google Scholar