我们来了解一下拉布拉多协议

作者：Ashutosh Marwah ( ash@ingonyma.com)

Labrador [1] 是第一个基于格的实用 zkSNARK。该协议生成大约 50 kB 的紧凑证明，适用于各种实际相关的 R1CS 大小。它已成为格密码学中的一个重要工具，已经在后量子签名聚合 [3] 等任务中得到应用。它也是 Greyhound [2] 的基础，Greyhound 是迄今为止最实用的基于格的多项式承诺方案。

本博客从头开始探索 Labrador 的构造，从一个简单的 baby 协议开始，逐步构建到完整的递归 Labrador 协议。

安全性

在我们深入研究格密码学之前，重要的是我们要了解如何在环 Zq 上为向量定义范数。对于

v→=(v1,⋯,vn)∈Zqn，我们将 v→ 的 2-范数定义为：

‖v→‖=(∑i=1n|vi|2)1/2

其中我们假设每个 vi∈(−⌈q/2⌉,⌈q/2⌉]。上面的 RHS 中的操作是在将 vi 视为实数时执行的。类似地，我们可以将无穷范数定义为：

‖v→‖∞=max1≤i≤n|vi|。

Labrador 协议的安全性依赖于模块短整数解 (MSIS) 假设，该假设建立在短整数解 (SIS) 假设之上。SIS 假设指出，对于多项式时间（可能是量子）的攻击者来说，找到方程 As→=0 使得 ‖s→‖≤β 对于某个小 β（相对于 q）的解在计算上是困难的，其中 A 是 Zqm×n 中的一个随机矩阵。

模块 SIS 将这个问题推广到多项式环。MSIS 不是使用 Zq 矩阵，而是在环 Rq:=Zq[X]/(Xd+1) 上运行，其中矩阵条目是 d 次多项式。该假设指出，对于适当选择的参数 (m,n,β)，找到短解 s→∈Rqn 到 As→=0 使得 ‖s→‖≤β 在计算上仍然是困难的，其中 A∈Rqm×n。这里，n 长度多项式向量 s→ 的范数是通过将其视为 nd 长度的 Zq 元素的向量来计算的。

这个假设可以用来构建格密码学中最核心的工具之一，也是 Labrador 协议的核心工具——Ajtai 承诺。假设 MSIS 对于参数 (m,n,β) 来说是困难的，那么对于范数最多为 β/2 的向量 s→∈Rqn，t:=As→ 充当绑定承诺。如果一个多项式算法能够找到两个向量 s→1≠s→2，使得它们都产生承诺 t，那么它也能够解决 MSIS，因为

A(s→1−s→2)=As→1−As→2=t−t=0

且

s→1−s→2≠0 且

‖s→1−s→2‖≤β。

虽然，我们在上面使用了 2-范数来定义 MSIS 问题，但是当使用无穷范数来测量范数时，对于较大的参数范围来说，它也是困难的。

Labrador 约束系统

Labrador 的witness被假定为 (s→i)i=1r 的形式，其中每个 s→i∈Rqn (一个 n 长度的 d 次多项式的向量)。Labrador 中有两种约束：相等约束和 const-zero 约束。一个相等约束由多项式 {aij:1≤i,j≤r}⊆Rq、多项式向量 {φ→i:1≤i≤r}⊆Rqn 和多项式 b∈Rq 组成。如果以下公式成立，则witness满足此约束

∑i,j=1raij⟨s→i,s→j⟩+∑i=1r⟨φ→i,s→i⟩+b=0.

这里，两个多项式向量之间的内积就是代数函数：

⟨p→,q→⟩=∑i=1npi(X)qi(X).

类似地，一个 const-zero 约束由多项式 {aij:1≤i,j≤r}⊆Rq、多项式向量 {φ→i:1≤i≤r}⊆Rqn 和环元素 b∈Zq 组成。如果以下公式成立，则witness满足此约束

const(∑i,j=1raij⟨s→i,s→j⟩+∑i=1r⟨φ→i,s→i⟩+b)=0.

上面的 const 函数提取多项式的常数项。

Labrador 协议允许 Prover 表明它持有一个满足多个相等和 const-zero 约束的witness，并且还具有较小的范数，特别是 ∑i=1r‖s→i‖2≤β2，其中 β 是给定的。

