三个平均复杂性问题的研究

发布时间：2024-07-11 05:16

　　最新的基于格的密码体制几乎都直接基于如下两个平均复杂性的问题:最小整数解(SmallestInteger Solution,SIS)问题和误差学习(Learning With Errors,LWE)问题。人们提出了很多求解SIS问题和LWE问题的理论算法,但对于实际应用中的复杂性估计还不足,密码设计中参数的选取还比较模糊。此外,平均复杂性的理论已被研究很多年。distNP类是平均复杂性形式的NP类,且有完全问题。Liven证明了所有自然的NP完全问题都有平均复杂性的形式,但是他给出的概率分布是不自然的。本文要研究的三个问题是SIS问题、LWE问题的求解算法和一个平均复杂性的可满足性(Satisfiability,SAT)问题的构造,并作出了如下三方面的工作:1.给出一个求解SIS问题和一个求解LWE问题的算法,并给出Darmstadt Lattice Challenge 和 Darmstadt LWE Challenge 的实验结果。实验结果证明了所述方案的可行性和高效性。2.给出将SIS问题和LWE问题转换为SAT问题的方法。3.构造一个具有平均复杂性的SAT问题,给出构造的通式以及...

【文章页数】：80 页

【学位级别】：硕士

【部分图文】：

图２．１?—个二维格上的离散高斯分布??

近似。所以Ｌ＞ｓ，ｃ也可以被有效得近似。对于不特殊说明的情??况，我们默认ｃ为原点，ｓ等于１。??连续高斯分布可以离散地推广到集合上，令??Ｐｓ，ｃ｛＾）?＝?＾ｘ￡ＡＰｓ，ｃ｛．＊＾）??对于格Ａ，定义离散高斯分布ＤＡ，ｓ，ｅ为??Ｖｘ?Ｇ?Ａ，?Ｄａ＾ｃ（ｘ）?＝??如前面所....

图２．２?—个二维格??

第二章预备知识??定义２．３丄（格）令５?＝?＆１，＆２，．．．，心（：１＾为７１个线性无关的向量组成的??集合，以Ｊ３为基的格￡（Ｂ）?＝?｛＾＾＝１而？?：ａ?Ｇ?Ｚ｝，通常记为Ａ?＝?￡（ｊＢ）。ｎ和??ｍ分别称为格的秩和维数。??事实上，格与欧几里得线性空间定义的区别在于....

图２．３?—个三维格??对于两组线性无关的向量Ｓ和如果即前者中的格点??

第二章预备知识??定义２．３丄（格）令５?＝?＆１，＆２，．．．，心（：１＾为７１个线性无关的向量组成的??集合，以Ｊ３为基的格￡（Ｂ）?＝?｛＾＾＝１而？?：ａ?Ｇ?Ｚ｝，通常记为Ａ?＝?￡（ｊＢ）。ｎ和??ｍ分别称为格的秩和维数。??事实上，格与欧几里得线性空间定义的区别在于....

图３．１当ｆｃ?＝?６０，?６?＝?２４和ｆｃ?＝?８０，?６?＝?３０时，得到的比值￥与维数ｎ的关系??

导数，可以确定参??数Ａ：、６的值。??关于存储空间，因为前一部分利用ＢＫＺ算法，故所需的存储空间为关于维??数ｎ的某个多项式；因为后一部分利用递进高斯筛法，故所需的存储空间为关于??维数ｎ的指数函数，但远低于高斯筛法所需的存储空间。??对?Ｄａｒｍｓｔａｄｔ?Ｌａｔｔｉｃｅ?Ｃ....

本文编号：4005305