限制多项式

前文提到，多项式的知识其实就是它的系数 \(c_0, c_1, \ldots, c_i\) 的知识。协议中我们是通过对秘密值 \(s\) 的幂的加密值再进行求幂来对系数进行「赋值」的（例如 \(E\left(s^i\right)^{c_i} = g^{c_i \cdot s^i}\)）。我们已经限制了证明者对 \(s\) 幂的加密值的选择，但是这个限制并不是强制的，也就是说，证明者可以使用任何可能的方法找到满足 \(z_p = \left(z_h\right)^{t(s)}\) 的值 \(z_p\) 和 \(z_h\)，再用这两个值来代替 \(g^p\) 和 \(g^h\) 交给验证者。例如随机选定的 \(r\)、\(z_h = g^r\) 和 \(z_p = \left(g^{t(s)}\right)^r\)，其中 \(g^{t(s)}\) 可以从已知的 \(s\) 的加密幂中计算出来。所以验证者需要证明者证明，他给出的 \(g^p\) 和 \(g^h\) 就是用 \(s\) 幂的加密值而不是其他值计算出来的。

我们看一个由一个变量和一个系数组成的一阶多项式 \(f(x) = c \cdot x\) 的简单例子，对应的 \(s\) 的加密值为 \(E(s) = g^s\)。这里我们要做的就是确保证明者是使用 \(s\) 的加密值，即 \(g^s\)，而不是其他值与系数 \(c\) 做同态相乘的。所以结果一定是 \(\left(g^s\right)^c\) 的形式（\(c\) 为任意值）。

解决这个问题的一种方法就是对另一个移位（Shift）的加密值做同样的运算，充当「校验和（Checksum）」的算术模拟，以确保结果是原始值的求幂值。

这是通过指数知识假设（Knowledge-of-Exponent Assumption，KEA）方法来实现的，在 [Dam91] 中有介绍，更精准地说：

