A Dimension-reduction Attack on Shortest Vector Problem Using Hints
-
摘要: 基于容错学习(LWE)问题及其变体设计的密码算法应用十分广泛，如密钥封装机制Kyber、数字签名Dilithium等。事实上，LWE问题的秘密向量通常为短向量，因此将LWE问题规约到最短向量问题(SVP)是一种常见的求解思路。传统SVP的求解算法包括枚举、筛法以及格基约化算法等。随着侧信道攻击的引入，SVP的求解产生了一些新的思路。该文针对提示信息进行分析，提出了整数提示信息和带模提示信息下的SVP降维攻击方法。实验结果表明，降维攻击方法在实际中具有较强的可行性，能够有效扩展枚举和筛法的应用上界。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. -
1 Kannan枚举
输入：格$ \mathcal{L} $，基$ \boldsymbol{b}_1,\boldsymbol{b}_2,\cdots,\boldsymbol{b}_n\in R^n $ 输出：最短向量$ {\boldsymbol{s}} $ 1. 假设最短向量$ {\boldsymbol{s}} $在b1, b2, ···, bn下的表示系数为$ ({x}_{1},{x}_{2},\cdots ,{x}_{n}) $，
初始化为$ (0,0,\cdots ,1) $；2. 利用高斯启发式估计$ {\lambda }_{1}(\mathcal{L}) $的范数$ ||{\lambda }_{1}(\mathcal{L})|| $； 3. 从$ {x}_{n} $开始依次枚举，计算当前最短向量的范数并与
$ ||{\lambda }_{1}(\mathcal{L})|| $比较；4. 如果当前最短向量范数小于$ ||{\lambda }_{1}(\mathcal{L})|| $则继续枚举下一个表示
系数分量，否则重新枚举上一表示系数分量；5. 当表示系数$ {x}_{1} $枚举结束后，由当前表示系数还原最短向量$ {\boldsymbol{s}} $。 
下载: 导出CSV
2 高斯筛法
输入：格$ \mathcal{L} $，基$ \boldsymbol{b}_1,\boldsymbol{b}_2,\cdots,\boldsymbol{b}_n\in R^n $，近似最短向量长度$ \mu $，阈值c 输出：最短向量$ \boldsymbol{s} $ 1. 初始化列表$ L=\{0\} $，栈$ \boldsymbol{S}=\varnothing $，碰撞次数$ K=0 $； 2. 若栈$ \boldsymbol{S} $非空，弹出向量$ {{\boldsymbol{v}}}_{\mathrm{new}} $，否则采样新格向量$ {{\boldsymbol{v}}}_{\mathrm{new}} $； 3. 对$ {{\boldsymbol{v}}}_{\mathrm{new}} $高斯约减直至无法约减； 4. 若$ {{\boldsymbol{v}}}_{\mathrm{new}}=0 $则$ K=K+1 $，返回步骤2； 5. 检查$ L $中是否存在$ \boldsymbol{v}_j $满足$ ||\boldsymbol{v}_{\mathrm{new}}-\boldsymbol{v}_j|| \lt \mu $； 6. 存在则输出$ \boldsymbol{s}=\boldsymbol{v}_{\mathrm{new}}-\boldsymbol{v}_j $并终止算法，否则将$ {{\boldsymbol{v}}}_{\mathrm{new}} $加入$ L $； 7. 如果$ K \lt c $则返回步骤2，否则终止算法。
下载: 导出CSV
3 基于整数方程的枚举算法
输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i}) $ 输出：最短向量$ \boldsymbol{s} $ 1. 将$ [{\boldsymbol{V}\boldsymbol{B}}|-\lambda ] $转换成Hermite标准形$ \mathbf{{\boldsymbol{V}}^{\prime}} $； 2. 求$ \mathbf{{\boldsymbol{V}}^{\prime}}\cdot \boldsymbol{x}=0 $的解空间，得到秘密向量$ \boldsymbol{x} $由特解$ \boldsymbol{t} $和基础解系
$ \boldsymbol{r}_1,\boldsymbol{r}_2,\cdots,\boldsymbol{r}_{n-m} $的表示形式；3. 利用引理1求解$ {c}_{1},{c}_{2},\cdots ,{c}_{n-m} $并还原$ {\boldsymbol{x}} $； 4. 根据方程$ {\boldsymbol{s}}=\boldsymbol{B}\cdot {\boldsymbol{x}} $恢复最短向量$ {\boldsymbol{s}} $并输出。
下载: 导出CSV
4 基于整数方程的筛法
输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i}) $ 输出：最短向量$ s $ 1. 将$ [{\boldsymbol{V}\boldsymbol{B}}|-\boldsymbol{\lambda} ] $转换成Hermite标准形$ {{\boldsymbol{V}}}^{\prime} $； 2. 求$ \mathbf{{\boldsymbol{V}}^{\prime}}\cdot \boldsymbol{x}=0 $的解空间，得到秘密向量$ \boldsymbol{x} $由特解$ \boldsymbol{t} $和基础解
系$ \boldsymbol{r}_1,\boldsymbol{r}_2,\cdots,\boldsymbol{r}_{n-m} $的表示形式；3. 利用$ \boldsymbol{r}_1,\boldsymbol{r}_2,\cdots,\boldsymbol{r}_{n-m} $和特解$ \boldsymbol{t} $构造样本向量； 4. 利用引理2求解$ {c}_{1},{c}_{2},\cdots ,{c}_{n-m} $并还原$ \boldsymbol{x} $； 5. 根据方程$ \boldsymbol{s}=\boldsymbol{B}\cdot \boldsymbol{x} $恢复最短向量$ \boldsymbol{s} $并输出。
下载: 导出CSV
7 格基约化求解算法
输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i},{K}_{i}) $ 输出：最短向量$ {\boldsymbol{s}} $ 1. 构造$ n+m $维格基矩阵$ {\boldsymbol{A}}_{1} $或$ {\boldsymbol{A}}_{2} $； 2. 利用引理3预处理格基矩阵； 3. 取约化后的首向量作为目标向量的近似值； 4. 还原最短向量$ {\boldsymbol{s}} $。
下载: 导出CSV
表 1 算法3转化效率统计表
轮数 小根上界 原始维数 平均降维维度 降维后维度 转化效率(%) 1 1 70
80
9016
15
1354
65
7722.86
18.75
14.442 70
80
909
7
961
73
8112.86
8.75
10.002 1 70
80
9035
36
2834
44
6250.00
45.00
31.112 70
80
9017
16
1553
64
6524.29
20.00
16.673 1 70
80
9035
40
3435
40
4650.00
50.00
37.782 70
80
9025
24
2945
56
6135.71
30.00
32.22
下载: 导出CSV
-
[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 k1/(2k) time kk/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. -
图(5) / 表(8)
计量
- 文章访问数: 119
- HTML全文浏览量: 52
- PDF下载量: 26
- 被引次数: 0
下载:
