上一节中谈到了，Bob可以让Alice计算$E(P(s))$，同时还不将$s$泄露给Alice

但是上一节中忽略了一个问题，Alice可以算$E(P(s))$但并不代表他会将$E(P(s))$发送给Bob，万一他只是随便算一算，然后给Bob返回一个错误的结果怎么办

因此我们需要在协议中加入一点其他的限制，从而强制Alice发送正确的结算结果，这个限制称为系数知识测试（Knowledge of Coefficient Test，KC）

和之前一样，记一个群为$G$，生成元为$g$，群的阶为$p$，且$p$足够大使得计算离散对数是困难的

KC Test

对于$\alpha \in F^*_p$，若有一个数对$(a,b)$，满足$a,b\neq 0$且$b=a\cdot \alpha$，则称$(a,b)$为$G$中的一个$\alpha$对

对于KC Test，具体Bob执行下列工作

  1. Bob选择一个随机的$\alpha \in_R F^*_p$与$a\in G$，然后计算$b= \alpha \cdot a$
  2. Bob将数对$(a,b)$作为挑战发送给Alice，此时$(a,b)$为$G$中的一个$\alpha$对
  3. Alice需要用另一个$G$中的一个$\alpha$对$(a',b')$响应Bob，也即Alice需要响应$(a',b')\neq (a,b)$
  4. Bob检查是否有$b'= \alpha \cdot a'$，若成立则接受Alice，否则拒绝Alice

如果说Alice知道$\alpha$，那他只需要随机选一个$a'\in G$，计算$b'= \alpha \cdot a'$并发送给Bob就可以了，但是之前提到了群$G$的阶$p$足够大，大到计算离散对数是困难的，因此Alice难以直接通过$(a,b)$得到

但是有一种方法，可以使得Alice在不知道$\alpha$的情况下仍然可以正确响应Bob，具体Alice可以这么操作：选择一个随机的$c \in_R F^*_p$，然后令$(a',b')=(c\cdot a,c\cdot b)$，发送给Bob，此时显然$(a',b')$是$G$中的一个$\alpha$对，因为$b'=c\cdot b = c \cdot \alpha \cdot a=\alpha \cdot (c \cdot a)=\alpha \cdot a'$

若Alice采用上述方式响应Bob，则意味着他知道这个特定的$\gamma$，满足$a'=\gamma \cdot a$，这种方式称为系数知识假设

系数知识假设（Knowledge of Coefficient Assumption，KCA）：若Alice在Bob选择的$a$和$\alpha$下，以一个不可忽略的概率返回一个合法的$(a',b')$，则说明Alice一定知道一个特定的$c$，满足$a'=c\cdot a$

在之前的第二节中，我们构造了一个协议使得Bob可以在不让Alice知道$s$的情况下计算$E(P(s))$，也即具有下列两个特性

  • 盲性：Alice不会知道任何关于$s$的信息，Bob不会知道任何关于$P$的信息
  • 可验证性：Alice发送一个不匹配的$E(P(s))$使得Bob仍然接受的概率可以忽略不计

利用之前提到的同态隐藏可以做到该协议的盲性，本节中将会利用上一节提到的KC Test和KCA实现可验证性

扩展的KCA

和上一节提到的一样，因为群G上计算离散对数是困难的，Alice难以直接通过$(a,b)$得到$\alpha$，如果Alice能在Bob选择的$a$和$\alpha$下响应Bob的挑战，则意味着Alice知道一个特定的$c$，满足$a'=c \cdot a$

这里将KCA扩展一下，Bob不是发送一个数对$(a,b)$，而是发送$d$个数对$(a_1,b_1),(a_2,b_2),...,(a_d,b_d)$，这$d$个数对都是$\alpha$对，和之前一样，Alice收到这些数对后需要返回一个不同的$(a',b')$（注意是返回一个不同的即可，而不是每一个数对都要返回不同的），因为Alice不知道$\alpha$，因此Alice需要选择一个$c\in F^*_p$，使得每一个数对$(a_i,b_i)$都能生成一个不同的$\alpha$对$(c\cdot a_i,c\cdot b_i)$

