格

本文介绍了基于格的证明系统，并重点解释了最有前途的解决方案Greyhound的工作原理。Greyhound是一种多项式承诺方案（PCS），它依赖于模块短整数解（M-SIS）问题，该问题被认为是量子计算机也难以解决的。文章还讨论了如何将Greyhound整合到LaBRADOR中，以实现更小的证明尺寸和亚线性验证时间。

本文从几何角度介绍了LWE问题，解释了格的概念，包括整数格和q元整数格的定义和性质，以及商群、行列式和到格的距离。讨论了随机格中短向量的存在性，介绍了SIS问题，并探讨了如何使用求解SIS的算法来求解LWE问题，最后给出了实际参数的选取建议，以及LWE和SIS在密码学中的应用，例如 Kyber 和 Dilithium。

本文深入探讨了LaBRADOR，一种基于标准格假设的证明系统，该系统利用递归实现亚线性证明大小。文章详细解释了LaBRADOR的核心思想，包括模块短整数解（M-SIS）问题、Ajtai承诺、多项式环以及用于检查向量是否为短向量的NormCheck子协议，并介绍了如何通过分解处理Ajtai承诺中的向量长度问题，以及如何利用外层承诺和递归来优化协议。

本文深入浅出地介绍了格密码学的基本概念，包括格的定义、格中的难题（最短向量问题和最近向量问题），以及如何利用格构造加密方案——“带错误的学习”（LWE）。文章还解释了LWE方案的安全性与格的难题之间的联系，并简要提及了Kyber等实际应用方案。

本文分析了一种基于平方根小数部分的伪随机数生成器（DRBG），并展示了如何利用格理论破解它，通过将问题转化为求解丢番图方程，并利用格约简算法在低维格中找到最近向量，从而恢复隐藏的整数，揭示了该DRBG在密码学上的脆弱性，强调了格理论在密码分析中的应用。