附近网站建设公司,外贸网站dns,山西推广型网站开发,wordpress不要分页目录
一. LWE问题的鲁棒性
二. LWE其他分布选择
三. 推荐文献
四. 附密码学人心中的顶会 一. LWE问题的鲁棒性
robustness#xff0c;翻译为鲁棒性
已有的论文表明#xff0c;及时敌手获取到部分关于秘密和error的信息#xff0c;LWE问题依旧是困难的#xff0c;这能…目录
一. 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 4CHES
会议简称CHES
会议全称International Conference on Cryptographic Hardware and Embedded Systems
出版社Springer 5PKC
会议简称PKC
会议全称International Workshop on Practice and Theory in Public Key Cryptography
出版社Springer