Labrador 论文 [1] 的第 6 节表明，可以将二元和 Z2d+1 R1CS 约束简化为上述形式的约束。我们不会在这里详细介绍。为了便于理解，上述约束是二次方的这一事实允许足够的通用性来描述 R1CS 约束。此外，R1CS 中witness的二元性质允许 Labrador 具有小范数的witness。

高级思路

Labrador 协议是递归工作的。可以将其分为两部分：基础协议和递归重塑。基础协议允许 Prover 证明witness {s→i:1≤i≤r}⊆Rqn 对于一组相等和 const-zero 约束的知识（这些可以被视为协议的“电路”）。如果 (s→i)i=1r 的总witness大小为 N=nr 个多项式，那么基础协议会创建一个大小为 O(N2/3) 的证明，单凭这一点并不是特别小。这就是递归发挥作用的地方。证明所满足的关系（相当于基础证明的 Verifier 操作）再次是线性约束和二次约束，因此可以使用上面的相等约束来表示。然后，可以将证明视为另一组相等约束的witness，并对适当的约束重新应用 Labrador 协议。如果适当地重塑witness并构造相应的问题，那么遵循此递归的证明大小为 O(|P|2/3)，其中 |P| 是基础协议结束时证明的大小。因此，经过一次递归迭代，证明大小变为 O(N4/9)。每次迭代都会迅速减小证明大小。只需 O(log⁡log⁡N) 次迭代，证明就会变为常数 O(1) 大小。对于实践中相关的 R1CS 大小，只需要递归协议约 7 次即可实现约 50 kB 的证明。

这里也值得注意的是，Verifier 在这个协议中需要做线性工作。这是该协议的主要缺点之一。

Baby Labrador

我们将从一个简单的协议开始，这个协议是 Labrador 的核心。这将使 Prover 能够聚合和证明约束。然后，我们将修改和改进它以启用递归。

假设 Prover 想要证明他持有一个witness {s→i:1≤i≤r}⊆Rqn（通常，你可以选择 n=N2/3 和 r=N1/3，其中 N 是总witness大小），该witness满足 K 个相等约束：

∑i,j=1raij(k)⟨s→i,s→j⟩+∑i=1r⟨φ→i(k),s→i⟩+b(k)=0

对于每个 1≤k≤K，以及 L 个 const-zero 约束：

const(∑i,j=1raij(l)⟨s→i,s→j⟩+∑i=1r⟨φ→i(l),s→i⟩+b(l))=0

对于每个 1≤l≤L，并且还满足范数约束：

∑i=1r‖s→i‖2≤β2。

所有约束的 aij、φi 和 b 项都是公共参数，特别是 Verifier 持有的。直接对它们进行操作是导致 Verifier 线性时间的原因。

Prover 和 Verifier 执行以下交互过程来证明这一点：

1. Ajtai 承诺到witness：

对于每个 1≤i≤r，Prover 将 t→i=As→i 发送给 Verifier，其中 A 是一个 κ×n 矩阵，其元素位于多项式环 Rq 中。对于这个简化的基础协议，我们将只使用这些承诺的同态性质。稍后，我们将看到 Ajtai 承诺是线性的这一事实可以用来将递归实例的约束写成相等约束。

请注意，此步骤中 Prover 消息的大小为 κr。κ 可以选择为一个常数，因此这些消息将是次线性的。

