A Dimension-reduction Attack on Shortest Vector Problem Using Hints

YIN Risheng; CAO Jinzheng; MA Yongliu; WANG Hong; CHENG Qingfeng

doi:10.11999/JEIT251277

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

YIN Risheng, CAO Jinzheng, MA Yongliu, WANG Hong, CHENG Qingfeng. A Dimension-reduction Attack on Shortest Vector Problem Using Hints[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251277

Citation:

YIN Risheng, CAO Jinzheng, MA Yongliu, WANG Hong, CHENG Qingfeng. A Dimension-reduction Attack on Shortest Vector Problem Using Hints[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251277

Citation:

PDF( 1539 KB)

A Dimension-reduction Attack on Shortest Vector Problem Using Hints

doi: 10.11999/JEIT251277 cstr: 32379.14.JEIT251277

School of Cyberspace Security, Information Engineering University, Zhengzhou 450001, China

Funds: The National Natural Science Foundation of China(62472438), The Natural Science Foundation of Henan (242300421414)

Received Date: 2025-12-02
Accepted Date: 2026-04-08
Rev Recd Date: 2026-04-07

Available Online: 2026-04-27

Abstract

Abstract

Objective Cryptographic algorithms based on the Learning With Errors (LWE) problem and its variants are widely used, including the key encapsulation mechanism Kyber and the digital signature scheme Dilithium. In many applications, the LWE secret is a short vector. Therefore, reducing LWE to the Shortest Vector Problem (SVP) is a common approach to cryptanalysis. Traditional SVP algorithms, including enumeration, lattice sieving, and lattice basis reduction, become difficult to apply directly in high-dimensional lattices because of their high computational cost. With the use of side-channel attacks, hints about the secret vector provide a new way to solve SVP. This paper proposes a dimension-reduction attack based on such hints. The method uses hints to reduce the problem dimension, thereby extending the practical range of enumeration and sieving. Methods Two types of hints are analyzed: integer hints and modular hints. For integer hints, which provide exact inner-product information about the shortest vector, the problem is formulated as a system of integer equations. The solution space of this system is then used to represent the shortest vector in a shorter linear form. Hermite normal form and Gaussian elimination are applied to obtain a particular solution and a fundamental solution system. This representation reduces the number of unknown coefficients that must be searched in enumeration or sampled in sieving. Thus, the search space is reduced, and the original SVP instance is transformed into a lower-dimensional problem. For modular hints, which provide inner-product information about the shortest vector modulo an integer, a conversion mechanism based on Coppersmith’s lemma is developed. For common-modulus modular equations, Lenstra-Lenstra-Lovász (LLL) lattice basis reduction is first used to reduce the norms of row vectors. Gaussian elimination is then applied to decrease the number of nonzero terms. Each resulting modular equation is screened according to Coppersmith’s lemma. Equations that satisfy the conversion condition are transformed into integer equations. For non-common-modulus modular equations, the moduli are first factorized into prime-power moduli. Equations with the same modulus are grouped and processed in the same manner. The resulting integer equations are then solved using the dimension-reduction enumeration or sieving method. Results and Discussions To evaluate the proposed dimension-reduction attack, the enumeration-based and sieving-based algorithms are compared with the lattice basis reduction algorithm in Algorithm 5 in terms of runtime and solution exactness. The effect of key parameters on dimension reduction is first analyzed. These parameters include the number of screening rounds (Fig. 2), the small-root bound (Fig. 3), and the modulus size (Fig. 4). The conversion efficiency of Algorithm 3 under different parameter settings is summarized in Table 1. The results show that more screening rounds generally improve the reduction effect, but this improvement has a saturation point. Beyond this point, additional rounds provide limited benefit. Finally, the computational efficiency of the proposed methods is compared with that of lattice basis reduction (Fig. 5). The results show that the computational cost of enumeration and sieving increases rapidly with dimension. However, up to dimension 90, the dimension-reduction attack can still use hints to reduce the dimension and obtain exact solutions more efficiently. Lattice basis reduction shows a slower increase in runtime as the dimension grows and is therefore more suitable for higher-dimensional SVP instances. Conclusions The proposed dimension-reduction attack provides a simple and effective method for solving SVP using hints. For integer hints, the solution space of the corresponding equation system is used to reduce the number of variables in enumeration and sieving. For modular hints, Coppersmith’s lemma is used to convert selected modular equations into integer equations, reducing the problem to the integer-hint case. The experiments show that, when sufficient hints are available, the method can effectively reduce the lattice dimension and extend the practical range of enumeration and sieving. Compared with lattice basis reduction, enumeration and sieving after dimension reduction can provide exact solutions within their applicable dimension range. Although the reduction effect tends to saturate as the number of hints increases, a moderate number of hints is sufficient to achieve effective dimension reduction. These results indicate that hint-based dimension-reduction attacks offer a practical route for exact SVP solving and provide useful evidence for the security evaluation of lattice-based cryptographic schemes.
- Learning With Errors (LWE),
- Shortest Vector Problem (SVP),
- Hints,
- Dimension-reduction attack

FullText(HTML)

References(22)

References

[1]	KANNAN R. Improved algorithms for integer programming and related lattice problems[C]. The 15th Annual ACM Symposium on Theory of Computing, New York, USA, 1983: 193–206. doi: 10.1145/800061.808749.
[2]	AONO Y and NGUYEN P Q. Random sampling revisited: Lattice enumeration with discrete pruning[C]. The 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Pairs, France, 2017: 65–102. doi: 10.1007/978-3-319-56614-6_3.
[3]	ZHENG Zhongxiang, WANG Xiaoyun, XU Guangwu, et al. Orthogonalized lattice enumeration for solving SVP[J]. Science China Information Sciences, 2018, 61(3): 032115. doi: 10.1007/s11432-017-9307-0.
[4]	YAMAMURA K, WANG Yuntao, and FUJISAKI E. Improved lattice enumeration algorithms by primal and dual reordering methods[C]. The 24th International Conference on Information Security and Cryptology, Seoul, South Korea, 2022: 159–174. doi: 10.1007/978-3-031-08896-4_8.
[5]	ALBRECHT M R, BAI Shi, LI Jianwei, et al. Lattice reduction with approximate enumeration oracles: Practical algorithms and concrete performance[C]. The Advances in Cryptology-41st Annual International Cryptology Conference, 2021: 732–759. doi: 10.1007/978-3-030-84245-1_25.
[6]	AONO Y, NGUYEN P Q, and SHEN Yixin. Quantum lattice enumeration and tweaking discrete pruning[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Brisbane, Australia, 2018: 405–434. doi: 10.1007/978-3-030-03326-2_14.
[7]	AJTAI M, KUMAR R, and SIVAKUMAR D. A sieve algorithm for the shortest lattice vector problem[C]. The 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001: 601–610. doi: 10.1145/380752.380857.
[8]	MICCIANCIO D and VOULGARIS P. Faster exponential time algorithms for the shortest vector problem[C]. The 21st Annual ACM-SIMA Symposium on Discrete Algorithms, Austin, USA, 2010: 1468–1480.
[9]	BONNETAIN X, CHAILLOUX A, SCHROTTENLOHER A, et al. Finding many collisions via reusable quantum walks: Application to lattice sieving[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques Advances in Cryptology, Lyon, France, 2023: 221–251. doi: 10.1007/978-3-031-30589-4_8.
[10]	LENSTRA A K, LENSTRA H W, and LOVÁSZ L. Factoring polynomials with rational coefficients[J]. Mathematische Annalen, 1982, 261(4): 515–534. doi: 10.1007/BF01457454.
[11]	SCHNORR C P and EUCHNER M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems[J]. Mathematical Programming, 1994, 66(1/3): 181–199. doi: 10.1007/BF01581144.
[12]	CHEN Yuanmi and NGUYEN P Q. BKZ 2.0: Better lattice security estimates[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security Advances in Cryptology, Seoul, South Korea, 2011: 1–20. doi: 10.1007/978-3-642-25385-0_1.
[13]	ALBRECHT M R, BAI Shi, FOUQUE P A, et al. Faster enumeration-based lattice reduction: Root hermite factor k^1/(2k) time k^k/8+o(k)[C]. The 40th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2020: 186–212. https://doi.org/10.1007/978-3-030-56880-1_7.
[14]	袁庆军, 张浩金, 樊昊鹏, 等. DTDS: 用于侧信道能量分析的Dilithium数据集[J]. 电子与信息学报, 2025, 47(8): 2499–2508. doi: 10.11999/JEIT250048. YUAN Qingjun, ZHANG Haojin, FAN Haopeng, et al. DTDS: Dilithium dataset for power analysis[J]. Journal of Electronics & Information Technology, 2025, 47(8): 2499–2508. doi: 10.11999/JEIT250048.
[15]	罗玉玲, 徐海洋, 欧阳雪, 等. 高效侧信道分析: 从协同去噪到自适应B样条降维[J]. 电子与信息学报, 2026, 48(3): 1354–1365. doi: 10.11999/JEIT251047. LUO Yuling, XU Haiyang, OUYANG Xue, et al. High-efficiency side-channel analysis: From collaborative denoising to adaptive B-spline dimension reduction[J]. Journal of Electronics & Information Technology, 2026, 48(3): 1354–1365. doi: 10.11999/JEIT251047.
[16]	DACHMAN-SOLED D, DUCAS L, GONG Huijing, et al. LWE with side information: Attacks and concrete security estimation[C]. The 40th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2020: 329–358. doi: 10.1007/978-3-030-56880-1_12.
[17]	LI Zhiwei, XU Jun, SONG Jun, et al. Improved attacks against lattice-based KEMs using hints from Hertzbleed[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025, 2025(4): 463–485. doi: 10.46586/tches.v2025.i4.463-485.
[18]	LU Qian, FENG Yansong, and PAN Yanbin. Solving LWE with independent hints about secret and errors[EB/OL]. https://eprint.iacr.org/2025/1128, 2025.
[19]	DAMM S, FISCHER A, MAY A, et al. Solving concealed ILWE and its application for breaking masked dilithium[EB/OL]. https://eprint.iacr.org/2025/1629, 2025.
[20]	陈韬, 赵旺鹏, 别梦妮, 等. 格基后量子密码双域可重构多项式乘法运算单元架构研究[J]. 电子与信息学报, 2025. doi: 10.11999/JEIT250929. (查阅网上资料,未找到对应的卷期页码信息,请确认). CHEN Tao, ZHAO Wangpeng, BIE Mengni, et al. Research on the architecture of dual-field reconfigurable polynomial multiplication unit for lattice-based post-quantum cryptography[J]. Journal of Electronics & Information Technology, 2025. doi: 10.11999/JEIT250929.
[21]	CAO Jinzheng, JIANG Haodong, and CHENG Qingfeng. Refined attack on LWE with hints: Constructing lattice via Gaussian elimination[C]. The 45th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 2025: 385–416. doi: 10.1007/978-3-032-01855-7_13.
[22]	HOWGRAVE-GRAHAM N. Finding small roots of univariate modular equations revisited[C]. 6th IMA International Conference on Cryptography and Coding, Cirencester, UK, 1997: 131–142. doi: 10.1007/BFb0024458.