Paper 2024/712

Quantum NV Sieve on Grover for Solving Shortest Vector Problem

Hyunji Kim, Hansung University
Kyungbae Jang, Hansung University
Hyunjun Kim, Hansung University
Anubhab Baksi, Nanyang Technological University
Sumanta Chakraborty, Techno International New Town
Hwajeong Seo, Hansung University
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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Shortest Vector ProblemGrover's searchLattice-based cryptographyQuantum Security.
Contact author(s)
khj1594012 @ gmail com
starj1023 @ gmail com
khj930704 @ gmail com
anubhab001 @ e ntu edu sg
sumantapapan @ gmail com
hwajeong84 @ gmail com
History
2024-05-15: last of 2 revisions
2024-05-09: received
See all versions
Short URL
https://ia.cr/2024/712
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2024/712,
      author = {Hyunji Kim and Kyungbae Jang and Hyunjun Kim and Anubhab Baksi and Sumanta Chakraborty and Hwajeong Seo},
      title = {Quantum {NV} Sieve on Grover for Solving Shortest Vector Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2024/712},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/712}},
      url = {https://eprint.iacr.org/2024/712}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.