A Reduced-rank Attacks on SVP 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 have emerged in large numbers. This paper addresses the challenge of solving the Shortest Vector Problem (SVP) in high-dimensional lattices, which is crucial for the security of lattice-based cryptographic algorithms like Kyber and Dilithium. Traditional SVP solving algorithms like enumeration and sieving become computationally infeasible in high dimensions. This paper introduces a novel reduced-rank attack that leverages hints about the secret vector to significantly reduce the dimensionality of the problem, enabling the use of more efficient algorithms like enumeration and sieving. Methods This paper presents a comprehensive analysis of two distinct types of hints: perfect hints and modular hints. For perfect hints, which provide exact information about the secret vector, the research formulates the problem as a system of integer equations. The proposed algorithms utilize the solution space of these equations to reduce the search space for enumeration and sieving. Specifically, the method employs Hermite normal form transformation and Gaussian elimination to derive a compact representation of the secret vector, effectively reducing the number of variables that need to be enumerated. This approach decreases the computational complexity from exponential to a more manageable level, enabling precise solutions of SVP instances. For modular hints, which provide information about the secret vector modulo some integer, this paper develops a conversion mechanism based on Coppersmith’s method. This technique identifies and converts a subset of modular equations into integer equations, allowing the problem to be reduced to the perfect hint scenario. The algorithm employs LLL lattice basis reduction and Gaussian elimination to preprocess the modular equations, followed by a systematic screening process that applies Coppersmith’s lemma to determine which equations can be successfully converted. This multi-step approach effectively expands the range of applicable hints and increases the practicality of the attack. Results and Discussions To verify the performance of rank-reduced attack, this paper compares the proposed algorithms with the traditional lattice basis reduction method (Algorithm 5) in terms of runtime and solution accuracy. First, the impact of various parameters on the dimensionality reduction effect was analyzed. Number of screening rounds ( Fig. 2 ), small root bound (Fig. 3 ) and modulus size (Fig. 4 ) are considered to evaluate the effect. A statistical summary of the conversion efficiency of Algorithm 3 under different parameter settings is given (Table 1 ). The data confirms that while increasing rounds helps, the dimensionality reduction efficiency exhibits a “saturation point,” beyond which additional rounds yield diminishing returns. Finally, the computational efficiency of the proposed methods is compared against the lattice basis reduction algorithm (Fig. 5 ). The experimental results demonstrate that the computational overhead for enumeration and sieving increases rapidly with dimension. However, for dimensions within 90, the reduced-rank attack remains more efficient. In contrast, the lattice basis reduction algorithm shows a slower rate of increase in runtime with dimension, making it more suitable for higher-dimensional problems.Conclusions The research concludes that the reduced-rank attack represents a practical and effective methodology for solving SVP in high-dimensional lattices. The experimental results confirm that the method can significantly extend the applicability of enumeration and sieving techniques, enabling precise solution of SVP instances that would otherwise be computationally infeasible. The findings demonstrate the potential of leveraging side information to overcome the limitations of traditional SVP solving algorithms and offer new perspectives for further research in lattice-based cryptography and post-quantum security analysis. This work makes several significant contributions to the field: it introduces novel dimensionality reduction techniques for SVP, provides a comprehensive analysis of hint utilization in lattice attacks, establishes practical parameter boundaries for attack effectiveness, and offers a comparative evaluation of different solving approaches. The methodology presented has important implications for the security assessment of lattice-based cryptographic schemes and contributes to the ongoing development of post-quantum cryptography. -
Key words:
- Learning with Errors (LWE) /
- Shortest Vector Problem (SVP) /
- Hints /
- Reduced-rank attacks
-
Kannan枚举 输入：格$ \mathcal{L} $，基$ {b}_{1},{b}_{2},\cdots ,{b}_{n}\in {R}^{n} $ 输出：最短向量$ s $ 1. 假设最短向量$ s $在下的表示系数为$ ({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} $枚举结束后，由当前表示系数还原最短向量$ s $ 
下载: 导出CSV
Gauss筛法 输入：格$ \mathcal{L} $，基$ {b}_{1},{b}_{2},\cdots ,{b}_{n}\in {R}^{n} $，近似最短向量长度$ \mu $，阈值
c输出：最短向量$ s $ 1. 初始化列表$ L=\{0\} $，栈$ \boldsymbol{S}=\varnothing $，碰撞次数$ K=0 $ 2. 若栈$ \boldsymbol{S} $非空，弹出向量$ {v}_{\mathrm{new}} $，否则采样新格向量$ {v}_{\mathrm{new}} $ 3. 对$ {v}_{\mathrm{new}} $高斯约减直至无法约减 4. 若$ {v}_{\mathrm{new}}=0 $则$ K=K+1 $，返回步骤2 5. 检查$ L $中是否存在$ {v}_{j} $满足$ ||{v}_{\mathrm{new}}-{v}_{j}|| \lt \mu $ 6. 存在则输出$ s={v}_{\mathrm{new}}-{v}_{j} $并终止算法，否则将$ {v}_{\mathrm{new}} $加入$ L $ 7. 如果$ K \lt c $则返回步骤2，否则终止算法
下载: 导出CSV
算法1 基于整数方程的枚举算法 输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i}) $ 输出：最短向量$ s $ 1. 将$ [\boldsymbol{V}\boldsymbol{B}|-\lambda ] $转换成Hermite标准形$ \mathbf{{\boldsymbol{V}}^{\prime}} $ 2. 求$ \mathbf{{\boldsymbol{V}}^{\prime}}\cdot x=0 $的解空间，得到秘密向量$ x $由特解$ t $和基础解系$ {r}_{1},{r}_{2},\cdots ,{r}_{n-m} $的表示形式 3. 利用引理1求解$ {c}_{1},{c}_{2},\cdots ,{c}_{n-m} $并还原$ x $ 4. 根据方程$ s=\boldsymbol{B}\cdot x $恢复最短向量$ s $并输出
下载: 导出CSV
算法2 基于整数方程的筛法 输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i}) $ 输出：最短向量$ s $ 1. 将$ [\boldsymbol{V}\boldsymbol{B}|-\lambda ] $转换成Hermite标准形$ {V}^{\prime} $ 2. 求$ \mathbf{{\boldsymbol{V}}^{\prime}}\cdot x=0 $的解空间，得到秘密向量$ x $由特解$ t $和基础解
系$ {r}_{1},{r}_{2},\cdots ,{r}_{n-m} $的表示形式3. 利用$ {r}_{1},{r}_{2},\cdots ,{r}_{n-m} $和特解$ t $构造样本向量 4. 利用引理2求解$ {c}_{1},{c}_{2},\cdots ,{c}_{n-m} $并还原$ x $ 5. 根据方程$ s=\boldsymbol{B}\cdot x $恢复最短向量$ s $并输出
下载: 导出CSV
算法3 基于共模方程的规约求解算法 输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i},K) $ 输出：最短向量$ s $ 1. 基于$ ({v}_{i},{\lambda }_{i},K) $构造模方程组，并构建系数矩阵 2. 通过LLL算法降低矩阵的行向量范数，高斯消元减少非零项 3. 对于矩阵的每一行，利用引理4判断是否能够转换为整数方程 4. 整理所有整数方程，将问题归约到基于整数提示信息的情形 5. 调用算法1或算法2求解最短向量$ s $
下载: 导出CSV
算法4 基于非共模方程的规约求解算法 输入：格$ \mathcal{L} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i},{K}_{i}) $ 输出：最短向量$ s $ 1. 对模数$ {K}_{i} $标准分解，并将共模的模方程整合成若干方程组 2. 对每个方程组进行LLL预处理，并用高斯消元减少向量中的非
零项3. 对于矩阵的每一行，利用引理4判断是否能够转换为整数方程 4. 整理所有整数方程，将问题归约到基于整数提示信息的情形 5. 调用算法1或算法2求解最短向量$ s $
下载: 导出CSV
算法5 格基约化求解算法 输入：格$ \mathcal{L} $，基矩阵$ \boldsymbol{B} $，$ m $组提示信息$ ({v}_{i},{\lambda }_{i},{K}_{i}) $ 输出：最短向量$ s $ 1. 构造$ n+m $维格基矩阵$ {\boldsymbol{A}}_{1} $或$ {\boldsymbol{A}}_{2} $ 2. 利用引理3预处理格基矩阵 3. 取约化后的首向量作为目标向量的近似值 4. 还原最短向量$ 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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]. Proceedings of 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] 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. (查阅网上资料,本条文献与第11条文献重复,请确认). [23] 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)
计量
- 文章访问数: 26
- HTML全文浏览量: 5
- PDF下载量: 6
- 被引次数: 0
下载:
