登录 后可观看高清视频

ZK 白板 S3M3: 基于格的 SNARKs

14次播放
2026-03-26

视频 AI 总结：

本视频深入探讨了格密码学及其在零知识证明中的应用。主讲人Vadim Lubashevsky首先介绍了格密码学中的核心难题——小整数解问题（SIS），并在此基础上构建了Ajtai承诺方案。随后，视频详细阐述了一个两阶段的证明系统，用于证明对一个长向量s的知识及其范数（大小）的约束。该证明系统结合了“左右技术”来确保范数的紧密性。最后，视频讨论了如何通过在多项式环上进行操作，显著提高这些格基证明的效率。

视频中提出的关键信息：

  1. 格密码学基础：

    • SIS 问题 (Small Integer Solution Problem)： 格密码学中的核心难题，被认为是量子安全的。它涉及给定矩阵A和目标t，找到一个具有小系数的向量s，使得As = t (mod q)。
    • Ajtai 承诺方案： 基于 SIS 问题构建，通过计算 As = t 来承诺向量 s。该方案具有压缩性（将长向量 s 压缩为短向量 t）和绑定性（难以找到不同的 s' 满足 As' = t）。

  2. 格基证明系统构建：

    • 初步证明（知识承诺）： 证明者知道一个满足 As = T 的 s。
      • 将长向量 s 分割成多个子向量，并对每个子向量进行承诺。
      • 验证者发送随机挑战矩阵 C，证明者响应 Z = S * C。
      • 验证者检查 norm(Z) 是否小，以及 A * Z = T * C。
      • 挑战矩阵 C 的必要性： 单个挑战向量 c 存在证明者作弊的风险（50% 成功率），使用多列的挑战矩阵 C 可以强制证明者正确响应，确保健全性。
    • “左右技术”实现范数紧密证明：
      • 初步证明只能保证 s 的范数“不太大”，但无法证明其满足特定的紧密范数（例如，s 是二元的）。
      • 左乘操作： 验证者发送随机整数 lambda。证明者计算 U+ 和 U-，它们是 s 的行向量与 lambda 幂次的加权和。
      • 范数提取： U+ 和 U- 的内积会揭示 s 的平方范数 Beta，以及一个关于 lambda 的多项式。
      • 多项式恒等引理： 通过检查 U+ * U- = Beta + sum(lambda^i * g_i)，利用多项式在随机点处求值来确保 Beta 是正确的平方范数。
      • 模 q 环绕问题： 由于所有计算都在模 q 下进行，Beta 可能是 Beta + Kq。
        • 解决方案： 确保 s 的系数足够小，使得其范数不会超过 q。
        • 更优方案（随机投影）： 引入随机投影矩阵 R，通过证明 R * s = t 来获得 s 范数更紧密的近似（例如，在 2-4 倍因子内）。

  3. 多项式环上的效率提升：

    • 多项式环 Rq = Zq[x] / (x^d + 1)： 将整数运算扩展到多项式环，其中 d 是 2 的幂次。
    • Module SIS： 在多项式环上定义的 SIS 问题。
    • 效率优势：
      • 挑战 C： C 可以是小多项式向量，提供更高的熵，减少挑战矩阵的维度，从而提高效率。
      • 乘法效率： 多项式乘法可以使用数论变换（NTT）或快速傅里叶变换（FFT）进行优化，将复杂度从 n^2 降低到 n log n。
      • 范数提取： 通过巧妙地构造 s(x) 与其自同构 phi(s(x)) 的乘积，可以将范数精确地提取为结果多项式的常数项。
      • 结构匹配： 格基方案本身通常在多项式环上操作，使得证明系统与底层方案结构一致，避免了额外的转换开销。