2. Const-zero 约束聚合：

   1. Verifier 将 L 个随机挑战 (ψl)l=1L∈rZq 发送给 Prover。
   2. Prover 通过对它们进行随机线性组合，将 L 个 const-zero 约束聚合为一个 const-zero 约束：

   const[∑l=1Lψl(∑i,j=1raij(l)⟨s→i,s→j⟩+∑i=1r⟨φ→i(l),s→i⟩+b(l))]=0

   因此，由

   aijagg:=∑l=1Lψlaij(l)φ→iagg:=∑l=1Lψlφ→i(k)bagg:=∑l=1Lψlb(l)

   给出的聚合 const-zero 约束也应该被witness满足：

   const(∑i,j=1raijagg⟨s→i,s→j⟩+∑i=1r⟨φ→iagg,s→i⟩+bagg)=0.

   请注意，Verifier 可以自己计算这个新的聚合约束。

   此时，Prover 和 Verifier 只需丢弃原始的 const-zero 约束。直观地说，如果其中一个约束不满足，那么聚合约束也很可能不满足。

   3. 然后，Prover 将其转换为相等约束，只需发送多项式：

   Bagg=−∑i,j=1raijagg⟨s→i,s→j⟩−∑i=1r⟨φ→iagg,s→i⟩。

   4. Verifier 检查这个多项式的常数项是否正确 (等于 bagg)。这就是为什么随机挑战是从 Zq 而不是 Rq 中选择的原因。

   5. 然后，Prover 和 Verifier 都将相等约束

   ∑i,j=1raijagg⟨s→i,s→j⟩+∑i=1r⟨φ→iagg,s→i⟩+Bagg=0。

   添加到他们的相等约束列表中。他们还进一步丢弃新构造的聚合 const-zero 约束。

   为了确保安全性，值得注意的是，添加约束只会使prover更难以作弊。此外，由于 Verifier 检查 Bagg 的常数项是否计算正确，我们保证聚合的 const-zero 约束已得到满足。

虽然在上面，我们将所有的 const-zero 约束聚合为一个相等约束，但为了确保安全性，需要重复上述步骤少量次数。但是，为了简单起见，我们不在这里这样做。

3. 相等约束聚合

现在我们只剩下相等约束了。我们将把所有这些聚合为一个相等约束。令 K′ 为相等约束的数量（K′=K+1，因为我们在上面添加了一个约束）。

1. Verifier 随机采样挑战多项式 (αk)k=1K′∈rRq 并将其发送给 Prover。

2. Prover 和 Verifier 通过形成现有约束的随机线性组合来聚合相等约束。如果约束是 1≤k≤K′:

   ∑i,j=1raij(k)⟨s→i,s→j⟩+∑i=1r⟨φ→i(k),s→i⟩+b(k)=0

   那么（最终）聚合的相等约束由下式给出：

   aij(fin):=∑k=1K′αkaij(k)φ→i(fin):=∑k=1K′αkφ→i(k)b(fin):=∑l=1Lαkb(l)

   并且witness应该满足以下条件：

   ∑i,j=1raij(fin)⟨s→i,s→j⟩+∑i=1r⟨φ→i(fin),s→i⟩+b(fin)=0。

与前面的步骤类似，很容易论证，如果witness不满足任何相等约束，那么它也不会满足这个约束。

因此，现在 Prover 只需要证明他的witness满足这个最终的相等约束。

4. 发送“垃圾”多项式

   1. 对于 1≤i,j≤r，Prover 将多项式：

   gij:=⟨s→i,s→j⟩hij:=⟨φ→i(fin),s→j⟩

   发送给 Verifier。

   2. Verifier 检查

   ∑i,j=1raij(fin)gij+∑i=1rhii+b(fin)=0.

现在，观察到 Prover 只需要证明 gij 和 hij 是诚实计算的。如果他能证明，那么他就证明了witness满足约束。

另外，请注意，Prover 在这一轮中发送了 2r2 个多项式。通过观察到 gij=gji 并对称化 hij，可以将其减少大约一半，以便它也满足类似的方程。但是，我们在此处忽略这些优化。

5. 摊销打开

Verifier 将挑战多项式 (ci)i=1r 发送给 Prover，并要求 Prover 在 Ajtai 矩阵 A 下打开承诺 ∑i=1rcit→i。Prover 始终可以使用多项式向量 ∑i=1rcis→i 打开它。但是，如果挑战多项式太大，不诚实的 Prover 也将能够打开对其他向量的承诺，因为 Ajtai 承诺只有在输入具有小范数时才具有约束力。因此，Verifier 需要从 C⊆Rq 的一个特殊子集中采样挑战。这个子集是专门选择的，以便：

1. |C| 是指数级的 (∼2128)。

2. 对于任何多项式 c∈C 和任何多项式 r∈Rq，我们有

   ‖c⋅r‖≤T‖r‖

   对于一些小的 T∈R+ (Labrador 为 15)