• Alice 有一个值 \(a\)，她想要 Bob 对其进行任意指数的求幂（这里 \(a\) 是一个有限域群的生成元），唯一的要求是只能对 \(a\) 进行求幂，为了确保这一点，她要：

  • 选择一个随机数 \(\alpha\)
  • 计算 \(a' = a^\alpha \ (\mathrm{mod}\ {n})\)
  • 提供一个元组 \((a, a')\) 给 Bob，然后让他对这两个值执行任意的求幂运算，返回结果元组 \((b, b')\)，同时保持这里的指数「\(\alpha\)-移位」不变，即 \(b^\alpha = b' \ (\mathrm{mod}\ {n})\)

• 因为 Bob 无法从元组 \((a, a')\) 中提取 \(\alpha\) 的值，通过暴力破解也难以实现，因此就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：

  • 选择一个值 \(c\)
  • 计算 \(b = (a)^c \ (\mathrm{mod}\ {n})\) 和 \(b' = {(a')}^c \ (\mathrm{mod}\ {n})\)
  • 回复 \((b, b')\)

• 有了回复的元组和 \(\alpha\)，Alice 就可以验证等式：

  $$(b)^\alpha = b'$$

  $$\left(a^c\right)^\alpha = {(a')}^c$$

  $$a^{c \cdot \alpha} = {\left(a^\alpha\right)}^c$$

• 结论：

  • Bob 在元组的两个值的计算上都用了同一个指数（即 \(c\)）
  • Bob 只能用 Alice 原本的元组来保持 \(\alpha\) 关系
  • Bob 知道指数 \(c\)，因为构造有效 \((b, b')\) 的唯一方式是使用同一个指数
  • Alice 并不知道 \(c\)，这和 Bob 不知道 \(\alpha\) 的原因一样（尽管 \(c\) 是被加密的，但它的可能取值范围并没有足够大到可以保持零知识的性质，这个问题我们将在 3.5 节解决）

最后这个协议提供了一个证明给 Alice，Bob 确实是用他知道的某个值对 \(a\) 进行求幂的，而且他也不能做其他的任何操作，例如乘法、加法，因为这样就会破坏 \(\alpha\)-移位关系。

在同态加密中，求幂是对被加密值进行乘法运算。我们可以应用这个结构到一个简单的单一系数多项式 \(f(x) = c \cdot x\) 的例子中：

• 验证者选择随机值 \(s, \alpha\)，然后提供令 \(x = s\) 的一阶及其「移位」的计算值：\(\left(g^s, g^{\alpha \cdot s}\right)\)

• 证明者代入系数 \(c\) 计算：\(\left( \left(g^s\right)^c, \left(g^{\alpha \cdot s}\right)^c \right) = \left(g^{c \cdot s}, g^{\alpha \cdot c \cdot s}\right)\)

• 验证者验证：\(\left(g^{c \cdot s}\right)^\alpha = g^{\alpha \cdot c \cdot s}\)

这个结构可以限制证明者只能用验证者提供的加密的 \(s\) 进行计算，因而证明者只能将系数 \(c\) 赋给验证者提供的多项式。现在我们可以扩展这种单项式上的方法到多项式上，因为计算是将每个项的系数赋值分别计算后再同态地「相加」在一起的（这个方法是 Jens Groth 在 [Gro10] 中介绍的）。所以如果给定证明者一个指数为 \(s\) 的幂以及它们的移位的加密值，他就可以计算原始的和移位后的多项式，可以满足同样的校验。对于阶数为 \(d\) 的多项式：

• 验证者提供加密值 \(g^{s^0}, g^{s^1}, \ldots, g^{s^d}\) 和他们的变换 \(g^{\alpha s^0}, g^{\alpha s^1}, \ldots, g^{\alpha s^d}\)

• 证明者：

  • 计算给定的带有 \(s\) 的幂的加密多项式：

    $$g^{p(s)} = \left(g^{s^0}\right)^{c_0} \cdot \left(g^{s^1}\right)^{c_1} \cdot \ldots \cdot \left(g^{s^d}\right)^{c_d} = g^{c_0 s^0 + c_1 s^1 + \ldots + c_d s^d}$$

  • 计算给定的带有 \(s\) 的幂的 \(\alpha\)-移位的加密「移位」多项式：

    $$ g^{\alpha p(s)} = \left(g^{\alpha s^0}\right)^{c_0} \cdot \left(g^{\alpha s^1}\right)^{c_1} \cdot \ldots \cdot \left(g^{\alpha s^d}\right)^{c_d} = g^{c_0 \alpha s^0 + c_1 \alpha s^1 + \ldots + c_d \alpha s^d} = g^{\alpha (c_0 s^0 + c_1 s^1 + \ldots + c_d s^d)}$$

  • 将计算结果 \(g^p, g^{p'}\) 提供给验证者

• 验证者校验：\({\left(g^p\right)}^\alpha = g^{p'}\)

前面的多项式例子 \(p(x) = x^3 - 3x^2 + 2x\) 就变成了：

• 验证者提供 \(E(s^3), E(s^2), E(s)\) 和它们的变换 \(E(\alpha s^3), E(\alpha s^2), E(\alpha s)\)

• 证明者计算：

  $$g^p = g^{p(s)} = \left(g^{s^3}\right)^1 \cdot \left(g^{s^2}\right)^{-3} \cdot \Big(g^s\Big)^2 = g^{s^3} \cdot g^{-3s^2} \cdot g^{2s} = g^{s^3 - 3s^2 + 2s}$$

  $$g^{p'} = g^{\alpha p(s)} = \left(g^{\alpha s^3}\right)^1 \cdot \left(g^{\alpha s^2}\right)^{-3} \cdot \Big(g^{\alpha s}\Big)^2 = g^{\alpha s^3} \cdot g^{-3 \alpha s^2} \cdot g^{2 \alpha s} = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

• 验证者校验：\({\left(g^p\right)}^\alpha = g^{p'}\)：

  $${\left(g^{s^3 - 3s^2 + 2s}\right)}^\alpha = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

  $$g^{\alpha(s^3 - 3 s^2 + 2s)} = g^{\alpha(s^3 - 3 s^2 + 2s)}$$

现在我们就可以确保证明者是用了验证者提供的多项式而不是其他值做了计算，因为别的方法不能够保持 \(\alpha\)-移位。当然如果验证者想要确保在证明者的多项式中排除了 \(s\) 的某些次幂，比如 \(j\)，他可以不提供对应的密文 \(g^{s^j}\) 及其移位 \(g^{\alpha s^j}\)。

与前面的协议相比，我们现在已经有了一个健壮的协议。然而，虽然已经做了加密，但在零知识性质上也还依然存在一个很明显的缺陷：理论上多项式参数 \(c_i\) 是一个很广的取值范围内的值，但实际上这个范围可能很有限（比如前面例子中的 6），这就意味着验证者可以在有限范围的系数组合中进行暴力破解，最终计算出一个与证明者的答案相等的结果。比如我们将每个系数的取值范围定为 100，多项式阶数为 2，那么会有 100 万种不同的组合，可以认为暴力破解只需要少于 100 万次的迭代。更重要的是，即使只有一个系数，且系数值为 1 的例子中，安全协议也应该能够保证其安全。

译者注：有了 KEA，就可以约束证明者只能使用验证者提供的加密值去构造证明了。严格地说，这里是用的是 KEA 的扩展版本，叫做指数假设的 q-幂知识（The q-Power Knowledge of Exponent Assumption，q-PKE）。