Analysis of the amplitude form of the quantum hash function
https://doi.org/10.26907/2541-7746.2023.1.5-15
Abstract
In this article, the properties of quantum hash functions are further explored. Previous findings show that so-called small-bias sets (special subsets of the set of elements of a cyclic group) generate a “phase” quantum hash function. Here, it was proved that they also generate an “amplitude” quantum hash function. Namely, it turned out that constructing small-bias sets while generating amplitude quantum functions yields a well-balanced combination of the cryptographic properties of unidirectionality and collision resistance. As a corollary of the obtained theorem, a general statement about the generation of new amplitude quantum hash functions based on universal hash families and small-bias sets was proved.
Supporting agencies: This study was performed as part of the state assignment no. AAAAA19-119011790156-3 of the Ministry of Science and Higher Education of the Russian Federation.
About the Authors
M. F. Ablayev
Federal Research Center “Kazan Scientific Center of the Russian Academy of Sciences”; Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420111
Kazan, 420008
F. M. Ablayev
Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420008
A. V. Vasiliev
Federal Research Center “Kazan Scientific Center of the Russian Academy of Sciences”; Kazan Federal University
Russian Federation
Russian Federation
Kazan, 420111
Kazan, 420008
References
1. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM J. Comput. 1997. V. 26, No 5. P. 1484–1509. doi: 10.1137/S0097539795293172.
2. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. Cambridge Univ. Press, 2010. 702 p. doi: 10.1017/CBO9780511976667.
3. Bernstein D.J. Introduction to post-quantum cryptography // Post-Quantum Cryptography / Bernstein D.J., Buchmann J., Dahmen E. (Eds.). Berlin, Heidelberg: Springer, 2009. P. 1–14. doi: 10.1007/978-3-540-88702-7_1.
4. Ablayev F.M., Vasiliev A.V. Cryptographic quantum hashing // Laser Phys. Lett. 2014. V. 11, No 2. Art. 025202. doi: 10.1088/1612-2011/11/2/025202.
5. Ablayev F., Vasiliev A. Computing Boolean functions via quantum hashing // Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday / Calude C., Freivalds R., Kazuo I. (Eds.). Ser.: Lecture Notes in Computer Science. V. 8808. Cham: Springer, 2014. P. 149–160. doi: 10.1007/978-3-319-13350-8_11.
6. Ablayev F., Ablayev M. Quantum hashing via ǫ -universal hashing constructions and Freivalds’ fingerprinting schemas // Descriptional Complexity of Formal Systems / J¨urgensen H., Karhum¨aki J., Okhotin A. (Eds.). Ser.: Lecture Notes in Computer Science. V. 8614. Cham: Springer, 2014. P. 42–52. doi: 10.1007/978-3-319-09704-6_5.
7. Ablayev F., Ablayev M., Vasiliev A. On the balanced quantum hashing // J. Phys.: Conf. Ser. 2016. V. 681. Art. 012019. doi: 10.1088/1742-6596/681/1/012019.
8. Vasiliev A. Quantum hashing for finite abelian groups // Lobachevskii J. Math. 2016. V. 37, No 6. P. 753–757. doi: 10.1134/S1995080216060184.
9. Ablayev F.M., Ablayev M.F., Vasiliev A.V., Ziatdinov M.T. Quantum fingerprinting and quantum hashing. Computational and cryptographical aspects // Balt. J. Mod. Comput. 2016. V. 4, No 4. P. 860–875. doi: 10.22364/bjmc.2016.4.4.17.
10. Li D., Zhang J., Guo F.-Z., Huang W., Wen Q.-Y., Chen H. Discrete-time interacting
11. quantum walks and quantum Hash schemes // Quantum Inf. Process. 2013. V. 12. P. 1501–1513. doi: 10.1007/s11128-012-0421-8.
12. Yang Y.-G., Xu P., Yang R., Zhou Y.-H., Shi W.-M. Quantum Hash function and its application to privacy amplification in quantum key distribution, pseudo-random number generation and image encryption // Sci. Rep. 2016. V. 6. Art. 19788. doi: 10.1038/srep19788.
13. Yang Y.-G., Bi J.-L., Chen X.-B., Yuan Z., Zhou Y.-H., Shi W.-M. Simple hash function using discrete-time quantum walks // Quantum Inf. Process. 2018. V. 17. Art. 189. doi: 10.1007/s11128-018-1954-2.
14. Ablayev F., Vasiliev A. Algorithms for quantum branching programs based on fingerprinting // Electron. Proc. Theor. Comput. Sci. 2009. V. 9. P. 1–11. doi: 10.4204/EPTCS.9.1.
15. Buhrman H., Cleve R., Watrous J., de Wolf R. Quantum fingerprinting // Phys. Rev. Lett. 2001. V. 87, No 16. Art. 167902. doi: 10.1103/PhysRevLett.87.167902.
16. Naor J., Naor M. Small-bias probability spaces: Efficient constructions and applications // STOC’90: Proc. 22nd Annu. ACM Symp. on Theory of Computing / Ortiz H. (Ed.). New York, NY: Assoc. Comput. Mach., 1990. P. 213–223. doi: 10.1145/100216.100244.
17. Ben-Aroya A., Ta-Shma A. Constructing small-bias sets from algebraic-geometric codes // FOCS’09: Proc. IEEE 50th Annu. Symp. on Foundations of Computer Science. Atlanta, GA, 2009. P. 191–197. doi: 10.1109/FOCS.2009.44.
18. Chen S., Moore C., Russell A. Small-bias sets for nonabelian groups // Approximation,
19. Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th
20. International Workshop, APPROX 2013, and 17th International Workshop, RANDOM
21. , Berkeley, CA, USA, August 21–23, 2013, Proceedings / Raghavendra P.,
22. Raskhodnikova S., Jansen K., Rolim J.D.P. (Eds.). Ser.: Lecture Notes in Computer
23. Science. V. 8096. Berlin, Heidelberg: Springer, 2013. P. 436–451. doi: 10.1007/978-3-642-40328-6_31.
24. Ablayev F.M., Ablayev M.F., Vasiliev A.V. Universal quantum hashing. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2014, vol. 156, no. 3, pp. 7–18. (In Russian)
Review
For citations:
Ablayev M.F., Ablayev F.M., Vasiliev A.V. Analysis of the amplitude form of the quantum hash function. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2023;165(1):5-15. (In Russ.) https://doi.org/10.26907/2541-7746.2023.1.5-15
Views:
282
Email this article 