A New Quantum Oracle Model for a Hybrid Quantum-Classical Attack on Post-Quantum Lattice-Based Cryptosystems

Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetriccryptography currently in use. Most attacks on these cryptosystems can be reduced to theshortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oraclemodel from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on theGaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle isproposed and analyzed. Two implementations of the new quantum oracle model are proposed andestimated. The complexity of implementing the new quantum oracle model to attackpost-quantum lattice-based cryptosystems that are finalists of the NIST post-quantumcryptography competition is analyzed. Comparison of obtained results for new and existingmodels of quantum oracle is given.