Gauss Sieve Quantum Circuit Design Method Based on Grover’s Algorithm

doi:10.3969/j.issn.1671-1122.2026.02.004

Abstract

Abstract:

Sieve is the fastest approach to solve the shortest vector problem in the lattice. In practice, the heuristic sieve has become a new type of attack against lattice-based cryptography due to its low time complexity and excellent attack efficiency. With the rapid advancement of quantum computing, quantum algorithms enable the quantum sieve to achieve the optimal asymptotic time complexity theoretically, but the research on specific circuit design for quantum sieve is still in the primary stage. In this paper, a quantum circuit design scheme of Gauss sieve based on Grover’s quantum search algorithm was proposed, which discussed in depth the quantum circuit design of the two core search processes in Gauss sieve and their key operations, and the corresponding Oracle black box quantum circuits were successfully constructed. Through the analysis and verification of toy examples, the scheme not only can be correctly executed under the quantum computing model, but also effectively reduces the time complexity of the Gauss sieve. This result provides new ideas and methods for the research of quantum sieve realization in the post-quantum cryptography era.

Key words: Gauss sieve, Grover’s quantum search algorithm, quantum circuit, shortest vector problem

CLC Number:

TP309

CAO Renlong, HU Honggang. Gauss Sieve Quantum Circuit Design Method Based on Grover’s Algorithm[J]. Netinfo Security, 2026, 26(2): 224-235.

Figures/Tables 10

References 21

