Universal hash functions from quantum procedures

F.M. Ablayev^∗ , M.T. Ziatdinov^∗∗

Zavoisky Physical-Technical Institute, FRC Kazan Scientific Center, Russian Academy of Sciences, Kazan, 420029 Russia Kazan Federal University, Kazan, 420008 Russia

E-mail: ^∗fablayev@gmail.com, ^∗∗gltronred@gmail.com

Received July 14, 2020

Full text PDF
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)

Abstract

Modern quantum technologies are NISQ (Noisy Intermediate-Scale Quantum) devices, which are used to create insufficiently accurate quantum computers with low computing power. However, quantum technologies have advanced considerably during the past years. Thus, the issue of demonstrating “quantum supremacy” in the era of NISQ technologies is on the agenda. This study demonstrates that “quantum supremacy” is forthcoming. We propose procedures for constructing a universal family of hash functions based on a quantum hashing process that maps the original sequence w to a quantum hash state and then by random transformation to the state |ψ) and generating the sequence u, which is an approximate description of the state |ψ). We proved that the proposed procedure generates a family of nondeterministic hash functions F, which allow us to reliably distinguish between different arguments. The F family can be considered an E-universal family of nondeterministic hash functions. We assume that the development of this research area will cast light on the effect of “quantum supremacy” and will also have a certain impact on the advance of post-quantum cryptography.

Keywords: quantum hash functions, universal hash family, quantum supremacy

Acknowledgments. The study was supported by the Russian Science Foundation (project no. 19-19-00656).

References

1. Feynman R.P. Quantum mechanical computers. Opt. News, 1985, vol. 11, no. 2, pp. 11–20. doi: 10.1364/ON.11.2.000011.
2. Manin Yu.I. Vychislimoe i nevychislimoe [Computable and Noncomputable]. Moscow, Sov. Radio, 1980. 128 p. (In Russian)
3. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev., 1999, vol. 41, no. 2, pp. 303–332. doi: 10.1137/S0036144598347011.
4. Preskill J. Quantum computing in the NISQ era and beyond. Quantum, 2018, vol. 2, p. 79. doi: 10.22331/q-2018-08-06-79.
5. Harrow A.W., Montanaro A. Quantum computational supremacy. Nature, 2017, vol. 549, no. 7671, pp. 203–209. doi: 10.1038/nature23458.
6. Carter J.L, Wegman M.N. Universal classes of hash functions. J. Comput. Syst. Sci., 1979, vol. 18, no. 2, pp. 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. In: Found. Trends Theor. Comput. Sci., 2005, vol. 1, no. 4, pp. 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, vol. 4, no. 4, pp. 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. Ablayev F.M., Vasiliev A.V. Kvantovoe kheshirovanie dlya kvantovykh kommunikatsii [Quantum Hashing for Quantum Communications]. Saarbrucken, LAMBERT Acad. Publ., 2015. 84 p. (In Russian)
13. Radhakrishnan J., R¨otteler M., Sen P. Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. Algorithmica, 2009, vol. 55, no. 3, pp. 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, vol. 543, no. 7644, pp.171–174.
15. Gambetta J.M., Chow J.M., Steffen M. Building logical qubits in a superconducting quantum computing system. npj Quantum Inf., 2017, vol. 3, art. 2, pp. 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, pp. 1–10. doi: 10.1145/3183895.3183901.
17. Gottesman D., Chuang I.L. Quantum digital signatures. 2001. arXiv:quant-ph/0105032.
18. Gavinsky D., Ito T. Quantum fingerprints that keep secrets. Electronic Colloquium on Computational Complexity, 2010, report no. 165. Available at: https://eccc.weizmann.ac.il/report/2010/165/.

The content is available under the license Creative Commons Attribution 4.0 License.