Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm | Applied Discrete Mathematics. Supplement. 2021. № 14. DOI: 10.17223/2226308X/14/13

Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm

Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In the paper, a model of the quantum oracle which is required for the implementation of the hybrid quantum-classical algorithm for solving SVP is proposed and analyzed. For the public key post-quantum cryptosystem NTRU which is the finalist of the third round of the NIST competition, upper bounds for the number of qubits and the depth of the scheme are obtained. The bounds are based on the proposed model of the quantum oracle.

Download file

Counter downloads: 29

Keywords

post-quantum cryptography, public-key cryptography, quantum search, cryptosystem NTRU

Authors

Name	Organization	E-mail
Bakharev A. O.	Novosibirsk State University; JetBrains Research Crypto Lab	sana.bakharev@gmail.com

Всего: 1

References

Zhong H.-S., Wang H., Deng Y.-H., et al. Quantum computational advantage using photons. Science. 2020. V. 370. Iss. 6523. P. 1460-1463.

Chen C., Danba O., Hoffstein J., et al. NTRU Algorithm Specifications and Supporting Documentation. https://ntru.org/, 2019.

Nielsen M. A. and Chuang I. L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010.

https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions.

Grover L. K. A fast quantum mechanical algorithm for database search // 28th Ann. ACM Symp. Theory Comput. (STOC). 1996. P. 212-219.

Micciancio D. and Voulgaris P. Faster exponential time algorithms for the Shortest Vector roblem // 21st Ann. ACM Symp. Discrete Algorithms (SODA). 2010. P. 1468-1480.

Laarhoven T., Mosca M., and van de Pol J. Finding shortest lattice vectors faster using quantum search // Des. Codes Cryptogr. 2015. V. 77. No. 2-3. P. 375-400.