格折叠方案：按位付费与 NTT

原文：https://blog.icme.io/folding-schemes-in-the-lattice-setting-pay-per-bit-and-ntts/

作者： Alberto Centelles

译者：Kurt Pan

格密码学使我们可以以格困难问题为基础构建密码原语。LatticeFold[1] 是首个基于格的折叠方案协议，灵感源自 HyperNova[2]，其安全性基于 Module Short Integer Solution (MSIS) 问题。简言之，它用 Ajtai 承诺（更确切地说，用 Lyubashevsky 等人提出的基于模的 Ajtai 承诺版本[4]）替代了现有的基于离散对数的承诺方案，如 KZG[3]。Ajtai 承诺要求被承诺的元素具有小范数。相比其基于离散对数的对应方案，这一步——必须证明见证向量具有小范数——在格基零知识证明中成为了一项主要的复杂性来源。如预期一样，格基折叠方案的主要挑战在于折叠后如何管理范数增长。

可以说，LatticeFold 的一个主要缺点是，在将给定实例（例如Customisable Constraint System (CCS)[5]）中的域元素嵌入到 Ajtai 承诺方案所需的多项式环时需要使用数论变换 (NTTs)。Neo[6] 是近期受 LatticeFold 启发的新折叠方案，它通过不同的编码避免了运行 NTTs，并实现了所谓的 “按位付费”承诺方案 ，即对一个元素的承诺成本与其比特数成线性关系。由于大多数情况下被承诺的元素都很小，这种“按位付费”特性非常理想。

因此，本文旨在探讨以下相关问题：

• LatticeFold 在其域到多项式环嵌入中采取了何种方法？

• Neo 如何在保持同态性的同时，避免 NTTs 并实现其“按位付费”承诺方案？

注意：本文仅聚焦于 LatticeFold 与 Neo 在域到多项式环编码上的差异。实际上，这些方案还有更多内容值得探讨，包括添加零知识特性或压缩证明大小等开放问题，我希望在近期予以覆盖。我也未提及最新的折叠方案 LatticeFold+[7]，该方案无需针对分解向量计算大量承诺，并优化了 LatticeFold 中用于范数边界检查的昂贵大乘积操作。此外值得一提的是，Neo 的域编码方法与 LatticeFold+ 的新范围证明完全兼容，可进一步提升 LatticeFold+ 的效率。

背景

在深入讨论 LatticeFold 和 Neo 的不同嵌入及其权衡之前，我将简要概述所使用的主要原语。分圆多项式环是 Ajtai 承诺运作的基础代数结构，而 NTT（数论变换）是将有限域元素（例如来自 CCS 关系）嵌入到分圆多项式环的手段之一。我希望使本背景部分尽可能具备上下文关联性。

分圆多项式

第  个分圆多项式是唯一的首一（monic）不可约多项式，它能够整除 ，但不能整除任何 （其中 ）。如果它不是首一的，就无法保证其唯一性。值得注意的是，该多项式的根是第  个本原（primitive）单位根，即那些满足  且对于所有  有  的  中的元素。

第  个本原单位根的个数由欧拉函数  决定， 给出了范围  中与  互素（）的整数  的数量。例如，当  为素数时，，此时第  个分圆多项式为 。当  是  的幂时，即 ，有 ，此时第  个分圆多项式为 。后者示例正是 LatticeFold 所使用的分圆多项式，也限制了 LatticeFold 的可实例化域。Neo 则没有此类限制。

分圆环

基于格的协议建立在一些著名的计算格问题之上，例如定义在多项式环  上的 Module-SIS（MSIS）。

如前所述，如果  是  的幂，则  亦是  的幂，且  为对应的第  个分圆多项式。环

称为分圆 环。该环由满足  的形如

的多项式构成。

LatticeFold 将  设为满足

的素数，其中  是  的因子，即  亦为  的幂，此时  包含  个本原  次单位根。因

且 ，故  包含所有  次本原单位根 ；又因 ，对所有 ， 在  中不可约。可验证若 ，则 ，从而 。因此

由于当  时  与  均不可约且互素，可应用中国剩余定理，将

分解为  个商环的直积：

其中  是由  给出的扩域。

LatticeFold 进一步简化论述，取 （即 ）。此时  中存在  个  次本原单位根，且

需要注意的是，这一对  的限制，使得 LatticeFold 不适用于某些有限域（如 Goldilocks 或 Mersenne61）。LatticeFold 的第 3.3 节描述了一种支持更广模数类的修改方法，即对任意满足  ，  的情况。

数论变换 (NTTs)

对于  为  的幂时，设

NTT 即将  在上述  个  次本原单位根  处进行求值：

等价地，

其中 。即对所有 ，有 。若

则

