当前位置：首页 > news >正文

网站建设网站制作江西seo推广方案

news 2025/8/5 1:32:05

网站建设网站制作,江西seo推广方案,WordPress主题get,做展示型企业网站目录一. LWE问题的鲁棒性二. LWE其他分布选择三. 推荐文献四. 附密码学人心中的顶会一. LWE问题的鲁棒性 robustness，翻译为鲁棒性已有的论文表明，及时敌手获取到部分关于秘密和error的信息，LWE问题依旧是困难的，这能…

一. LWE问题的鲁棒性

二. LWE其他分布选择

三. 推荐文献

四. 附密码学人心中的顶会

一. LWE问题的鲁棒性

robustness，翻译为鲁棒性

已有的论文表明，及时敌手获取到部分关于秘密和error的信息，LWE问题依旧是困难的，这能体现出该问题的鲁棒性。

在2010年，Goldwasser等人发现，如果限定秘密的模长，或者将关于秘密的很难求逆的函数值（类似单向函数）告诉敌手，该问题的困难性和原始的LWE问题是一样的。在实际证明归约的过程中，维度n和误差率 $\alpha$ 都是相对较小的。基于此理论可以设计一个对称的密码（symmetric-key encryption）方案，其允许密钥不太完美或者被泄露部分信息。

如果给出计算意义上很难求逆的单向函数值，2010年Dodis证明即使如此依旧可以基于LWE问题设计公钥密码方案。

在后来的工作中，人们陆续发现了LWE问题的鲁棒性提现：忽略维度和误差率（error rate）的变化，及时秘密和error的部分线性关系被泄露，LWE问题依旧是可证明安全的。

二. LWE其他分布选择

回顾LWE问题我们发现，其error的选择有两个要点：1.来源高斯分布；2.值相对较小。那么现在我们就在想，error能不能来自于其他分布，比如说在某个区间上的均匀分布呢？

在2013年，有两篇相关的工作，一个是Dottling-Muller，另一个是Micciancio-Peikert。这些人都证明了选择其他非高斯分布也是可以的。

选其他分布会比高斯分布更好吗？

从算法设计的层面来讲，像均匀分布比高斯分布更容易实现，所以在网络安全领域更加具有应用价值。

在2011年，Arora 和Ge发现，如果把error的尺寸范围设定为d，那么解决LWE问题的时间和空间复杂度为：

$2^{d^2}$

这显然给LWE问题的困难性证明带来了极大的挑战，好在这类攻击算法要求给定的LWE样本足够多。

接下里我们将简短解释LWE的样本个数如何影响问题的困难性。

对于非高斯分布的error（比如说可以选择均匀分布），哪怕error选取的空间很小，比如只能取0或1，也就是：

$\lbrace 0,1\rbrace$

只要给与敌手的样本个数为m是有上限的，那么LWE问题依旧是困难的。如果将该上限去掉的话，那么根据Arora-Ge攻击算法，LWE问题可直接被攻破。举几个简单的例子。

如果error只是简单的二进制，那么样本个数需要限定为：

如果error的尺寸放宽到：

那么样本个数也可以放宽到：

其实有点惊讶，当error只取0或1时，LWE问题也是困难的。但是其样本个数太少了，导致很难利用其设计密码系统。

已有的研究表明，先从足够大的高斯error中选取，再形成标准的LWE分布，然后再调整更大的维度，再将此分布作为后续search-LWE问题中的ai，那么形成的新问题在信息论（information-theoretically）上是无法解决的。此时的ai选择并不是真的随机分布，问题变得更加困难了。要想证明其安全性的话，也比较直接。因为标准的LWE分布与均匀分布之间是不可区分的，只要标准的decision-LWE问题困难，那么小-error版本的LWE问题也就是困难的。