同态加密：Paillier算法

请注意，本文编写于 1020 天前，最后修改于 878 天前，其中某些信息可能已经过时。

概述

最著名的半同态加密方案，其是一个支持加法PHE的公钥密码系统，由Paillier在1999年的eurocrypt上首次提出，之后又在PKC01提出了简化版本，是当前Paillier方案的最优方案

众多PHE方案中Paillier效率较高，安全性证明完备，各大顶会和实际应用中广泛使用，隐私计算场景中最常用的PHE实例化之一

其他加法PHE还有DGK，OU和基于格的方案等，但是DGK方案的密文空间相比Paillier更小，加解密效率更高，但由于算法的正确性和安全性在学术界没有得到广泛研究和验证，OU和基于格的加法同态计算效率更高，也是PHE不错的候选项，但是OU使用相对少，基于格方案密文太大，部分场景具有局限性

原理

方案算法

KeyGen：密钥生成算法，产生公钥$PK$和私钥$SK$，以及一些公开常数$PP$（Public Parameter）
Enc：加密算法，使用$PK$对用户数据加密，得到密文$CT$
Dec：解密算法，解密$CT$得到明文$PT$
Add：同态加法，输入两个$CT$进行同态加法运算
ScalaMul：同态标量乘法，输入一个$CT$和一个标量$PT$，计算$CT$的标量乘法

方案描述

密钥生成

选择两个长度相等的大素数$p$和$q$，满足$gcd [ pq,(p-1)(q-1) ] =1$
计算$n=pq$和$\lambda=lcm(p-1,q-1)$，lcm是最小公倍数
随机选择证书$g\leftarrow Z^*_{n^2}$
定义函数$L(x)=\frac{x-1}{n}$，计算$\mu=[\ L(g^\lambda \ mod \ n^2) \ ]^{-1} \ mod \ n$
输出公钥$PK=(n,g)$，私钥$SK=(λ,μ)$

加密

输入明文消息m，满足$0\leq m<n$
选择随机数$r\in Z^*_n,0\leq r <n$
计算密文$c=g^mr^n \ mod \ n^2$

解密

输入密文c，满足$c \in Z^*_{n^2}$
计算明文$m=[\ L(c^\lambda \ mod \ n^2) \ ]·\mu \ mod \ n$

同态加法

对于密文$c_1,c_2$，计算$c=c_1·c_2\ mod \ n^2$

同态标量乘法

对于密文$c_1$和标量$k$，计算$c=c_1^k \ mod \ n^2$

正确性和安全性

加解密正确性

$$ Decrypt(c)=L(c^\lambda \ mod \ n^2)\cdot \mu=L((g^mr^n)^\lambda \ mod \ n^2)\cdot \lambda^{-1}=L(g^{m\lambda} \ mod \ n^2)\cdot \lambda^{-1}=\lambda \cdot m \cdot \lambda ^{-1}=m \ mod\ n $$

这里分析一下

因为$(p-1)|\lambda ,(q-1)|\lambda$，故有$\lambda=k_1(p-1)=k_2(q-1)$
此时根据费马小定理，可以得到$g^\lambda=g^{k_1(p-1)} \equiv 1 \ mod \ p$，因此有$(g^\lambda-1)| p$
同理有$g^\lambda=g^{k_2(q-1)} \equiv 1 \ mod \ q,(g^\lambda-1)| q$
根据数论知识，可以得到$(g^\lambda-1)|pq$，也即$g^\lambda\equiv 1 \ mod \ n$
从而有$g^\lambda \ mod \ n^2 \equiv 1 \ mod \ n$，也即$g^\lambda \ mod \ n^2 = n \cdot k_g +1(k<n)$
根据之前定义的$L(x)=\frac{x-1}{n}$，有$L(g^\lambda \ mod \ n^2)=k_g$
同时有
$$ \begin{aligned}&kn+1\equiv kn+1 \ mod \ n^2\\&(kn+1)^2\equiv(kn)^2+2kn+1\equiv 2kn+1\ mod\ n^2\\&(kn+1)^3\equiv (kn)^3+3(kn)^2+3kn+1\equiv 3kn+1 \ mod \ n^2\end{aligned} $$
不难得出
$$ (kn+1)^m\equiv mkn+1 \ mod\ n^2 $$
因此我们可以得到$g^{m\lambda}=(k_gn+1)^m\equiv mk_gn+1 \ mod \ n^2$
又有$r^{n\lambda}=(k_n+1)^n\equiv n^2k_n+1\equiv 1\ mod \ n^2$
因此利用$L$函数可以得到$L(g^{m\lambda} r^{n\lambda} \ mod n^2)=L(nmk_g+1)=\frac{nmk_g+1-1}{n}=mk_g$
根据之前计算的$L(g^\lambda \ mod \ n^2)=k_g$
因此有
$$ \frac{L(c^\lambda \ mod \ n^2)}{L(g^\lambda \ mod \ n^2)}=\frac{mk_g}{k_g}\equiv m \ mod \ n $$