这种挑战空间经常出现在格密码学中（例如，在 Dilithium 中），因为它有必要确保使用挑战组合的向量保持其小范数。在 Labrador 中，挑战空间 C 由具有 23 个零系数、31 个 ±1 系数和 10 个 ±2 系数的多项式组成。还需要进一步使用拒绝采样来确保在从此集合中采样时满足算子范数条件（条件 2）之上。

最后，我们让 Prover 和 Verifier 执行以下步骤：

1. Verifier 从挑战空间 C 中随机采样 (ci)i=1r 并将其发送给 Prover。
2. Prover 以 z→=∑i=1rcis→i 作为响应。

3. Verifier 检查

   ‖z‖≤Tβr=:γ

   并且以下方程是否满足：

   Az→=∑i=1rciti⟨z→,z→⟩=∑i,j=1rgijcicj∑i=1rci⟨φ→i(fin),z→⟩=∑i,j=1rhijcicj

粗略地说，z→ 上的范数界限以及它打开到 ∑i=1rciti 的承诺这一事实意味着 z→ 是由 Prover 诚实产生的。其余的两个方程保证了多项式 gij 和 hij 是诚实产生的。通过在这些方程中插入诚实的 z→，很容易检查出 LHS 上 cicj 的系数是 gij 的诚实值和 hij 的诚实值。由于 ci 是在一个大的空间中随机选择的，如果 Prover 没有提供正确的 gij 或 hij，那么其中一个方程会以很高的概率失败。

上面陈述的协议可以被形式化，并用于提供一个亚线性大小的证明，证明 Prover 持有一个有效的witness。观察到 Prover 的证明由承诺 {ti:1≤i≤r}、垃圾多项式 {gij,hij:1≤i,j≤r} 和多项式向量 z→ 组成。Verifier 检查这些证明元素的步骤 5.3 中的条件。不难看出，这些验证条件（只有二次和线性约束；ci 可以是约束定义的一部分，因为 Verifier 已经知道它们了）可以被重新定义为相等约束，其中witness是上述证明元素。这几乎是 Labrador 所做的，除了，我们现在无法有效地递归协议，因为在上述协议中从 z→ 中提取一个有效的witness所需的范数松弛太大（类似于 ‖(s→i)i=1r‖ 的 O(Tβr)）。为了规避这个问题，在 Labrador 中，Verifier 使用一个称为“JL 投影”的随机投影来估计witness的范数。他通过向 const-zero 约束集添加一些线性约束来确保 Prover 诚实地计算这个投影。最后，我们还需要确保每个递归轮次的通信量都很小。为此，Prover 将只对每轮中的 (ti,gij,hij) 进行 Ajtai 承诺。

Labrador 基础协议

我们现在准备好描述 Labrador 中使用的基础协议。在这个协议结束时产生的证明可以作为证明发送给 Verifier，也可以用作下一个递归轮次的witness。与上面的协议类似，假设 Prover 希望证明他持有一个witness {s→i:1≤i≤r}⊆Rqn，该witness满足 K 个相等约束：

∑i,j=1raij(k)⟨s→i,s→j⟩+∑i=1r⟨φ→i(k),s→i⟩+b(k)=0

对于每个 1≤k≤K，以及 L 个 const-zero 约束：

const(∑i,j=1raij(l)⟨s→i,s→j⟩+∑i=1r⟨φ→i(l),s→i⟩+b(l))=0

对于每个 1≤l≤L，并且还满足范数约束：

∑i=1r‖s→i‖2≤β2。

为此，Prover 和 Verifier 执行以下步骤：

1. Ajtai 承诺到witness: 与上面的 Baby Labrador 协议相同，Prover 计算 s→i 的承诺为 t→i=As→i。但是，正如我们在上面指出的，我们希望避免将所有这些 t→i 发送给 Verifier。因此，Prover 发送一个对这些 (t→i)i=1r 的承诺。请注意，向量 t→i 不需要像 Ajtai 承诺的绑定属性所要求的那样具有小范数。因此，我们需要首先分解**每个 t→i。分解操作采用基数 b 和一个多项式向量 p→，并返回 (p→(0),p→(1),⋯,p→(l−1)) 使得

p→=∑i=0l−1bip→(i)

并且 ‖p→(i)‖∞≤b/2（类似于一个基数 b 分解）。我们将把这个操作的逆操作称为重组操作，该操作组合 (p→(0),p→(1),⋯,p→(l−1)) 以产生 p→。请注意，重组操作是线性的。

