Quantum Algorithm for the Invariant Estimate of the Closeness of Classical Ciphers to the One-Time Pad

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

An invariant measure of the closeness of a block cipher to the perfect (ideal) cipher of the one-time pad has been proposed. The measure is the same for any implementation of the one-time pad. A quantum algorithm based on the determination of the eigenvalue (phase) of the quantum state has been proposed to estimate the closeness of the block cipher to ideal in terms of the proposed measure with high probability and accuracy.

About the authors

S. N Molotkov

Academy of Cryptography of the Russian Federation; Osipyan Institute of Solid State Physics, Russian Academy of Science

Author for correspondence.
Email: sergei.molotkov@gmail.com
121552, Moscow, Russia; 142432, Chernogolovka, Moscow region, Russia

References

  1. D. Deutsch and R.Jozsa, Proceedings of the Royal Society of London, Series A: Mathematical and Physical Sciences 439(1907), 553 (1992).
  2. P. W. Shor, SIAM J.Comput. 26(5), 1484 (1997).
  3. L. K.Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. ACM Press, N. Y., USA (1996), p. 212.
  4. D. R. Simon, SIAM J.Comput. 26(5), 1474 (1997).
  5. M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia, arXiv:1602.05973 [quan-ph], (2016).
  6. A. Ambainis, Quantum Walk Algorithm for Element Distinctness, 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE (2014), p. 22; https://ieeexplore.ieee.org/document/1366221.
  7. A. W. Harrow, A. Hassidim, and S. Lloyd, Phys. Rev. Lett. 103(15), 150502 (2009).
  8. D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher1, and L. Wossnig, arXiv:0311001 [quant-ph], (2014).
  9. M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwand, arXiv:1512.04965 [quant-ph] (2015).
  10. M. Almazrooie, A. Samsudin, R. Abdullah, and K. N. Mutter, SpringerPlus 5(1), 1494 (2016).
  11. M. Almazrooie, A. Samsudin, R. Abdullah, and K. N. Mutter, Quantum Grover Attack on the Simpli ed-AES, Proceedings of the 2018 7th International Conference on Software and Computer Applications, ACM, N.Y., NY, USA (2018), p. 204.
  12. Д. В. Денисенко, Г. Б. Маршалко, М. В. Никитенкова, В. И. Рудской, В. А. Шишкин, ЖЭТФ 155, 645 (2019).
  13. V. Gheorghiu and M.Mosca, A resource estimation framework for quantum attacks against cryptographic functions - recent developments, (2021); https://globalriskinstitute.org.
  14. M. Piani and M. Mosca, Quantum threat timeline report, (2020); https://globalriskinstitute.org.
  15. M.Piani, M.Mosca, Quantum threat timeline report (2019); https://globalriskinstitute.org.
  16. V. Gheorghiu and M.Mosca, A resource estimation framework for quantum attacks against cryptographic functions, Global Risk Institute quantum risk assessment report (2020); https://globalriskinstitute.org.
  17. V. Gheorghiu and M. Mosca, A resource estimation framework for quantum attacks against cryptographic functions, part 4, Global Risk Institute quantum risk assessment report (2018); https://globalriskinstitute.org.
  18. V. Gheorghiu and M. Mosca, A resource estimation framework for quantum attacks against cryptographic functions, part 3, Global Risk Institute quantum risk assessment report (2018); https://globalriskinstitute.org.
  19. V. Gheorghiu and M.Mosca, A resource estimation framework for quantum attacks against cryptographic functions, part 2, Global Risk Institute quantum risk assessment report (2018); https://globalriskinstitute.org.
  20. V. Gheorghiu and M.Mosca, A resource estimation framework for quantum attacks against cryptographic functions, part 1, Global Risk Institute quantum risk assessment report (2017); https://globalriskinstitute.org.
  21. Y.-A. Chen and X.-S. Gao, arXiv:1712.06239 [quant-ph] (2018).
  22. A. Ambainis, arXiv:1010.4458 [quant-ph] (2010).
  23. A. M. Childs, R. Kothari, and R. D. Somma, SIAM Journal on Computing. 46(6), 1920 (2017).
  24. L. Wossnig, Z. Zhao, and A. Prakash, Phys. Rev. Lett. 120(5), 050502 (2018).
  25. G. Brassard, P. Hoyer, and A. Tapp, ACM SIGACT News 28(2), 14 (1997).
  26. A. Chailloux, M. Naya-Plasencia, and A. Schrottenloher, An E cient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography, preprint (2017); https://eprint.iacr.org/2017/847.
  27. G. Brassard, P. Hoyer, and A. Tapp, arXiv:0005055 [quant-ph] (2000).
  28. T. H¨aner and M. Soeken, arXiv:2006.03845 [quant-ph] (2020).
  29. M. Roetteler and R. Steinwandt, Inf. Process. Lett. 115(1), 40 (2015).
  30. A. Hosoyamada and E. Aoki, On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers, ed. by S. Obana and K. Chida, Springer International Publishing AG, WSEC 2017, LNCS 10418, Springer Nature Switzerland AG, Geneva (2017)p. 3; https://link.springer.com/chapter/10.1007/978-3-319-64200-0_1.
  31. X.Bonnetain, M. Naya-Plasencia, and A. Schrottenloher, On Quantum Slide Attacks, preprint (2018); https://eprint.iacr.org/2018/1067.pdf.
  32. А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления, МЦНМО-ЧеРо, М. (1999), 192 с.
  33. G. Leander and A.May, Grover Meets Simon - Quantumly Attacking the FX-construction, Advances in Cryptology ? ASIACRYPT 2017 23rd International Conference on the Theory and Applications of Cryptology and Information Security Hong Kong, China, December 3-7, 2017 Proceedings, Part II, Springer (2017).
  34. G. S. Vernam, Journal of the IEEE 55, 109 (1926).
  35. В. А. Котельников, Отчет (19 Июня, 1941); https://cryptography-museum.ru.
  36. C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, July, 379 (1948)
  37. Oct., 623 (1948)
  38. The material in this paper appeared originally in a con dential report A Mathematical Theory of Cryptography, dated Sept. 1, (1945); https://www.iacr.org>shannon>shannon45.
  39. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, Cambridge, N.Y., Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi, Dubai, Tokyo, Mexico City (2010).
  40. S. N. Molotkov, Laser Phys. Lett. 19, 045201 (2022).
  41. S. N. Molotkov, Laser Phys. Lett. 19, 075203 (2022).
  42. И. М. Арбеков, С. Н. Молотков, ЖЭТФ 152, 62 (2017).
  43. С. Н. Молотков, Письма в ЖЭТФ 103, 389 (2016).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 Российская академия наук