混合对偶与Meet-LWE攻击及Gabidulin码密码系统分析

### 混合对偶与Meet - LWE攻击及Gabidulin码密码系统分析 #### 混合对偶与Meet - LWE攻击概述 在解决稀疏三元学习误差（LWE）问题时，存在三种混合对偶攻击方法，分别是新提出的混合对偶Meet - LWE攻击以及之前的Hybrid1和Hybrid2攻击。这三种攻击方法在不同的参数条件下表现各有优劣。 - **复杂度分析**：新攻击的复杂度与Hybrid1和Hybrid2攻击有所不同。当$k = 1$时，新攻击的$T_e = (2B + 1)k/2$值较大，达到$2^{79}$，这使得其复杂度比其他一些攻击方法大很多。这主要是因为当$q$值较大时，格基规约后误差的范围$B$也会变大。而Hybrid1和Hybrid2攻击主要受$B/q$的相对值影响，而非$B$的绝对值。 - **不同参数下的性能比较** - 当权重比$w/n$较小时且$q$不是太大，新攻击的性能优于Hybrid1和Hybrid2攻击。 - 当权重比$w/n$较大时，新攻击和Hybrid2攻击的性能都不如Hybrid1攻击，有时甚至比对偶攻击还差。 - 当$q$非常大时，新攻击会因$T_e$值大而受到影响，若权重比$w/n$足够小，Hybrid2攻击的性能最佳。 为了直观展示三种攻击方法的优势，我们考虑一系列具有全同态加密（FHE）类型参数的稀疏三元LWE问题。对于$\log n$分别取10、11、12、13的情况，选择合适的$q$值，使得对应的三元秘密方案的比特安全性在128到256之间。对于每一组$n$和$q$，考虑$w$分别为64、128、192三种不同的值，并固定$\sigma = 8/\sqrt{2\pi} \approx 3.2$。比较结果如图1所示，该图大致可分为三个区域，对应上述三种情况： | $\log n$值 | 最佳攻击方法情况 | | ---- | ---- | | $\log n = 12$ | 新攻击在大多数情况下表现最佳 | | $\log n = 10, 11$ | 随着权重比$w/n$增大，Hybrid1攻击在大多数情况下表现最佳；新攻击在权重较小的情况下表现最佳，如$\log n = 11$且$w = 64$的所有情况 | | $\log n = 13$ | 由于对应的$q$值变大，Hybrid2攻击在大多数情况下表现最佳；新攻击在$q$值较小时表现最佳 | 基于这些结果，一些FHE实现（如HElib和HEAAN），若其参数处于新攻击的优势区域，应重新评估其参数。不过，这些结果对NIST后量子密码标准化第三轮的方案没有影响，因为基于LWE的方案不采用稀疏三元秘密项（除了NTRULPrime，但对于这些方案，Hybrid1攻击效果更好），而基于NTRU的方案不能用对偶攻击来评估其比特安全性。 此外，由于Hybrid1攻击的性能总是不低于对偶攻击，所以在比较中未包含对偶攻击。同时，将这三种攻击与原始攻击进行比较，发现混合对偶攻击在大多数情况下比原始攻击效果更好。 #### 密码系统分析：Gabidulin码密码系统 在量子时代，基于数论问题的公钥密码系统会受到Shor算法的严重威胁，因此基于编码理论的密码系统成为了有潜力的替代方案。其中，基于Gabidulin码的密码系统因其公钥表示紧凑而受到关注，但大多数相关变体由于Gabidulin码的固有结构弱点已被破解。 ##### 背景与相关密码系统 - **McEliece密码系统**：1978年提出，使用Goppa码作为底层线性码，但由于密钥尺寸大，未在实际中广泛应用。后来的改进方案主要分为两类：一是用其他汉明度量码替换Goppa码；二是使用具有其他度量的码。 - **GPT密码系统**：1991年由Gabidulin等人提出，基于秩度量码，即基于Gabidulin码的加密方案。此后出现了一些基于Gabidulin码的变体，但大多因结构弱点被破解。 - **Lau - Tan密码系统**：2018年提出，公钥由两部分组成，一是受随机码干扰的Gabidulin码的生成矩阵（该随机码具有最大秩权重$n$），二是秩权重为$n$的向量。这种掩盖Gabidulin码结构的技术可防止一些现有攻击。 ##### 研究贡献 - **Gabidulin码生成向量性质**：Gabidulin码的所有生成向量与零向量构成一个一维线性空间。对于固定的生成向量$g$，其他生成向量形式为$\gamma g$（$\gamma \in F_{qm}^*$），这意味着在$F_{qm}$上的Gabidulin码共有$q^m - 1$个生成向量。 - **计算生成向量的新方法**：引入了一种与以往不同的方法，从任意生成矩阵计算Gabidulin码的生成向量。 - **密钥恢复攻击**：提出了一种简单而有效的密钥恢复攻击方法，可在多项式时间内恢复Lau - Tan密码系统的私钥，从而完全破解该密码系统。具体是将恢复私钥的问题转化为在基域上求解多元线性方程组。 - **系统修复**：提出了一种简单有效的修复方案，该方案能抵御现有结构攻击，且具有更大的信息传输率。对于该修复方案，提出的攻击需要指数级复杂度。 - **应用于其他密码系统**：将该攻击方法应用于分析Loidreau在2017年提出的另一个基于Gabidulin码的密码系统，降低了恢复等效私钥的复杂度。 ##### 预备知识 - **基本概念和符