假设

t′→:=decompose((t→i)i=1r,base=b1)。

那么，‖t′→‖∞≤b1/2。这个范数界足以确保 Ajtai 承诺的绑定。因此，Prover 将承诺 u→1=Bt′→ 发送给 Verifier。请注意，u→1 具有小的常数大小。

2. JL 投影：

在这一步中，Verifier 使用 Johnson-Lindenstrauss (JL) 引理来确保 Prover 的witness具有小范数。JL 引理大致指出，对于一个向量 v→∈Zm 和一个随机矩阵 Π，该矩阵的维度为 256×m，其元素随机地从 {−1,0,1} 中选择，概率为 P(1)=P(−1)=1/4 和 P(0)=1/2，固定大小的向量 Πv 的范数集中在 ‖v‖ 附近。具体来说，

Pr[‖Πv‖≤30‖v‖]≤negl。

矩阵 Π 通常被称为“JL 投影”。我们在此简要地指出，这个术语用词不当。一般来说，这个矩阵不是线性代数意义上的投影。

以下是 Prover 和 Verifier 使用这个引理的方法：

1. Verifier 随机抽取一个 256×rnd JL 投影 Π 并将其发送给 Prover。

2. 令 v→∈Zqrnd 为扁平化的witness (s→i)i=1r。Prover 以 p→=Πv→ 作为响应。

3. Verifier 检查 p→ 的范数是否小：‖p→‖≤128β。

   如果 Prover 诚实地计算了 p→ 并且这个检查通过了，那么 Verifier 可以保证整个witness的范数小于 ≈2β。与上述 Baby 协议中的 O(Tβr) 相比，这是一个显著的改进。选择界限 128β 是为了给一个诚实的 p→ 通过这个测试提供充分的概率（Prover 和 Verifier 需要重复多次 Π 直到这个测试成功）。

4. 现在，我们必须确保 Prover 是否正确计算了 p→。为此，Prover 和 Verifier 都向witness满足的约束添加一些约束。简而言之，Prover 声称witness满足 Zq 方程：

   Π⋅ flatten(s→1,s→2,⋯,s→r)=p→.

   这些只是witness上的 256 个线性约束，它们可以表示为 256 个 const-zero 约束（每一行一个），其中 aij=0，φ→i 由 Π 的行元素组成，并且 b=−p→k。我们将这些约束的确切形式推迟到论文中。

协议的其余部分几乎与上面的 Baby 协议相同。

3. Const-zero 约束聚合：

Prover 和 Verifier 将 const-zero 约束聚合为相等约束，这与上面的 Baby 协议完全相同。

4. 相等约束聚合：

他们还将相等约束聚合为以下形式的单个约束：

∑i,j=1raij(fin)⟨s→i,s→j⟩+∑i=1r⟨φ→i(fin),s→i⟩+b(fin)=0

遵循 Baby 协议中的过程。

5. 发送“垃圾”多项式：

如前所述，对于 Labrador 的递归轮次，Prover 不会发送垃圾多项式。相反，他使用 Ajtai 承诺对它们进行承诺。再次，gij 和 hij 的范数可能很大，因此必须使用合适的基数（例如 b2 和 b3）对它们进行分解。假设这些的分解版本存储在 g′→ 和 h′→ 中。然后，Prover 将这些向量承诺为：

u→2:=Cg′→+Dh′→

其中 C 和 D 是一些随机公共矩阵。

由于 Verifier 没有纯文本的 gij 和 hij，他会推迟最终约束验证。

6. “摊销打开”：

与 Baby 协议类似，Verifier 将来自 C 的挑战多项式 (ci)i=1r发送给 Prover。但是，现在 Prover 不像以前那样发送 z→。他也不需要承诺到 z→，因为 Verifier 已经知道 Az→=∑i=1rcit→i。因此，从这个意义上讲，还没有“打开”。

递归

在上面的基础协议末尾，Prover 声称知道 (t′→,g′→,h′→,z→)，使得以下公式成立：

1. 范数条件

‖z→‖≤γ,‖t′→‖∞≤b1/2,‖g′→‖∞≤b2/2‖z→‖∞≤b3/2,