且 。当  且  时，不可约因子则为次数  的多项式。

Module-SIS 与 Ajtai 的承诺

给定矩阵 ，Module-SIS 问题是寻找范数小的向量 （即 ）使得

SIS 问题等价于求解线性方程组，其中矩阵  提供系数，向量  为未知量，而额外的“小范数”约束对问题的困难性至关重要，否则可通过高斯消元法轻易求解。

在 Ajtai 承诺方案中，使用随机性 （用于隐藏）对消息  进行承诺，其中两者的范数  都保持较小，并满足

LatticeFold

将  嵌入到 

我们假设  且

环  中的一个元素定义为

其中 。

LatticeFold 将在  上的 CCS 关系中的  个实例-见证对打包为单个在  上的实例-见证对。对于 ，有两种解释方式：

1. 作为某个  的系数嵌入
2. 作为某个  的 NTT 表示

在 LatticeFold 中，每个  中的条目  被设定使得 ，其中 。换言之， 是一个多项式，其在  次本原单位根上的  个求值值为 。

有人可能会问，为什么不将  直接作为  的系数嵌入？换言之，给定在  上的 CCS 关系，为什么 LatticeFold 要以 NTT 形式将  元素嵌入 ？

为说明起见，取一个 R1CS 关系（R1CS 是 CCS 的子集）：

其中 ，并令 。则满足以下方程：

如果我们将它们作为  元素的系数来打包，即

这并不能保证 。的确，

为了使 CCS 关系成立，我们需要运行逆 NTT（iNTT），使得

这样，当  在本原单位根  处求值时，会得到：

需要注意的是，如果  的范数较小（即 ），这并不保证 。也就是说，iNTT 并不保范数。因此，LatticeFold 需要独立于其原始大小对任意元素进行承诺。

另一方面，NTT 的一个优势是可以将在  上的  个独立关系批量打包为在  上的单个关系。

假设我们有  个 R1CS 关系

我们可以使用 NTT 将它们打包成单个在  上的 R1CS 关系：

其中

LatticeFold 的承诺方案

综合上述，（简化的）LatticeFold 的承诺关系定义为：

该关系用于证明 Ajtai 承诺的正确打开。在 CCS 上下文中，可以将  中的每个元素视为对原始 CCS 关系中  子集执行 iNTT 后得到的。完整的 CCS 关系见定义 4.2。

在  中， 是  中的多项式向量。其每个元素的 NTT 形式即  中元素的系数，也即

零检验  作为大乘积论证编码了 Ajtai 承诺所需的范数上界 。LatticeFold 使用  而非  来进行此大乘积论证，是为了对  应用 sum-check 协议，将关系  归约到另一个关系 ，

并简单地检验

Neo

将  嵌入到 

考虑到在 CCS 关系的元素上运行 iNTT 以执行 LatticeFold 协议的缺点，Neo 对以下问题给出了答案：

我们如何将  嵌入到一个低范数向量  中，使得  可以直接使用 Ajtai 的承诺方案进行承诺，并保持同态性？

Neo 通过将每个元素  的  进制分解嵌入到系数中来映射到环元素 ：

此嵌入保证 ，即具有低范数。与 LatticeFold 中使用的嵌入不同， 保留了原始 CCS 约束。注意，如果所有  都很小，则可以将多个  元素嵌入到同一个 。

为说明起见，取一个 R1CS 关系

其中 ，共有  个约束。每个约束形如 ，其中 。令 。它们的二进制分解为 ，因此它们的嵌入为

由于 ，显然有

因此，嵌入后原始 CCS 约束依然成立。

请注意，此等式仅当  时成立，即在取模  后不存在回绕。

从环到矩阵

Ajtai 的承诺方案描述在  元素上。然而，Neo 的协议用矩阵来描述。本节展示如何将来自  的元素转换回 Neo 中使用的  元素。

系数映射

对于元素

系数映射  定义为

对于向量 ，

分解映射

给定域元素向量 ，Neo 定义  进制分解映射

• 矩阵  具有低范数，即对所有 ，$\|z_{i,j}\|_\infty
• 每一列 可视作  中某环元素  的系数；
• 每一行 可视作  中所有元素的  项系数。

显然 。

由于 Ajtai 的承诺作用在  上，当我们说对矩阵  进行 Ajtai 承诺时，即指操作

其中  为低范数向量，。

旋转矩阵

Neo 实际计算这些承诺的思路来源于观察到旋转矩阵集合

构成一个环，且同构于 。因此，承诺方案可视为 -module 同态映射

满足对任意  及  有

那么，什么是这些旋转矩阵？

定义 移位矩阵 及元素  的 旋转矩阵 如下：

其中  是分圆多项式

的系数。对所有 ，有 。若 ，则 ，其余 。令