Универсальное семейство хеш-функций на основе квантовых процедур

Ф.М. Аблаев, М.Т. Зиятдинов

Казанский физико-технический институт им. Е.К. Завойского ФИЦ Казанский научный центр РАН, г. Казань, 420029, Россия

Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.259-268

Для цитирования : Аблаев Ф.М., Зиятдинов М.Т. Универсальное семейство хеш-функций на основе квантовых процедур // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 259–268. – doi: 10.26907/2541-7746.2020.3.259-268.

For citation : Ablayev F.M., Ziatdinov M.T. Universal hash functions from quantum procedures. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 259–268. doi: 10.26907/2541-7746.2020.3.259-268. (In Russian)

Аннотация

Предложены процедуры построения универсального семейства хеш-функций на основе квантового хеширующего процесса, отображающего исходную последовательность w в квантовое хеш-состояние и далее случайным преобразованием в состояние |ψ) и порождением последовательности u, являющимся приближенным описанием состояния |ψ) .

Доказано, что предлагаемая процедура порождает семейство недетерминированных хеш-функций F, которые позволяют достоверно различать различные аргументы. Семейство F можно считать E-универсальным семейством недетерминированных хеш-функций.

Ключевые слова: квантовые хеш-функции, универсальное семейство хеш-функций, квантовое превосходство

Благодарности. Исследование выполнено за счет гранта Российского научного фонда (проект № 19-19-00656).

Литература

1. Feynman R.P. Quantum mechanical computers // Opt. News. – 1985. – V. 11, No 2. – P. 11–20. – doi: 10.1364/ON.11.2.000011.
2. Манин Ю.И. Вычислимое и невычислимое. – М.: Сов. радио, 1980. – 128 с.
3. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM Rev. – 1999. – V. 41, No 2. – P. 303–332. – doi: 10.1137/S0036144598347011.
4. Preskill J. Quantum computing in the NISQ era and beyond // Quantum. – 2018. – V. 2. – P. 79. – doi: 10.22331/q-2018-08-06-79.
5. Harrow A.W., Montanaro A. Quantum computational supremacy // Nature. – 2017. – V. 549, No 7671. – P. 203–209. – doi: 10.1038/nature23458.
6. Carter J.L, Wegman M.N. Universal classes of hash functions // J. Comput. Syst. Sci. – 1979. – V. 18, No 2. – P. 143–154.
7. Thorup M. High speed hashing for integers and strings. – 2015. – arXiv:1504.06804.
8. Stinson D.R., Paterson M. Cryptography: Theory and Practice. – Chapman and Hall/CRC, 2018. – 598 p.
9. Luby M., Wigderson A. Pairwise independence and derandomization // Found. Trends Theor. Comput. Sci. – 2005. – V. 1, No 4. – P. 237–301. – doi: 10.1561/0400000009.
10. Ablayev F., Ablayev M., Vasiliev A., Ziatdinov M. 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.
11. Diestel J., Spalsbury A. The Joys of Haar Measure. – Providence, RI: Am. Math. Soc., 2014. – xiv+320 p.
12. Аблаев Ф.М., Васильев А.В. Квантовое хеширование для квантовых коммуникаций. – Saarbrucken: LAMBERT Acad. Publ., 2015. – 84 с.
13. Radhakrishnan J., R¨otteler M., Sen P. Random measurement bases, quantum state distinction and applications to the hidden subgroup problem // Algorithmica. – 2009. – V. 55, No 3. – P. 490–516. – doi: 10.1007/s00453-008-9231-x.
14. Mohseni M., Read P., Neven H., Boixo S., Denchev V., Babbush R., Fowler A., Smelyanskiy V., Martinis J. Commercialize quantum technologies in five years // Nature. – 2017. – V. 543, No 7644. – P. 171–174.
15. Gambetta J.M., Chow J.M., Steffen M. Building logical qubits in a superconducting quantum computing system // npj Quantum Inf. – 2017. – V. 3. – Art. 2, P. 1–7. – doi: 10.1038/s41534-016-0004-0.
16. Svore K., Geller A., Troyer M., Azariah J., Granade C., Heim B., Kliuchnikov V., Mykhailova M., Paz A., Roetteler M. Q#: Enabling scalable quantum computing and development with a high-level DSL // RWDSL2018: Proc. Real World Domain Specific Languages Workshop 2018. – Vienna, 2018. – Art. 7, P. 1–10. – doi: 10.1145/3183895.3183901.
17. Gottesman D., Chuang I.L. Quantum digital signatures. – 2001. – arXiv:quantph/0105032.
18. Gavinsky D., Ito T. Quantum fingerprints that keep secrets // Electronic Colloquium on Computational Complexity. – 2010. – Report No. 165. – URL: https://eccc.weizmann.ac.il/report/2010/165/.

Поступила в редакцию 14.07.2020

Аблаев Фарид Мансурович, доктор физико-математических наук, главный научный сотрудник лаборатории нелинейной оптики; заведующий кафедрой теоретической кибернетики

Казанский физико-технический институт им. Е.К. Завойского ФИЦ Казанский науч-

ный центр РАН

ул. Сибирский тракт, д. 10/7, г. Казань, 420029, Россия

Казанский (Приволжский) федеральный университет ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: fablayev@gmail.com

Зиятдинов Мансур Тагирович, научный сотрудник лаборатории нелинейной оптики; научный сотрудник лаборатории «Квантовые методы обработки информации»

Казанский физико-технический институт им. Е.К. Завойского ФИЦ Казанский научный центр РАН

ул. Сибирский тракт, д. 10/7, г. Казань, 420029, Россия

Казанский (Приволжский) федеральный университет ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail: gltronred@gmail.com

Контент доступен под лицензией Creative Commons Attribution 4.0 License.