最新的基于格的密码体制几乎都直接基于如下两个平均复杂性的问题:最小整数解(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问题,给出构造的通式以及随机化的构造。