Welcome to the resource topic for 2024/712
Title:
Quantum NV Sieve on Grover for Solving Shortest Vector Problem
Authors: Hyunji Kim, Kyoungbae Jang, Hyunjun Kim, Anubhab Baksi, Chakraborty Sumanta, Hwajeong Seo
Abstract:Quantum computers can efficiently model and solve several challenging problems for classical computers, raising concerns about potential security reductions in cryptography. NIST is already considering potential quantum attacks in the development of post-quantum cryptography by estimating the quantum resources required for such quantum attacks. In this paper, we present quantum circuits for the NV sieve algorithm to solve the Shortest Vector Problem (SVP), which serves as the security foundation for lattice-based cryptography, achieving a quantum speedup of the square root. Although there has been extensive research on the application of quantum algorithms for lattice-based problems at the theoretical level, specific quantum circuit implementations for them have not been presented yet.
Notably, this work demonstrates that the required quantum complexity for the SVP in the lattice of rank 70 and dimension 70 is 2^{43} (a product of the total gate count and the total depth) with our optimized quantum implementation of the NV sieve algorithm.
This complexity is significantly lower than the NIST post-quantum security standard, where level 1 is 2^{157}, corresponding to the complexity of Grover’s key search for AES-128.
ePrint: https://eprint.iacr.org/2024/712
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .