【格密码基础】：补充LWE问题

目录

一. LWE问题的鲁棒性

二. LWE其他分布选择

三. 推荐文献

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

---

一. LWE问题的鲁棒性

robustness，翻译为鲁棒性

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

在2010年，Goldwasser等人发现，如果限定秘密的模长，或者将关于秘密的很难求逆的函数值（类似单向函数）告诉敌手，该问题的困难性和原始的LWE问题是一样的。在实际证明归约的过程中，维度n和误差率都是相对较小的。基于此理论可以设计一个对称的密码（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问题的时间和空间复杂度为：

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

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

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

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

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

如果error的尺寸放宽到：

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

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

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

三. 推荐文献

（1）总结LWE与SIS问题

D. Micciancio and C. Peikert. Hardness of SIS and LWE with small parameters. In CRYPTO,
pages 21–39. 2013.

（2）攻击LWE问题

S. Arora and R. Ge. New algorithms for learning in presence of errors. In ICALP (1), pages
403–415. 2011.

（3）证明LWE问题的鲁棒性

S. Ling, D. H. Phan, D. Stehle, and R. Steinfeld. Hardness of ´ k-LWE and applications in traitor
tracing. In CRYPTO, pages 315–334. 2014.

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

（1）欧密

会议简称：EUROCRYPT

会议全称：International Conference on the Theory and Applications of Cryptographic Techniques

出版社：Springer

（2）美密

会议简称：CRYPTO

会议全称：International Cryptology Conference

出版社：Springer

（3）亚密

会议简称：ASIACRYPT

会议全称：Annual International Conference on the Theory and Application of Cryptology and Information Security

出版社：Springer

（4）CHES

会议简称：CHES

会议全称：International Conference on Cryptographic Hardware and Embedded Systems

出版社：Springer

（5）PKC

会议简称：PKC

会议全称：International Workshop on Practice and Theory in Public Key Cryptography

出版社：Springer