Анализ амплитудной формы квантовой хеш-функции
https://doi.org/10.26907/2541-7746.2023.1.5-15
Аннотация
Работа продолжает исследования свойств квантовых хеш-функций. Ранее установлено, что так называемые множества с малым отклонением (специальные подмножества множества элементов циклической группы) генерируют квантовую хеш-функцию в “фазовой форме”. В статье доказано, что такие множества генерируют квантовую хеш-функцию также и в “амплитудной форме”: а именно: оказалось, что конструкция множеств с малым отклонением при генерации квантовых функций в амплитудной форме также обеспечивает сбалансированное сочетание криптографических свойств однонаправленности и устойчивости к коллизиям.
В качестве следствия из полученной теоремы доказано общее утверждение о генерации новых квантовых хеш-функций в амплитудной форме на основе универсальных хеш-семейств и множеств с малым отклонением.
При поддержке: Работа выполнена в рамках государственного задания Министерства науки и высшего образования Российской Федерации (тема № ААААА19-119011790156-3).
Об авторах
М. Ф. Аблаев
Федеральный исследовательский центр «Казанский научный центр Российской академии наук»; Казанский (Приволжский) федеральный университет
Россия
Россия
Аблаев Марат Фаридович, научный сотрудник Лаборатории квантовой оптики и информационных технологий; научный сотрудник Лаборатории «Квантовые методы обработки информации»
ул. Лобачевского, д. 2/31, г. Казань, 420111
ул. Кремлевская, д. 18, г. Казань, 420008
Ф. М. Аблаев
Казанский (Приволжский) федеральный университет
Россия
Россия
Аблаев Фарид Мансурович, главный научный сотрудник Лаборатории «Квантовые методы обработки информации»
ул. Кремлевская, д. 18, г. Казань, 420008
А. В. Васильев
Федеральный исследовательский центр «Казанский научный центр Российской академии наук»; Казанский (Приволжский) федеральный университет
Россия
Россия
Васильев Александр Валерьевич, старший научный сотрудник Лаборатории квантовой оптики и информационных технологий; старший научный сотрудник Лаборатории «Квантовые методы обработки информации»
ул. Лобачевского, д. 2/31, г. Казань, 420111
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
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 quantum walks and quantum Hash schemes // Quantum Inf. Process. 2013. V. 12. P. 1501–1513. doi: 10.1007/s11128-012-0421-8.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. Chen S., Moore C., Russell A. Small-bias sets for nonabelian groups // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16thInternational Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013, Proceedings / Raghavendra P., Raskhodnikova S., Jansen K., Rolim J.D.P. (Eds.). Ser.: Lecture Notes in Computer Science. V. 8096. Berlin, Heidelberg: Springer, 2013. P. 436–451. doi: 10.1007/978-3-642-40328-6_31.
18. Аблаев Ф.М., Аблаев М.Ф., Васильев А.В. Универсальное квантовое хеширование // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2014. Т. 156, кн. 3. С. 7–18.
Рецензия
Для цитирования:
Аблаев М.Ф., Аблаев Ф.М., Васильев А.В. Анализ амплитудной формы квантовой хеш-функции. Ученые записки Казанского университета. Серия Физико-математические науки. 2023;165(1):5-15. https://doi.org/10.26907/2541-7746.2023.1.5-15
For citation:
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
Просмотров:
283
Послать статью по эл. почте 