2. 我们可以重组并恢复：

{t→i:1≤i≤r}←recompose(t′→,base=b1){gij:1≤i,j≤r}←recompose(g′→,base=b2){hij:1≤i,j≤r}←recompose(h′→,base=b3)

满足承诺等式：

u→1=Bt′→u→2=Cg′→+Dh′→Az→=∑i=1rciti

和约束条件：

∑i=1rci⟨φ→i,z→⟩=∑i,j=1rhijcicj∑i,j=1raij(fin)gij+∑i=1rhii+b(fin)=0.⟨z→,z→⟩=∑i,j=1rgijcicj

我们上面的论证保证了证明 (t′→,g′→,h′→,z→) 的知识对于 Prover 来说是充分的。如果这些向量的大小足够小，Prover 可以直接将它们发送给 Verifier。这是递归的基本情况。

另一方面，观察到上述约束可以放入相等约束的形式。除了最后一个约束外，所有约束都是线性约束，最后一个约束也只是一个二次约束（重组操作是线性的，并且约束可以直接根据 t′→,g′→,h′→ 进行重写）。此外，可以证明这些约束 (t′→,g′→,h′→,z→) 的witness具有小的 2-范数（例如，通过使用对于维度 m 的向量 v→, ‖v→‖≤m‖v→‖∞）。因此，可以将验证 Labrador 基础证明的问题重写为原始问题的一个实例，并递归该协议。

更详细地说，将基础证明 (t′→,g′→,h′→,z→) 展平为一个多项式数组，然后将其重塑为witness {s→i′:1≤i≤r′}，其中每个 s→i′∈Rqn′。仔细选择参数 r′ 和 n′ 以最大限度地减少每次迭代中的证明大小（通常 n′=Θ(r′2)）。上面的每个约束都根据 s→i′ 进行了重写，并存储了相应的相等约束。我们注意到，Verifier 可以在没有任何 Prover 帮助的情况下执行此操作。在这种重新排列之后，Prover 和 Verifier 可以再次执行基础协议的迭代。

使用 ICICLE v4 实现

ICICLE v4 引入了对常见格原语的支持。我们使用这些原语以与后端无关的方式（可以在 CPU 和 GPU 上运行）创建一个简单且高度可读的 Labrador 协议的 C++ 实现（在这里查看）。

在我们的 Labrador 实现中，我们选择 q=pKBpBB，其中 pKB 是 Koala bear 素数，而 pBB 是 Baby bear 素数。因此，我们把 q 称为 Baby Koala 环。选择这些素数来定义 q 确保了高效的算术和 negacyclic NTT（数论变换）。这个环在代码中由类型 Zq 表示。类似地，我们使用类型 Rq 表示多项式环 Rq，使用 Tq 表示 NTT 域中表示的相同多项式环。

让我们看一下上面提到的一些主要操作的 C++ API。

1. 分解：以下代码分解了 C++ 代码中的向量 (ti)i=1r

​​​​ // computes number of digits required to decompose Zq element with base1
​​​​ size_t l1 = balanced_decomposition::compute_nof_digits<Zq>(base1);
​​​​ std::vector<Rq> T_tilde(l1 * r * kappa);
​​​​ balanced_decomposition::decompose(
​​​​     T.data(),       // input
​​​​     r * kappa,      // input size
​​​​     base1,          // base
​​​​     {},             // default config
​​​​     T_tilde.data(), // output
​​​​     T_tilde.size()  // output size
​​​​     );

我们在此注意到，如果用户知道分解所需的输出大小小于 compute_nof_digits 指定的大小，他们可以使用它作为输出大小。遵循与上面相同的 API 的 balanced_decomposition::recompose 函数可用于断言情况是否如此。

2. Ajtai 承诺：以下代码使用矩阵 B 计算 t\~ 的 Ajtai 承诺。在计算多项式矩阵乘积之前，我们需要将 t\~ 转换为 NTT 域。假设 B 矩阵以 NTT 形式存储。

