加密多项式
配合这些工具，我们现在就可以在加密的随机数 \(x\) 上做运算并相应地修改零知识协议了。
我们来看一下如何计算多项式 \(p(x) = x^3 - 3x^2 + 2x\)。前面已经明确了，知道一个多项式就是知道它的系数，在这个例子中也就是知道：1，-3，2。因为同态加密并不允许再对加密值求幂，所以我们必须要给出 \(x\) 的 1 到 3 次幂的加密值：\(E(x), E(x^2), E(x^3)\)，那么我们要计算的加密多项式就是：
$${E\left(x^3\right)}^1 \cdot {E\left(x^2\right)}^{-3} \cdot {E\left(x\right)}^{2} =$$
$${\left(g^{x^3}\right)}^1 \cdot {\left(g^{x^2}\right)}^{-3} \cdot {\Big( g^{x} \Big)}^2 =$$
$$g^{1x^3} \cdot g^{-3x^2} \cdot g^{2x} =$$
$$g^{x^3 - 3x^2 + 2x}$$
通过这些运算，我们就获得了多项式在一些未知数 \(x\) 处的加密计算结果。这确实是一个很强大的机制，因为同态的性质，同一个多项式的加密运算在加密空间中始终是相同的。
我们现在就可以更新前一个版本的协议了，比如对于阶数为 \(d\) 的多项式：
-
验证者
- 取一个随机数 \(s\)，也就是秘密值
- 令指数 \(i\) 取值为 \(0, 1, ..., d\) 时分别计算对 \(s\) 求幂的加密结果，即：\(E(s^i) = g^{s^i}\)
- 代入 \(s\) 计算未加密的目标多项式：\(t(s)\)
- 把对 \(s\) 求幂的加密结果提供给证明者：\(E(s^0), E(s^1), ..., E(s^d)\)
-
证明者
-
计算多项式 \(h(x) = \frac{p(x)}{t(x)}\)
-
使用加密值 \(g^{s^0}, g^{s^1}, \ldots, g^{s^d}\) 和系数 \(c_0, c_1, \ldots, c_n\) 计算
$$E\left( p(s) \right) = g^{p(s)} = \left(g^{s^d}\right)^{c_d} \cdots \left(g^{s^1}\right)^{c_1} \cdot \left(g^{s^0}\right)^{c_0}$$
然后同样计算
$$E\left( h(s) \right) = g^{h(s)}$$
-
将结果 \(g^p\) 和 \(g^h\) 提供给验证者
-
-
验证者
- 最后一步是验证者在加密空间内检查 \(p = t(s) \cdot h\)：
$$g^p = \left(g^h\right)^{t(s)} \quad \Rightarrow \quad g^p = g^{t(s) \cdot h}$$
注：因为证明者并不知道与 \(s\) 相关的任何信息，所以很难提出不合法但能匹配验证的计算结果。
尽管这个协议中证明者的灵活性有限，他依然可以通过其他的方式来伪造证明，无需实际使用验证者提供的 \(s\) 的幂的加密值。例如，如果证明者声称有一个满足条件的多项式，但只使用了 2 个幂值 \(s^3\) 和 \(s^1\)，这在当前协议中是不能验证的。
译者注：本节利用强同态加密这个工具，构造了一个相对较强的零知识证明协议。但是如上文所述，这里还是存在一些问题——无法验证证明者是否是真的使用了验证者提供的值来构造证明。
下一节中将会展示如何构造一个完备的多项式零知识证明协议。