A Dimension-reduction Attack on Shortest Vector Problem Using Hints

Risheng, Yin

doi:10.11999/jeit251277

A Dimension-reduction Attack on Shortest Vector Problem Using Hints

2026-05-01

0

PRE

AI

DOI：10.11999/jeit251277

原文链接

原文求助

摘要

En 中文

目标基于学习误差问题（LWE）及其变体的密码学算法被广泛应用，包括密钥封装机制Kyber和数字签名方案Dilithium。在许多应用中，LWE的秘密是一个短向量。因此，将LWE归约到最短向量问题（SVP）是一种常见的密码分析方法。传统的SVP算法，包括枚举、格筛和格基约简，由于计算成本高，在高维格中难以直接应用。利用侧信道攻击，关于秘密向量的提示提供了一种新的解决SVP的方法。本文提出了一种基于此类提示的降维攻击方法。该方法利用提示降低问题维度，从而扩展枚举和筛法的实用范围。方法分析了两种类型的提示：整数提示和模数提示。对于提供最短向量精确内积信息的整数提示，问题被表述为整数方程组。然后利用该方程组的解空间，将最短向量表示为更短的线性形式。应用Hermite标准形和Gauss消元法获得特解和基础解系。这种表示减少了枚举或筛法中必须搜索或采样的未知系数数量。因此，搜索空间被缩小，原始SVP实例被转化为低维问题。对于提供最短向量模整数内积信息的模数提示，开发了一种基于Coppersmith引理的转换机制。对于同模模数方程，首先使用Lenstra-Lenstra-Lovász（LLL）格基约简降低行向量的范数，然后应用Gauss消元法减少非零项数量。根据Coppersmith引理筛选每个得到的模数方程。满足转换条件的方程被转化为整数方程。对于非同模模数方程，首先将模数分解为素幂模数。相同模数的方程被分组并按相同方式处理。然后使用降维枚举或筛法求解得到的整数方程。结果与讨论为评估提出的降维攻击，将基于枚举和筛法的算法与算法5中的格基约简算法在运行时间和解的精确性方面进行比较。首先分析了关键参数对降维的影响。这些参数包括筛选轮数（图2）、小根界（图3）和模数大小（图4）。算法3在不同参数设置下的转换效率总结于表1。结果表明，更多的筛选轮数通常能改善降维效果，但这种改善存在饱和点。超过该点后，额外的轮数收益有限。最后，比较了所提出方法与格基约简的计算效率（图5）。结果显示，枚举和筛法的计算成本随维度增加而迅速上升。然而，在维度90以内，降维攻击仍能利用提示降低维度并更高效地获得精确解。格基约简的运行时间随维度增长较慢，因此更适合高维SVP实例。结论提出的降维攻击为利用提示解决SVP提供了一种简单有效的方法。对于整数提示，利用相应方程组的解空间减少枚举和筛法中的变量数量。对于模数提示，利用Coppersmith引理将选定的模数方程转化为整数方程，将问题转化为整数提示情形。实验表明，在足够提示的情况下，该方法能有效降低格维度并扩展枚举和筛法的实用范围。与格基约简相比，降维后的枚举和筛法在其适用维度范围内能提供精确解。虽然随着提示数量增加降维效果趋于饱和，但适度的提示数量足以实现有效降维。这些结果表明，基于提示的降维攻击为精确解决SVP提供了实用途径，并为格密码方案的安全性评估提供了有用证据。

Keyword:

Learning With Errors (LWE)

Shortest Vector Problem (SVP)

Hints

Dimension-reduction attack

A Dimension-reduction Attack on Shortest Vector Problem Using Hints

摘要

期刊

机构

引用论文