Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems

A. O. Bakharev

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 43-48

Résumé

Every year, quantum computing is developing with increasing force. Therefore, there is a need to design and analyze cryptosystems that will be resistant to attacks using a quantum computer. The security of many well-known post-quantum lattice-based cryptosystems depends on the complexity of solving the shortest vector problem (SVP). One of the most efficient algorithms to solve this problem is the GaussSieve algorithm. For the previously proposed model of the quantum oracle used in the hybrid quantum-classical algorithm for solving SVP, new updated bounds of the number of qubits and the depth of the scheme are obtained. This improvement is achieved by optimizing all quantum operations with integers used in the model. A new quantum oracle model is proposed and analyzed, which uses classical memory to store a list of vectors. This model requests the number of qubits that is logarithmic to the length of the list in the GaussSieve algorithm. Upper bounds on the complexity of the attack of post-quantum cryptosystems that have become finalists of the NIST competition have been obtained. These upper bounds indicate that the exponential length of the list from the GaussSieve algorithm imposes limitations on the possibility of implementing hybrid attacks on the known standards of post-quantum cryptosystems.

Détail

Keywords: quantum search, public-key cryptography, post-quantum cryptography.