cdcq的密码学教程三——同态加密的Paillier算法

一、前言

什么是同态加密？

同态加密就是指对密文做某种运算后相当于对明文做某种运算。例如经典的 RSA 算法就是一个乘法同态的加密算法：

c_1 \equiv m_1 ^ e\ mod\ n \\ c_2 \equiv m_2 ^ e\ mod\ n \\ c_1 * c_2 \equiv (m_1 * m_2) ^ e\ mod\ n

一般地，如果一对加解密算法 $E(m)$ 和 $D(c)$ 满足 $D(F_2(E(m_1), E(m_2))) = F_1(m_1, m_2)$ ，那么我们就说这个算法是对操作 $F_1(x, y)$ 同态的。

同态加密有什么用？

如果你可以在本地就执行所有的操作，那当然是没有必要加密啦。但是许多场景是要在异地计算的，例如云计算，本地的算力不够，要提交到服务器计算，但是又不希望泄漏计算数据的隐私；或者是多方计算，一个计算涉及多台主机，就可以使用同态加密。

Paillier 是比较入门的一种同态加密算法，支持两个加密数字相加或者一个加密数字乘上一个明文数字，本文就主要介绍这个算法。

二、Paillier 公钥加密系统

Paillier 是一个公钥加密系统，由三部分组成：密钥生成算法、加密算法和解密算法。

密钥生成算法：

随机选取两个大质数 p 和 q ，保证 $gcd(pq, (p - 1)(q - 1)) = 1$ 。
模数 $n = pq$ 。
从 $[1, n^2]$ 中随机选取一个整数 $g$ 作为公钥， $\lambda = lcm(p - 1, q - 1)$ 为私钥。
定义 $L(x) = \frac{x - 1}{n}$ ，计算 $\mu \equiv (L(g^\lambda\ mod\ n^2))^{-1}\ mod\ n$ 。如果 $\mu$ 不存在则重新执行密钥生成算法。

加密算法：

明文 $m$ 应该是区间 $[0, n)$ 中的一个整数。

从 $(0, n)$ 中随机选取一个整数 $r$ 。
密文 $c \equiv g^mr^n\ mod\ n^2$ 。

解密算法：

密文 $c$ 应该是区间 $(0, n^2)$ 中的一个整数

明文 $m \equiv L(c^\lambda\ mod\ n^2) \cdot \mu\ mod\ n$ 。

三、解密算法的正确性证明

有些朋友可能看完加密算法一头雾水，为何会同时存在两个模数 $n$ 和 $n^2$ ？ $L$ 函数这么一个奇怪的定义又是怎么回事？这事要从二项式定理说起。

我们都知道二项式定理：

(1 + n)^x = \sum_{k = 0}^x \binom{k}{x}n^k .

在模 $n^2$ 意义下，就有

(1 + n)^x \equiv 1 + nx + \binom{2}{x}n^2 + ... \equiv 1+nx\ mod\ n^2 .

把两边变化一下，可以得到

x \equiv \frac{(1 + n)^x - 1}{n}\ mod\ n^2 .

这意味着我们可以轻易地计算形如 $(1 + kn)^x$ 的数在模 $n^2$ 意义下关于 $(1 + kn)$ 的对数，方法就是通过 $L$ 函数计算。

此外还需要知道一个结论，Carmichael 定理： $p$ 和 $q$ 是大质数， $n = pq$ ， $\lambda = lcm(p - 1, q - 1)$ ，对于任意整数 $w$ 有

\left\{ \begin{aligned} w^\lambda \equiv 1\ mod\ n \\ w^{n\lambda} \equiv 1\ mod\ n^2 \\ \end{aligned} \right.

证明：

第一条很显然，利用欧拉定理得到。

由第一条可以知道 $w^\lambda = 1 + kn$ ，那么 $w^{n\lambda} = (1 + kn)^n$ ，根据之前有关二项式定理的结论就有

w^{n\lambda} \equiv (1 + kn)^n \equiv 1 + kn^2 + \binom{2}{n}k^2n^2 + ... \equiv 1\ mod\ n^2 .

现在来看解密公式

L(c^\lambda\ mod\ n^2) \cdot \mu \equiv \frac{L(c^\lambda\ mod\ n^2)}{L(g^\lambda\ mod\ n^2)}\ mod\ n .

其中

c^\lambda \equiv g^{m\lambda}r^{n\lambda} \equiv g^{m\lambda}\ mod\ n^2 .

所以

\frac{L(c^\lambda\ mod\ n^2)}{L(g^\lambda\ mod\ n^2)} \equiv \frac{L(g^{m\lambda}\ mod\ n^2)}{L(g^\lambda\ mod\ n^2)} \ mod\ n .

考察 $g^\lambda$ ，有

g^\lambda \equiv 1\ mod\ n .

所以

g^\lambda \equiv 1 + kn\ mod\ n^2 \\ g^{m\lambda} \equiv (1 + kn)^m \equiv 1 + knm \ mod\ n^2 .

那么

L(g^\lambda\ mod\ n^2) = \frac{g^\lambda - 1}{n} = k \\ L(g^{m\lambda}\ mod\ n^2) = \frac{g^{m\lambda} - 1}{n} = km .

因此

\frac{L(g^{m\lambda}\ mod\ n^2)}{L(g^\lambda\ mod\ n^2)} \equiv \frac{km}{k} \equiv m\ mod\ n .

这样就证明了 Paillier 算法的正确性。

看到这里我们可以说：Paillier 本质是利用了计算某些离散对数很容易的问题。随机数 $r$ 是用来遮蔽明文的，但如果有私钥 $\lambda$ ，就可以将 $r$ 消除掉，然后计算离散对数得到 $m$ 。

Paillier 原文采用的是另一种角度证明，先证明了加密函数是双射的，然后可以得到一些结论。此外原文还说用中国剩余定理可以加速解密过程，这里就不多说了。

四、Paillier 算法的同态操作

Paillier 的同态操作原理还是比较简单的，基本上自己都能推出来。

让密文相乘就可以使两个加密数相加：

c_1 = g^{m_1}{r_1}^n \\ c_2 = g^{m_2}{r_2}^n \\ c_1c_2 = g^{m_1 + m_2}(r_1r_2)^n .

对 $c_1c_2$ 解密就可以得到 $m_1 + m_2$ 。

对密文做 $a$ 次方就可以使一个加密数乘上 $a$ ：

c = g^mr^n \\ c^a = g^{am}r^{an} .

解密就得到 $am$ 。

由此可以看出 Paillier 算法不需要公钥就可以实现同态操作。

五、后记

学这个算法的过程也算比较坎坷，因为网络上没啥证明的教程。有一篇文章居然说为了方便起见，选 $g = 1 + n$ ，证明倒是方便了，但我觉得不合适。所幸有一片知乎文章写得很清楚，加上算法本身不算难，最后也是搞懂了。希望这篇文章能让后来者学得更轻松一些。

参考文章：

知乎教程，作者“民科局长”：https://zhuanlan.zhihu.com/p/106340045?utm_source=weibo

一篇英文教程，但是没有证明：https://blog.openmined.org/the-paillier-cryptosystem/

论文原文：https://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf