强同态加密

我们再回到同态加密上，使用模运算，例如取模 7，我们可以得到：

$$5^1 = 5 \ (\mathrm{mod}\ {7})$$

$$5^2 = 4 \ (\mathrm{mod}\ {7})$$

$$5^3 = 6 \ (\mathrm{mod}\ {7})$$

$$\ldots$$

不同指数下运算将会得到同样的结果：

$$5^5 = 3 \ (\mathrm{mod}\ {7})$$

$$5^{11} = 3 \ (\mathrm{mod}\ {7})$$

$$5^{17} = 3 \ (\mathrm{mod}\ {7})$$

$$\ldots$$

这样就很难知道指数是多少了。事实上，如果模取得相当大，从运算结果倒推指数运算就不可行了，现代密码学很大程度上就是基于这个问题的困难程度。

方案中所有的同态性质都在模运算中保留了下来：

$$\mathrm{加密：} 5^3 = 6 \ (\mathrm{mod}\ {7})$$

$$\mathrm{乘法：} 6^2 = {(5^3)}^2 = 5^6 = 1 \ (\mathrm{mod}\ {7})$$

$$\mathrm{加法：} 5^3 \cdot 5^2 = 5^5 = 3 \ (\mathrm{mod}\ {7})$$

注：模相除有点难，已经超出范围了。

我们来明确地说明一下加密函数：\(E(v) = g^v \ (\mathrm{mod}\ {n})\)，这里 \(v\) 就是我们要加密的值。

备注 3.2 这个同态加密模式有一个限制，我们可以把一个加密的值和一个未加密的值相乘，但我们不能将两个加密的值相乘（或者相除），也就是说我们不能对加密值取幂。虽然这些性质第一感觉看上去很不友好，但是却构成了 zk-SNARK 的基础。这个限制将在 3.6.1 节中讲到。

译者注：通过模运算形成的集合被称为有限域，而通过计算指数再进行模运算形成的集合构成循环群。常见的同态加密方式除了整数幂取模之外，还有椭圆曲线上的倍乘。