基于Grover算法的高斯筛法量子线路设计方法

doi:10.3969/j.issn.1671-1122.2026.02.004

摘要/Abstract

摘要：

筛法是求解格中最短向量问题的最快方法。在实际应用中，启发式筛法因其较低的时间复杂度和卓越的攻击效率，成为针对格密码算法的新型攻击手段。随着量子计算技术迅猛发展，量子算法的引入使量子筛法在理论上能够达到最优的渐近时间复杂度，但目前针对量子筛法的电路设计研究仍处于初级阶段。因此，文章提出一种基于Grover量子搜索算法的高斯筛法量子线路设计方案，深入探讨高斯筛法中两个核心搜索过程的量子电路设计及其关键操作，并成功构建相应Oracle黑盒的量子线路。通过玩具示例验证该方案不仅能够在量子计算模型下正确执行，而且能有效降低高斯筛法的时间复杂度。

关键词: 高斯筛法, Grover量子搜索算法, 量子线路, 最短向量问题

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

中图分类号:

TP309

曹仁龙, 胡红钢. 基于Grover算法的高斯筛法量子线路设计方法[J]. 信息网络安全, 2026, 26(2): 224-235.

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

图/表 10

图1

图2

图3

图4

图5

表1

表2

表3

表4

图6

参考文献 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