同态加法正确性

不难验证

$$ Decrypt(c_1\cdot c_2 \ mod \ n^2)=Decrypt(g^{m_1}r^n \cdot g^{m_2}r^n \ mod \ n^2)=Decrypt(g^{m_1+m_2}r^{2n} \ mod \ n^2)=m_1+m_2 $$

同态标量乘法正确性

$$ Decrypt(c_1^a \ mod \ n^2)=Decrypt(g^{am_1}r^n \ mod \ n^2 =am_1 $$

安全性

方案满足加密方案的标准安全定义：语义安全，也即在CPA下密文不可区分性（IND-CPA），直观的说就是密文不会泄露关于明文的任何信息，方案可归约到判定性合数剩余假设（DCRA，Decisional Composite Residuosity Assumption，给定合数$n$和整数$z$，判定$z$是否在$n^2$下是否是$n$次剩余，目前暂未被攻破）

高效实现

在不影响算法正确性的前提下，为了简化运算，可在KeyGen阶段取$g=n+1$，此后对于$g^m$的运算可转换为$(n+1)^m$的运算

根据二项式定理，可以展开如下

$$ (n+1)^m=\left (\begin{matrix}m\\0\end{matrix} \right )n^m+\left (\begin{matrix}m\\1\end{matrix} \right )n^{m-1}+...+\left (\begin{matrix}m\\2\end{matrix} \right )n^2+mn+1 \ mod\ n^2 $$

上式前$m-1$项均为$n^2$的倍数，$mod \ n^2$条件下约去，因此转化为下列等式

$$ (n+1)^m=mn+1\ mod \ n^2 $$

DJN优化方案

该方案描述了Paillier密码系统的一般性结构，其中包括了部分优化，目前为最优方案，优化后算法不同点如下

KeyGen阶段

KeyGen阶段生成RSA素数要求$p=q=3 \ mod \ 4$且$gcd(p-1,q-1)=2$

随机选择$x\leftarrow Z_n^*$，计算$h=-x^2，h_s=h^n\ mod \ n^2，\lambda=\frac{(p-1)(q-1)}{2}$
公钥$PK=(n,hs)$

加密阶段

密文$c=g^mr^n \ mod \ n^2$，其中$r^n$部分可优化

对于$r^n$，采用$h_s^a$来替换原来的$r^n$，其中$a\leftarrow Z_{2^{\frac{|n|}{2}}}$，该方案比原算法的比特长度减小一般，计算速度更快

中国剩余定理加速模指数

中国剩余定理（CRT）有一个非常好的特性，他描述了两个代数空间的同构性，也即一个代数空间可以被分解为多个互相正交的子空间，且原来的空间与分解后的空间保持一一映射，也就是同一个空间的两种表现形式

当$n=pq，gcd(p,q)=1$时，有$Z_n\simeq Z_p * Z_q$，意味着$Z_n$中的运算可以转化为$(Z_p,Z_q)$中，从而计算效率更高，因此利用该定理可以在模下加速模指数运算

具体利用CRT加速计算例子如下

当$n=pq，gcd(p,q)=1$时，计算$a^b \ mod \ n$，计算方法有两种

直接嗯算：该方法在$Z_n$上计算，计算量较大
CRT优化：先将$a^b$映射到$(Z_p,Z_q)$上计算，最后再将结果聚合到$Z_n$

映射到$Z_p$：计算$a^b$在$Z_p$上的映射$x_p=a_p^{b_p}$，其中$a_p=a \ mod \ p$，根据欧拉定理，有$b_p=b \ mod \ \phi(p)$
映射到$Z_q$：计算$a^b$在$Z_q$上的映射$x_q=a_q^{b_q}$，步骤同上
聚合：利用CRT公式计算$x$
$$ x=x_p\cdot q^{-1} (mod \ p) \cdot q+x_q\cdot p^{-1}( mod \ q) \cdot p $$
根据贝祖定理，由于$p$和$q$互素，因此有
$$ q{-1}(mod \ p)\cdot q+p^{-1}(mod \ q)\cdot p=1 $$
带入上式，得到
$$ x=x_p[1-p^{-1} (mod \ q)\cdot p]+x_q\cdot p^{-1}(mod \ q)\cdot p=x_p+(x_q-x_p)\cdot p^{-1}(mod \ q)\cdot p $$

从而利用CRT，先映射到小空间进行计算，再聚合到大空间，得到最终结果

利用CRT加速Paillier

Paillier中的主要开销在于$Z_{n^2}$上的模指数运算，在拥有私钥的情况下，可以利用CRT将$Z_{n^2}$分解到$Z_{p^2}$和$Z_{q^2}$上计算，提高加解密速度

若需要此方法加速，则计算方必须知道模数$n^2$的分解，也即需要知道$(p^2,q^2)$，这两个是私钥，因此可以直接用于解密过程

对于加密过程，根据加密方是否拥有私钥，将加密算法设计为两类

若加密方无私钥，采用算法$Enc(pk,m)$
若加密方有私钥，则采用算法$Enc(pk,sk,m)$，此时可利用CRT加速加密过程

预计算

因为确定密钥参数后，Paillier每次加密都是固定底数的（fixed-base），此时模幂运算可采用快速幂，利用空间换时间

此时加解密中重复使用的变量会被保存，这些计算会在密钥生成阶段完成计算并保存，以避免加解密时重复计算

JNI技术

Java本地接口（Java Native Interface），提供若干API，使得Java可以与其他语言程序互相调用，以实现Java不便实现的功能或难以达到的效率

从而用这个技术，可以调用C++代码来替Java执行计算

代价是丧失可移植性

打包

为了确保安全强度，Paillier方案中的明文空间大小为固定的n（如3072 bits），而待加密的明文可能属于较小的空间（如16bits）

在这种情况下，如果按照正常的加密方式，将1个明文加密为1个密文，则明文空间会存在很高的冗余（等同于先在16bits明文的高位填充0，编码到3072bits，再进行加密），在加密时间和空间上效率都很低

为了避免冗余，在明文较短且定长的情况下，我们充分利用明文空间，将多个明文打包为1个进行加解密，具体步骤如下

打包：根据Paillier方案中n的比特长度|n|和单个明文的长度|m_i|，计算明文空间可容纳的最大明文数量$k=\lfloor\frac{|n|}{|m_i|}\rfloor$，以k个明文分为一组，对$\{m_i\}_{i=1,2,...k}$进行拼接，然后得到
$$ m=m_k||m_{k-1}||...||m_1 $$
加密：利用Paillier算法对$m$进行加密，得到密文$c$
解密：对密文$c$进行Paillier解密，得到明文$m$
解包：对解密后的$m$进行拆分

相比于原来的一次加密一个明文，打包优化后，密文大小和加解密中模指数时间消耗降低为原来的1/k，该方法的优化效果取决于明文长度

Python库

Rrefs:Usage — python-paillier 1.4.1 documentation

参考文章

$[1]$Paillier P. Public-key cryptosystems based on composite degree residuosity classes//International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 1999: 223-238.

$[2]$Paillier-Cryptosystem - Wikipedia

$[3]$Paillier半同态加密：原理、高效实现方法和应用 - 知乎专栏

同态加密 Paillier算法

概述

原理

方案算法