Paper 2023/1565
Finding Shortest Vector Using Quantum NV Sieve on Grover
Abstract
Quantum computers, especially those with over 10,000 qubits, pose a potential threat to current public key cryptography systems like RSA and ECC due to Shor's algorithms. Grover's search algorithm is another quantum algorithm that could significantly impact current cryptography, offering a quantum advantage in searching unsorted data. Therefore, with the advancement of quantum computers, it is crucial to analyze potential quantum threats. While many works focus on Grover’s attacks in symmetric key cryptography, there has been no research on the practical implementation of the quantum approach for lattice-based cryptography. Currently, only theoretical analyses involve the application of Grover's search to various Sieve algorithms. In this work, for the first time, we present a quantum NV Sieve implementation to solve SVP, posing a threat to lattice-based cryptography. Additionally, we implement the extended version of the quantum NV Sieve (i.e., the dimension and rank of the lattice vector). Our extended implementation could be instrumental in extending the upper limit of SVP (currently, determining the upper limit of SVP is a vital factor). Lastly, we estimate the quantum resources required for each specific implementation and the application of Grover's search. In conclusion, our research lays the groundwork for the quantum NV Sieve to challenge lattice-based cryptography. In the future, we aim to conduct various experiments concerning the extended implementation and Grover's search.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Shortest Vector ProblemLattice based cryptographyQuantum NV SieveQuantum attackGrover's search
- Contact author(s)
-
khj1594012 @ gmail com
starj1023 @ gmail com
oyj0922 @ gmail com
wjseok @ kisti re kr
livezone @ kisti re kr
d2estiny @ kisti re kr
kibae @ kisti re kr
hwajeong84 @ gmail com - History
- 2023-10-13: approved
- 2023-10-11: received
- See all versions
- Short URL
- https://ia.cr/2023/1565
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1565,
author = {Hyunji Kim and Kyoungbae Jang and Yujin Oh and Woojin Seok and Wonhuck Lee and Kwangil Bae and Ilkwon Sohn and Hwajeong Seo},
title = {Finding Shortest Vector Using Quantum {NV} Sieve on Grover},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1565},
year = {2023},
url = {https://eprint.iacr.org/2023/1565}
}