Abstract
Caulk$[ZBK+22]$最近的引入了向量承诺方案的位置隐藏可链接性的安全概念，并提供了一个零知识论证，即承诺向量的元素包括某个其他承诺向量的子集
在子集向量的大小$m$比包含它的子集向量的尺寸$n$小得多的情况下，该协议的Prover开销不是很大，渐近证明复杂度为$O(m^2+m\log n)$，其中$\log n$来自子协议，表明盲多项式的根都是$n$次单位根
本文展示了如何对caulk进行优化，用多项式可分割性检查替换子协议，从而将渐近证明器的复杂性降低至$O(m^2)$
1 Introduction
Caulk给出了两种有效链接到长度为$n$的向量承诺方案，分别对应于$m=1$和$m>1$的情况，主要思路是在一个较小的子群上利用KZG多项式方案进行承诺，并利用配对进行验证
Caulk中，$m=1$时Prover的渐进开销为$O(\log n)$，$m>1$时为$O(m^2+m\log n)$，Caulk通过预计算向量承诺来将Prover Time减少至亚线性阶，揭示承诺需要$O(n)$的时间
1.1 Our Contribution
本文改进了Caulk的方案，将$m>1$情况的Prover渐进开销降低至$O(m^2)$，不再与$n$相关
Caulk中的复杂度$m\log n$的项来自于其子协议，因为在子协议中需要证明承诺多项式在某些点上的揭示为一个$n$次单位根
本文的方法通过优化配对的验证等式来优化Caulk协议，简单来说就是检查求值点可被$X^n-1$整除
这个优化虽然需要Prover为每个向量索引预计算和保存一个额外的witness元素，不过本质上是一个空间换时间的方法，可以进一步降低Prover的开销，不过优化需要解决两个问题
第一个问题在于，Prover需要利用盲因子$r$，构造一个盲多项式$Z(X)=r\prod_{i\in I}(X-\omega^i)$，同时证明存在某个多项式$H(X)$，满足$Z(X)\cdot H(X)=X^n-1$，问题在于$Z(X)$的承诺，因为只有一个盲因子，因此需要设计协议防止泄露任何与根相关的信息
另一个问题是计算商多项式$H(X)$的时间开销为$O(n)$，稍微有点长，本文利用预计算和保存witness元素的配对检查来进行优化
优化结果如下
2 Preliminaries
记法和Caulk的基本相同
集合$S\sub \mathbb F$商的消失多项式记为$Z_S(X)=\prod_{v\in S}(X-v)\in \mathbb F[X]$，以集合$S$元素为幂的集合记为$x^S=\{x^i\}_{i\in S},S\sub \Z$
本文和Caulk一样，在AGM中讨论
此外，本文参考了Plonk$[GWC19]$中的实配对和虚配对检查
度为$q$的记为$SRS_i=[f(x)]_i,x\in_R\mathbb F,i\in [q]$，其中多项式$f\in \mathbb F_{<q}[X]$
记$f_{i,j}$表示$SRS_i$的第$j$个元素，记$a,b\in \mathbb F^q$上的两个向量，两个向量在群$\mathbb G_1,\mathbb G_2$的编码由代数敌手$\mathcal A$返回
利用两个矩阵$T_1,T_2\in \mathbb F$，实配对检查等式为$(a\cdot T_1)\cdot (b\cdot T_2)=0$
如果在AGM中操作，对于每个输出$[a_j]_i$，$\mathcal A$返回一个向量$v$，满足
$$ a_j=\sum v_l\cdot f_{i,l}(x)=R_{i,j}(x) $$
其中$R_{i,j}(X)=\sum v_l\cdot f_{i,l}(X)$
对于$i\in \{1,2\}$，令$R_i=(R_{i,j})_j$表示域$\mathbb F$上的多项式对应的向量，则对应的虚配对检查的验证等式为$(R_1\cdot T_1)\cdot (R_2\cdot T_2)\equiv0$
关于密码学假设，和Plonk中一样，采用DLOG假设的配对变体q-DLOG
其他采用的协议组件还包括KZG向量承诺和Caulk中提到的位置隐藏链接性
3 Lookup Argument Construction
本文的lookup argument基于Caulk第七章的协议构建
记$\boldsymbol c,\boldsymbol a$分别表示向量$\vec c\in \mathbb F^n,\vec a\in \mathbb F^m$的向量承诺，并假设$n,m$都是2的正整数次幂
记$\mathbb H,\mathbb V$表示$\mathbb F$的两个乘法子群，大小分别为$n,m$，生成元分别为$\omega ,v$
记$I\sub [n]$为$\vec a$在$\vec c$中的值的下标，记一个映射$u:[m]\rarr I$，对于$\forall i \in [m],a_i=c_{u(i)}$
协议首先由Prover计算三个多项式$Z_I,C_I,U\in \mathbb F_{\leq m}[X]$，如下
$$ \begin{aligned} Z_I(X)&=\prod_{i\in I}X-\omega^i\\ C_I(X)&=\sum_{i\in I}c_i\cdot \tau_i(X)\\ U(X)&=\sum_{j\in [m]}u(j)\cdot \mu_j(X) \end{aligned} $$
其中$\tau_i(X),\mu_i(X)$分别是$I,\mathbb V$的拉氏基多项式
这三个多项式满足下列四个等式时，表明两个向量之间的位置链接隐藏性
$$ \begin{align} C(X)-C_I(X)&=0 \mod Z_I\\ Z_\mathbb H &= 0 \mod Z_I\\ C_I(U(X))-A(X)&=0 \mod Z_\mathbb V\\ Z_I(U(X)) &= 0 \mod Z_\mathbb V \end{align} $$
但是有一个问题，上述四个等式的前两个包含了度为$n$的多项式$C(X),Z_\mathbb H(X)$，计算这两个多项式的KZG承诺的时间开销为$O(n)$，不过这两个多项式都不是复合多项式（后两个验证等式中的$C_I,Z_I$都是复合多项式），因此我们可以利用SRS中的点$x$来完成实配对，从而检查约束正确，这么做的好处在于，可以在$O(m^2)$的时间内预计算配对检查所需要的商元素
接下来继续回到协议，继续定义两个多项式$W_1,W_2$
$$ \begin{aligned} C-C_I&=Z_I\cdot W_1\\ Z_\mathbb H&=Z_I\cdot W_2 \end{aligned} $$
Prover会查找预计算的值$\{[W_1^{(i)}(x)]_2,[W_2^{(i)}(x)]_2\}_{i\in I}$，其中
$$ \begin{aligned} W_1^{(i)}(X)&=\frac{C(X)-c_i}{X-\omega^i}\\ W_2^{(i)}(X)&=\frac{Z_\mathbb H}{X-\omega^i} \end{aligned} $$
并计算对应的群元素
$$ \begin{aligned} [W_1(x)]_2&=\sum_{i\in I}\frac{[W_1^{(i)}(x)]_2}{\prod_{j\in I,i=\neq j}\omega^i-\omega^j}\\ [W_2(x)]_2&=\sum_{i\in I}\frac{[W_2^{(i)}(x)]_2}{\prod_{j\in I,i=\neq j}\omega^i-\omega^j} \end{aligned} $$
然后Prover向Verifier发送对应于式1和式2的上元素，Verifier返回一个挑战$\alpha$，要求在该挑战处验证式3和式4，Prover通过揭示多项式的承诺来响应挑战，由于多项式的度比较低，因此揭示的开销为$O(m\log m)$
还有一个问题是提供三个多项式$Z_I,C_I,U$的零知识性，这也很简单，对于多项式$C_I,U$，只需要分别加上$Z_I,Z_\mathbb V$的一个随机倍数即可，$Z_I$复杂一些，需要乘上一个随机盲因子
Prover必须在协议的最后一步中的挑战点处计算$Z_I$的值，如果只是简单的对乘一个随机盲因子并不能提供足够的随机性来确保该多项式在承诺和求值时的零知识性，但是可以利用KZG的批处理特性来进一步减少知识的泄露，从而确保零知识性
协议如下图所示
协议的Prover复杂度为$O(m^2)$，主要是第一轮中计算$Z_I,C_I$两个多项式，以及第二轮中聚合预计算的KZG证据$\boldsymbol \omega$
Verifier验证过程需要检查三个KZG承诺揭示和一次配对计算，由于$U'(X)$的KZG承诺不会在子协议中揭示，因此可以通过消除$U'(X)$中的一个盲度来优化协议
此外，由于消除了子协议中使用的度约束检查，从而减少了一次配对的计算，利用Caulk中第八节的批处理方案，可以将配对数量减少至3，群$\mathbb G_1$的元素减少至7个
4 Linking to Pedersen Commitments
Caulk的第六节介绍了如何奖向量与一个Pedersen承诺相关联，也即$m=1$的情况，该方案中SRS需要包含一个额外的群$\mathbb G_1$的元素$h$，该元素与SRS中其他元素的离散对数关系位置
若期望用可分割性检查替换Caulk第六节的论证协议中的子协议时，需要注意可分割性检查不能确保$Z_I$有根，若$Z_I$是常数多项式，则配对检查与盲KZG揭示不匹配，不过在广义论证中，第三节的式4确保了$Z_I$有根
本文利用广义Schnorr证明来组成广义查找论证，从而在单元素情况下构造一个有效的论证，由于基于DLOG的经典Schnorr知识论证可以从一个标量域推广至素数阶域$[Sch91]$，此类情况下，本文将Schnorr协议推广至$\mathbb G_1$中两个具有不同底数的Pedersen承诺的知识论证
首先Prover随机选择$k\larr \mathbb F$，计算多项式$A(X)=v+k(X-1)$，并计算对应的承诺值$\boldsymbol a=v[1]_1+k[x-1]_1$，之后Prover和Verifier在$\boldsymbol a$和$\mathbb V=\{1\}$之间执行一次查找论证，从而证明下列两个知识
$$ \begin{aligned} \boldsymbol v&=v[1]_1+rh\\ \boldsymbol a&=v[1]_1+k[x-1]_1 \end{aligned} $$
具体协议如下
References
$[1]$ Jim Posen, Assimakis A. Kattis:Caulk+: Table-independent lookup arguments. IACR Cryptol. ePrint Arch. 2022: 957 (2022)