​​​​// T_tilde_hat = NTT(T_tilde)
​​​​ntt(
​​​​    T_tilde.data(),     // 输入
​​​​    T_tilde.size(),     // 输入大小
​​​​    NTTDir::kForward,   // NTT 方向
​​​​    {},                 // 默认配置
​​​​    T_tilde_hat.data()  // 输出
​​​​);
​​​​// 计算 u1 = T_tilde_hat @ B
​​​​matmul(
​​​​    T_tilde_hat.data(), // A
​​​​    1,                  // A_nof_rows
​​​​    T_tilde_hat.size(), // A_nof_cols
​​​​    B.data(),           // B
​​​​    T_tilde_hat.size(), // B_nof_rows
​​​​    kappa1,             // B_nof_cols
​​​​    {},                 // 默认配置
​​​​    u1.data()           // 输出
​​​​    );

3. JL 投影：JL 投影在 Labrador 协议中以两种方式使用。首先，向证明者提供一个种子，并要求计算从该种子计算出的 JL 投影与一个向量的乘积。以下是代码中的样子：

​​​​// p = Pi*flatten(S)
​​​​labrador::jl_projection(
​​​​  reinterpret_cast<const Zq*>(
​​​​  S.data()),        // 输入
​​​​  n * r * d,        // 输入大小
​​​​  jl_seed.data(),   // 种子*
​​​​  jl_seed.size(),   // 种子长度
​​​​  {},               // 默认配置
​​​​  p.data(),         // 输出
​​​​  JL_out            // 输出大小
​​​​);

其次，我们还需要能够提取 JL 矩阵的行。ICICLE 也有一个用于此目的的 API。此外，此 API 还允许你共轭和提取行，因为 Labrador 需要它们。

​​​​// 获取 JL 矩阵的第 j 行的共轭
​​​​labrador::get_jl_matrix_rows(
​​​​    jl_seed.data(), // 种子*
​​​​    jl_seed.size(), // 种子长度
​​​​    r * n,          // 行大小
​​​​    j,              // 行索引
​​​​    1,              // 行数
​​​​    true,           // 共轭
​​​​    {},             // 默认配置
​​​​    Q_j.data());    // 输出

4. 范数界限：ICICLE 还提供 API 来检查 Zq 向量的 2-范数和无穷范数是否被某个固定界限所约束：

​​​​// JL_check = || p || < sqrt(JL_out / 2) * beta
​​​​norm::check_norm_bound(
​​​​    p.data(),                           // 输入
​​​​    JL_out,                             // 输入大小
​​​​    eNormType::L2,                      // 范数类型 L2 或 LInfinity
​​​​    uint64_t(sqrt(JL_out / 2) * beta),  // 范数界限
​​​​    {},                                 // 默认配置
​​​​    &JL_check                           // 存储结果
​​​​    )

5. 挑战空间采样：最后，ICICLE 提供了一个 API 来有效地采样类似 Labrador 的挑战空间多项式。

​​​​sample_challenge_space_polynomials(
​​​​    seed,               // 种子
​​​​    seed_len,           // 种子长度
​​​​    r,                  // 要采样的多项式数量
​​​​    31,                 // ±1 的数量
​​​​    10,                 // ±2 的数量
​​​​    OP_NORM_BOUND,      // 算子范数界限
​​​​    {},                 // 默认配置
​​​​    challenge.data()    // 输出
​​​​    );

为了提高效率，算子范数检查与采样融合在一起。对于不需要算子范数界限的协议，可以简单地将上面的范数界限设置为 0。

有关 Rust 中 ICICLE API 的概述，请查看我们的文档这里。

参考文献

[1] Beullens, W., Seiler, G. (2023). LaBRADOR: Compact Proofs for R1CS from Module-SIS. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14085. Springer, Cham. https://doi.org/10.1007/978-3-031-38554-4_17

[2] Ngoc Khanh Nguyen and Gregor Seiler. 2024. Greyhound: Fast Polynomial Commitments from Lattices. In Advances in Cryptology – CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2024, Proceedings, Part X. Springer-Verlag, Berlin, Heidelberg, 243–275. https://doi.org/10.1007/978-3-031-68403-6_8

[3] Marius A. Aardal and Diego F. Aranha and Katharina Boudgoust and Sebastian Kolby and Akira Takahashi. Aggregating Falcon Signatures with LaBRADOR (2024)

https://eprint.iacr.org/2024/311

• 原文链接： hackmd.io/@Ingonyama/fas...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～