思考一下，如果Alice收到了两个或以上的数对，则其生成$\alpha$对的方式有很多种，以Alice收到两个$\alpha$对$(a_1,b_1),(a_2,b_2)$举例，此时Alice可以选择$c_1,c_2\in F^*_p$，并计算

$$ (a',b')=(c_1\cdot a_1+c_2\cdot a_2,c_1\cdot b_1+c_2\cdot b_2 ) $$

显然这也是一个$\alpha$对

稍微推广一下，将上述方法推广至$d$个$\alpha$对，Alice可以选择$c_1,...,c_d\in F^*_p$，满足$(a',b')=(\sum_{i=1}^dc_i\cdot a_i,\sum_{i=1}^dc_i\cdot b_i)$

不难看出，如果Alice采用这种方式生成一个$\alpha$对，则意味着其知道$a'$和$a_1,...,a_d$之间的某些线性关系，根据第三节提到的KCA，我们可以得到$d$阶KCA，如下

d-KCA：假设Bob选择了一个随机的$\alpha \in_R F^*_p$，并给Alice发送了$d+1$个数对$(g,\alpha\cdot g),(s\cdot g,\alpha\cdot s\cdot g),...,(s^d\cdot,\alpha\cdot s^d\cdot g)$，如果Alice可以生成一个$\alpha$对$(a',b')$，则意味着Alice以一个不可忽略的概率知道系数$c_0,...,c_d\in F^*_p$，满足$a'=\sum_{i=0}^dc_i\cdot s^i\cdot a_i,$

结合第二章提到的多项式盲评估来看d-KCA，这里Bob发送的不是随机的$\alpha$对，而是一系列可以构造出特定多项式结构的$\alpha$对，这对继续构建协议非常有用

对盲评估协议的验证

这里将之前的同态隐藏修改一下，令$E(x)=x\cdot g$，g为G的生成元，则利用这个$E$，构建协议如下

  1. Bob选择一个随机的，然后Bob根据，向Alice发送$d+1$个$\alpha$对：$(E(1),E(\alpha)),(E(s),E(\alpha \cdot s)),...,(E(s^d),E(\alpha \cdot s^d))$
  2. Alice利用收到的这些值，利用d-KCA的方法计算$a=P(s)\cdot g,b=\alpha \cdot P(s)\cdot g$，然后将$(a,b)$返回给Bob
  3. Bob检查等式$b=\alpha \cdot a$是否成立，若成立则接受Alice，否则拒绝Alice

上述协议中，注意到给定了$P$的系数，也即$P(s)\cdot g$实际上是$g,s\cdot g,...,s^d \cdot g$的线性组合，而$\alpha \cdot P(s)\cdot g$是$\alpha \cdot g,\alpha \cdot s\cdot g,...,\alpha \cdot s^d \cdot g$的线性组合，根据第二节中提到的内容，Alice可以根据Bob提供的值，计算一个只有他知道的多项式$P$，且因为Bob发送的$\alpha$对都是经过同态隐藏处理的，因此Bob也可以确保Alice无法根据这些$\alpha$对恢复出$s$

此外，根据d-KCA，如果Alice返回了正确的$(a,b)$，则意味着其知道$c_0,...,c_d\in F^*_p$，满足$a'=\sum_{i=0}^dc_i\cdot s^i\cdot a_i,$的概率不可忽略，也即Alice确实知道某个多项式$P$，满足$P(X)=\sum^d_{i=0}c_i\cdot X_i$

同样的，Bob在协议的第三步知道P的概率也是可忽略的，从而我们利用了d-KCA开发了一个可验证的多项式盲评估的协议

小结

利用系数知识测试，Bob可以确保Alice不会随意的违背协议，再结合上第一节中的同态隐藏和第二节中的多项式盲评估，使得Alice和Bob可以完成相应的计算

下一篇文章中将介绍如何利用这个组件构建zk-SNARKs

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$Explaining SNARKs Part III: The Knowledge of Coefficient Test and Assumption - electriccoin-blog
$[2]$Explaining SNARKs Part IV: How to make Blind Evaluation of Polynomials Verifiable - electriccoin-blog