Plonk-3-用于识别排列的多项式协议

Posted on Edited on

论文原文 ==> 953.pdf (iacr.org)，PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

5.用于识别排列的多项式协议

​ 从根本上说，我们的通用SNARK是“排列检查”，其灵感来自于Bayer和Groth [[BG12](S. Bayer and J. Groth. Effiffifficient zero-knowledge argument for correctness of a shufflfflffle. In *Advances in Cryptology - EUROCRYPT 2012 - 31st Annual* *International Conference on the Theory and Applications of Cryptographic* *Techniques, Cambridge, UK, April 15-19, 2012. Proceedings*, pages 263–280, 2012.)]及其在[[BCC+16](J.Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Effiffifficient zero knowledge arguments for arithmetic circuits in the discrete log setting. pages 327–357, 2016.)，[MBKM19](M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn. Sonic: Zero-knowledge snarks from linear-size universal and updateable structured ref-erence strings. *IACR Cryptology ePrint Archive*, 2019:99, 2019.)]中的变体所提出的排列参数。同样，与[[MBKM19](M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn. Sonic: Zero-knowledge snarks from linear-size universal and updateable structured ref-erence strings. *IACR Cryptology ePrint Archive*, 2019:99, 2019.)]相比，我们的主要优点是可以通过处理单变量多项式和可乘子组来获得更简单的协议。

​ 维度界限：我们使用两个整数参数n≤d。直观地讲，n是诚实证明者多项式的度，d是我们实际上对恶意证明者强制执行的范围。因此，我们在分析证明者效率并描述“正式”协议输入时假设度数为n。但是在分析稳健性时允许度数为d。

​ 我们假设存在生成器 g 的n阶乘子子集H⊂**F**。

​ 指定 i∈[n]，Li(X) 为**F** <n[X]的一个元素，Li(g)=1且Li(a)=0，其中a∈H 与 g不同，例如，{Li}，其中 i∈[n] 是 H的拉格朗日基础。

​ {Li} 可以”将点检查减少到范围检查“。

断言5.1. 给定i∈[n]和Z，Z*∈**F**[X]。 则针对每一个a∈H，有且只有Z(gi) = Z*(gi)时 Li(a)(Z(a) - Z*(a)) = 0。

​ 给定f，g∈**F**[X]和一个排列 σ：[n]→[n]，写为 g=σ(f)，针对每一个a∈H，g(gi) = f(gσ(i))

​ 我们提出了一个范围多项式协议，使Ppoly能够证明 g=σ(f)。

预处理多项式：多项式为 SID∈*F**[X]，SID由S(gi)=i定义，对于每一个i∈[n]且Sσ∈F*[X]，Sσ(**gi) = σ(i)。

输入：f，g∈**F**<n[X]

协议：

1.Vpoly选择随机数β，γ∈**F**，并发送给到Ppoly。

2.令 f’:=f+β·SID+γ，g’:=g+β·Sσ+γ。则，针对i∈[n]，有
$$
f’(g^i) = f(g^i) + β \cdot i + γ, g’(g^i)=g(g^i) + β \cdot σ(i) + γ
$$
3.Ppoly计算 Z ∈ F <n[X]，且**Z**(g)=1；并且对于 i∈{2,…,n}
$$
Z(g^i)=\sum _{1 \leq j \leq i} f’(g^j)/g’(g^j)
$$
如果某元素未定义，在γ之上会发生的可能性为negl(λ)，协议则中止。

4.Ppoly发送*Z***给到第三方 *I***。

5.Vpoly检验a，其中a∈H。

​ (a) L1(a)(Z(a)-1) = 1

​ (b) Z(a)f’(a) = g’(a)Z(a·g)

如果上述检验OK，则输出acc。

5.1检查“扩展”排列

预处理多项式：多项式为 SID1,…,SIDk∈**F**<n[X]，SIDj由SID(gi)=(j-1)·n + i定义，对于每一个i∈[n]。

输入：f1,…,fk，g1,…,gk∈**F**<n[X]

协议：

1.Vpoly选择随机数β，γ∈**F**，并发送给到Ppoly。

2.令 fj’:=fj+β·SIDj+γ，gj’:=gj+β·Sσj+γ。则，针对j∈[k]，i∈[n]，有
$$
f’ _j (g^i) = f _j (g^i) + β \cdot ((j-1) \cdot n + i) + γ, g_j’(g^i)=g_j(g^i) + β \cdot σ((j-1) \cdot n + i) + γ
$$
3.定义 f’，g‘∈*F*<kn[X]如下：
$$
f’(X) := \prod _{j \isin [k]} f_j’(X),g’(X) := \prod _{j \isin [k]} g_j’(X)
$$
4.**Ppoly计算 *Z*** ∈ F <n[X]，且*Z*(g)=1；并且对于 i∈{2,…,n}
$$
Z(g^i)=\sum _{1 \leq l \leq i} f’(g^j)/g’(g^j)
$$
5.**Ppoly发送*Z*给到第三方 **I。

5.Vpoly检验全部a，其中a∈H。

​ (a) L1(a)(Z(a)-1) = 1

​ (b) Z(a)f’(a) = g’(a)Z(a·g)

如果上述检验OK，则输出acc。