A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems

A. O. Bakharev

Novosibirsk State University, 2 Pirogov Street, 630090 Novosibirsk, Russia

Abstract: Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given. Tab. 4, illustr. 10, bibliogr. 48.

Keywords: quantum search, public-key cryptography, lattice-based cryptography, post-quantum cryptography, Grover's algorithm, quantum computation.

UDC: 519.7

Received: 27.06.2023
Revised: 27.11.2023
Accepted: 22.03.2024

DOI: 10.33048/daio.2024.31.777

 English version: Journal of Applied and Industrial Mathematics, 2024, 18:3, 395–411