Paper 2024/712 Original: eprint.iacr.org/2024/712 ↗

Concrete Quantum Cryptanalysis of Shortest Vector Problem

Abstract

This paper presents quantum circuits for the Nguyen–Vidick (NV) sieve algorithm to solve the Shortest Vector Problem (SVP) in lattice-based cryptography. We focus on optimizing the circuit depth of the quantum NV sieve, leveraging Grover’s algorithm to reduce the search complexity. Using the proposed quantum NV sieve, we estimate the quantum re- sources required to solve SVP for various dimensions. Specifically, for a dimension size of 512 (the parameter for Kyber-512), our implemen- tation achieves a quantum attack cost of 2126.0045 in terms of the gate count–depth product metric used by National Institute of Standards and Technology (NIST). To optimize circuit depth, we employ carry-lookahead and carry-save adders for efficient multi-addition operations. Further, our quantum NV sieve performs precise sieving by implementing fixed-point arithmetic, incorporating essential components (such as input setting, up-scaling, and two’s complement). To the best of our knowledge, previous work on quantum cryptanaly- sis of SVP using the sieve algorithm has remained theoretical, without proposing quantum circuits. Our work humbly demonstrates that the post-quantum security of lattice- based cryptography (with respect to the quantum attack complexity) falls between that of multivariate-based and code-based cryptography.