[1]	HELLMAN M. New Directions in Cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 644-654. doi: 10.1109/TIT.1976.1055638 URL
[2]	RIVEST R L, SHAMIR A, ADLEMAN L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126. doi: 10.1145/359340.359342 URL
[3]	ELGAMAL T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469-472. doi: 10.1109/TIT.1985.1057074 URL
[4]	MERKLE R, HELLMAN M. Hiding Information and Signatures in Trapdoor Knapsacks[J]. IEEE Transactions on Information Theory, 1978, 24(5): 525-530.
[5]	SHOR P W. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]// IEEE. The 35th Annual Symposium on Foundations of Computer Science. New York: IEEE, 1994: 124-134.
[6]	LAGARIAS J C, ODLYZKO A M. Solving Low-Density Subset Sum Problems[J]. Journal of the ACM (JACM), 1985, 32(1): 229-246. doi: 10.1145/2455.2461 URL
[7]	COSTER M J, LAMACCHIA B A, ODLYZKO A M, et al. An Improved Low-Density Subset Sum Algorithm[C]// Springer. Workshop on the Theory and Application of Cryptographic Techniques. Heidelberg: Springer, 1991: 54-67.
[8]	COPPERSMITH D. Finding a Small Root of a Univariate Modular Equation[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 1996: 155-165.
[9]	COPPERSMITH D. Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 1996: 178-189.
[10]	VAN EMDE BOAS P. Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice[D]. Amsterdam: University of Amsterdam, 1981.
[11]	AJTAI M. The Shortest Vector Problem in L2 is NP-Hard for Randomized Reductions[C]// ACM. The 30th Annual ACM Symposium on Theory of Computing. New York: ACM, 1998: 10-19.
[12]	AJTAI M, KUMAR R, SIVAKUMAR D. A Sieve Algorithm for the Shortest Lattice Vector Problem[C]// ACM. The 33rd Annual ACM Symposium on Theory of Computing. New York: ACM, 2001: 601-610.
[13]	NGUYEN P Q, VIDICK T. Sieve Algorithms for the Shortest Vector Problem Are Practical[J]. Journal of Mathematical Cryptology, 2008, 2(2): 181-207. doi: 10.1515/JMC.2008.009 URL
[14]	MICCIANCIO D, VOULGARIS P. Faster Exponential Time Algorithms for the Shortest Vector Problem[C]// ACM. The 21st Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2010: 1468-1480.
[15]	MERMIN N D. Quantum Computer Science: An Introduction[M]. Cambridge: Cambridge University Press, 2007.
[16]	GROVER L K. Quantum Mechanics Helps in Searching for a Needle in a Haystack[J]. Physical Review Letters, 1997, 79(2): 325-328. doi: 10.1103/PhysRevLett.79.325 URL
[17]	BRASSARD G, HOYER P, MOSCA M, et al. Quantum Amplitude Amplification and Estimation[J]. Contemporary Mathematics, 2002, 305: 53-74.
[18]	LAARHOVEN T, MOSCA M, VAN DE POL J. Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search[C]// Springer. International Workshop on Post-Quantum Cryptography. Heidelberg: Springer, 2013: 83-101.
[19]	KIM H, JANG K, OH Y, et al. Finding Shortest Vector Using Quantum NV Sieve on Grover[C]// Springer. International Conference on Information Security and Cryptology. Heidelberg: Springer, 2023: 97-118.
[20]	KIM H, JANG K, KIM H, et al. Quantum NV Sieve on Grover for Solving Shortest Vector Problem[EB/OL]. (2024-05-29)[2025-02-01]. https://eprint.iacr.org/2024/712.
[21]	DORIGUELLO J F, GIAPITZAKIS G, LUONGO A, et al. On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem[EB/OL]. (2024-10-17)[2025-02-01]. https://doi.org/10.48550/arXiv.2410.1375.

算法步骤	经典/量子寄存器变量	值
STEP 1	${{Q}_{v}}$	{2,-8, 6,-4, 10}
STEP 1	${{Q}_{w}}$	{2,-3, 1,-3, 6}
STEP 2	${{Q}_{v}}$	{2,-8, 6,-4, 10}
STEP 2	${{Q}_{w}}$	{2,-3, 1,-3, 6}
STEP 3	$Dup\_{{Q}_{w}}$	{2,-3, 1,-3, 6}
STEP 4.1	${{Q}_{aux}}$	{4,-11, 7,-7, 16}
STEP 4.2	${{Q}_{v}}$	{-2, 8,-6, 4,-10}
STEP 4.3	${{Q}_{v}}$	{0, 5,-5, 1,-4}
STEP 5.1	sign_flag [0: rank-1]	{0, 0, 0, 0, 0}
STEP 5.2	sign_flag [rank: 2rank-1]	{0, 1, 1, 1, 1}
STEP 5.3	${{Q}_{v}}$	{0, 5, 5, 1, 4}
	${{Q}_{w}}$	{2, 3, 1, 3, 6}
	${{Q}_{aux}}$	{4, 11, 7, 7, 16}
STEP 5.4	output1	{8, 33, 7, 21, 96}
STEP 5.5	output2	{0,-15,-5,-3,-24}
STEP 6	result1	${{00000010100101}_{\left( 2 \right)}}$ (165)
STEP 6	result2	${{11111111010001}_{\left( 2 \right)}}$ (-47)
STEP 7	MSB	0
STEP 7	MSB	1

算法步骤	经典/量子寄存器变量	值
STEP 1	${{Q}_{v}}$	{1,-4, 3,-2, 5}
	${{Q}_{w}}$	{-2, 3,-1, 3, 6}
	${{Q}_{v2}}$	${{00000000110111}_{\left( 2 \right)}}$ (55)
STEP 2	${{Q}_{v}}$	{1,-4, 3,-2, 5}
	${{Q}_{w}}$	{-2, 3,-1, 3, 6}
	${{Q}_{v2}}$	${{00000000110111}_{\left( 2 \right)}}$ (55)
STEP 3.1	sign_flag[0: rank-1]	{1, 1, 1, 1, 0}
	${{Q}_{v}}$	{1, 4, 3, 2, 5}
	${{Q}_{w}}$	{2, 3, 1, 3, 6}
STEP 3.2	output	{-2,-12,-3,-6, 30}
STEP 4	result	${{11111111111001}_{\left( 2 \right)}}$ (-7)
STEP 5.1	result	${{00000000010100}_{\left( 2 \right)}}$ (20)
STEP 5.2	MSB	0
STEP 6.1	${{Q}_{v2}}$	${{11111111001001}_{\left( 2 \right)}}$ (-55)
STEP 6.2	result	${{11111111011101}_{\left( 2 \right)}}$ (-35)
STEP 6.3	MSB	1

算法	时间复杂度	空间复杂度
高斯筛法^[14]	${{2}^{0.415d+o\left( d \right)}}$	${{2}^{0.2075d+o\left( d \right)}}$
本文量子高斯筛法	${{2}^{0.311d+o\left( d \right)}}$	${{2}^{0.2075d+o\left( d \right)}}$

筛法	预言机	QRAM	加法器	乘法器	额外CNOT门	量子比特数
本文高斯筛法	$O_{\text{gauss}}^{\left( 1 \right)}$	1	4D-2	2D	2Dk+4	6Dk+5D+5k
本文高斯筛法	$O_{\text{gauss}}^{\left( 2 \right)}$	1	D+1	D	2D+4	3Dk+3D+5k
本文 NV筛法	${{O}_{\text{NV}}}$	1	2D	D	2D	3Dk+3D+5k
NV筛法^[20]	$O'_{\text{NV}}$	1	2D	D	Dk	4Dk+4D+5k