计算复杂性理论是研究各种计算模型、探究各种计算问题求解有效算法的存在性、比较计算问题求解的困难程度并据其复杂度进行分类研究的理论。本书对这些基础理论知识进行了全面介绍。在此基础上，引入了格的LLL算法、最近平面算法和格的某些困难问题的相关复杂度研究结果，并进一步介绍计算复杂性在密码学中的应用，尝试为读者呈现计算复杂性理论和密码学相融合的知识体系，特别适合于从事密码学尤其是从事基于格的后量子密码研究的读者。