4-KCA验证The Knowledge of Coefficient Test and Assumption

KCA验证The Knowledge of Coefficient Test and Assumption

2019.12.06 胡振远

在多项式盲证中，Alice在未知 $s$ 的情况下，通过计算 $E(P(s))$ ，确实能够验证Bob拥有 $s$ ，是 $P(x)$ 的解。因此Alice可以向外界宣告，Bob是对的。但是如果Alice不诚实，不计算 $E(P(s))$ 就直接向外宣告Bob是对的，或者宣告Bob是错的。那么Alice这种行为如何保证呢。我们需要用到KCA做检验。

KCA检验原理

我们可以这么理解KCA检验的原理，假设Bob秘密的持有一个数据 $\alpha$ ，现在Alice除了需要公布 $E(P(s))$ ，还需要公布 $E(\alpha P(s))$ 。那么Bob就能根据 $E(P(s))$ 和 $E(\alpha P(s))$ 计算这两者的相关性。

由于Alice不知道 $\alpha$ ，如果Alice没有诚实地计算 $E(P(s))$ 和 $E(\alpha P(s))$ ，就无法伪造一份 $E(\alpha P(s))$ 。

那么Bob如何把 $\alpha$ 秘密地传输给Alice，而且Alice还可以在不知道 $\alpha$ 的情况下，计算出 $E(P(s))$ 和 $E(\alpha P(s))$ 呢。

$\alpha$ 对

我们定义 $g$ 是群 $G$ 的生成元， $\alpha \cdot g$ 表示 $\alpha$ 个 $g$ 相加。如果 $a$ ， $b$ 都是 $G$ 中的元素，且 $b=\alpha \cdot a$ ，我们称 $(a，b)$ 是一个 $\alpha$ 对。

按一下流程

Bob首先在某个 ${\Bbb{F}_p^*}$ 中选择一个 $\alpha$ ，从 $G$ 中选择 $a$ ，然后计算 $b=\alpha \cdot a$
Bob发送这个 $(a，b)$ 给Alice
Alice在 ${\Bbb{F}_p^*}$ 中选择一个 $\gamma$ ，计算 $(a'，b')=(\gamma \cdot a，\gamma \cdot b)$
由于 $b'=\gamma \cdot b=\gamma \alpha \cdot a= \alpha(\gamma \cdot a) = \alpha \cdot a'$ ，因此 $(a'，b')$ 也是一个 $\alpha$ 对。

使用 $\alpha$ 对进行KCA检验

在Bob向Alice公布 $E(s^0),E(s^1),E(s^2),...,E(s^d)$ 的同时，我们现在要求Bob同时Alice公布 $E(\alpha s^0),E(\alpha s^1),E(\alpha s^2),...,E(\alpha s^d)$ ，我们当然希望Bob公布的分别都是一个个的 $\alpha$ 对。

$E(s^0)$	$E(\alpha s^0)$
$E(s^1)$	$E(\alpha s^1)$
$E(s^2)$	$E(\alpha s^2)$
...	...
$E(s^d)$	$E(\alpha s^d)$

那怎么验证他们确实都是 $\alpha$ 对呢。

配对函数

配对函数 $e$ 是满足如下定义的函数：

$e(g^x,g^y)=e(g,g)^{xy}$

如果要验证 $\alpha$ 对，我们就可以判断如下等式是否成立:

$e(E(f(s),g^\alpha)=e(E(\alpha f(s)),g)$

设 $A=E(f(s))$ , $B=E(\alpha f(s))$

$e(A,g^\alpha)=e(g^{f(s)},g^\alpha)=e(g,g)^{\alpha f(s)}$
$e(B,g)=e(g^{\alpha f(s)},g)=e(g,g)^{\alpha f(s)}$

因此 $A，B$ 是一个 $\alpha$ 对，这样也就验证了Bob公布的两组数据。

KCA检验

回到多项式盲证，为了检验Alice正确的计算了 $E(P(s))$ ，现在需要Alice再计算一组 $E(\alpha P(s))$ 。由于

$E(\alpha P(x))=E(a_0\alpha x^0+a_1\alpha x^1+a_2\alpha x^2+...+a_d\alpha x^d)$

= $E(\alpha x^0)^{a_0}\cdot E(\alpha x^1)^{a_1}\cdot E(\alpha x^2)^{a_2}\cdot ... \cdot E(\alpha x^d)^{a_d}$

现在Alice不光要公布 $E(x^0)^{a_0}\cdot E(x^1)^{a_1}\cdot E(x^2)^{a_2}\cdot ... \cdot E(x^d)^{a_d}$ 的计算结果，同时还需要公布 $E(\alpha x^0)^{a_0}\cdot E(\alpha x^1)^{a_1}\cdot E(\alpha x^2)^{a_2}\cdot ... \cdot E(\alpha x^d)^{a_d}$