Paillier

1. 原始Paillier

1.1 简介

Paillier加密算法是Pascal paillier在1999年发明的概率公钥加密算法，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法，已经广泛应用在加密信号处理或第三方数据处理领域。

复合剩余类的困难问题：判定合数剩余类问题是指$N= p * q$，其中 $p$ 和 $q$ 都是大素数，任意给定 $y ∈ \mathbb{Z}^{*}_{N^2}$,使得$z = y^{N} \;mod\; N^2$,判定z是模$N^2$的N次剩余还是非剩余是困难的。

论文：Efficient Public-Key Cryptosystems Provably Secure against Active Adversaries

1.2 算法过程

1.2.1 密钥产生

选取两个随机的大素数 $p,q$ ，计算 $n=p∗q$ 和 $λ=lcm(p−1,q−1)$， $lcm$ 为两个参数的最小公倍数。

选取随机数 $g$ ，$g∈\mathbb{Z}_{n^2}^{*}$ 且满足 $μ=(L(g^λmod\;n^2))^{−1}$ 存在。

函数 $L(x)$ 的定义如下 $L(x)=\frac{(x−1)}{n}$, 注意这里$L(x)$就是除法求商。

此时，公钥为$(n,g)$ ，私钥为$(λ,μ)$ 。

1.2.2 加密过程

对于明文$m$ ， $m∈Z_n$，选择随机数$r<n$, 加密过程为：

$c=g^mr^n(mod\;n^2)$ (公式1)

1.2.3 解密过程

对于密文 $c$ 解密过程为：

$$m=L(c^λmod\;n^2)μmod\;n=\frac{L(c^λmod\;n^2)}{L(g^λmod\;n^2)} (公式2)$$

1.3 正确性分析

1.3.1 离散对数性质

通过二项式定理，我们计算：

$(1+n)^x=\sum_{k=0}^{x}\begin{pmatrix} x \\ k \end{pmatrix} \quad n^k=1+nx+\begin{pmatrix} x \\ 2\end{pmatrix} n^2 + \text{higher powers of n}$

这表明：$(1+n)^x≡1+nx\;mod\;n^2$

因此，如果：$y=(1+n)^x\;mod\;n^2$

那么：$x≡\frac{y-1}{n}\;mod\;n$

从而：$L((1+n)^x\;mod\;n^2)≡x\;mod \;n$

1.3.1 解密

因为 $(p−1)|λ$,$(q−1)|λ$

所以 $λ=k_1(p−1)=k_2(q−1)$

由费马小定理可得：

\begin{cases}

g^λ=g{k_1(p−1)}≡1(mod;p) ,; (g^λ−1)|p &\

g^λ=g{k_2(q−1)}≡1(mod;q) , ;(g^λ−1)|q &

\end{cases}

所以 $(g^λ−1)|pq,g^λ≡1(mod\;n)$

所以 $g^λ(mod\;n^2)≡1(mod\;n)$

即 $g^λ(mod\;n^2)=n∗k_g+1(mod\;n);k_g<n$

所以 $L(g^λ(mod\;n^2))=k_g$

通过二项式定理可以得出: $(1+kn)^m≡knm+1(mod\;n^2)$

所以 $g^{mλ}=(1+k_gn)^m≡k_gnm+1(mod\;n^2)$, $r^{nλ}=(1+k_n)^n≡k_nn^2+1≡1(mod\;n^2)$

所以 $L(c^λmod\;n^2)=L(g^{mλ}r^{nλ}(mod\;n^2))=L(k_gnm+1)=mk_g$

所以(2)式 $\frac{L(c^λmod\;n^2)}{L(g^λmod\;n^2)}=\frac{mk_g}{k_g}≡m(mod\;n)$

1.3.2 同态加法

1. 两个密文的乘积将解密为对应的明文之和：

$D(E(n_1,r_1)·E(m_2,r_2)\; mod\;n^2)=m_1+m_2\; mod\;n$

证明：

$D(E(n_1,r_1)·E(m_2,r_2)\; mod\;n^2)=D(g^{m_1}·r_1^n·g^{m_2}·r_2^n)\;mod\;n^2=D(g^{m_1+m_2}·(r_1r_2)^n\;mod\;n^2=m_1+m_2)$

2. 一个密文与以$g$为底、明文为幂的数相乘将解密为对应明文之和

$D(E(m_1,r_1)·g^{m_2}\;mod\;n^2) = m_1+m_2\;mod\;n$

证明：

$$D(E(m_1,r_1)·g^{m_2}\;mod\;n^2) = D(g^{m_1}·r_1^n·g^{m_2}\;mod\;n^2)=D(g^{m_1+m_2}·r_1^n)\;mod\;n^2=m_1+m_2\;mod\;n$$

1.3.3 同态乘法

密文的明文幂将倍洁密文对应明文的乘积

$D(E(m_1,r_1)^k\;mod\;n^2)=km_1\;mod\;n$

证明：

$D(E(m_1,r_1)^k\;mod\;n^2)=D((g^{m_1}·r_1^n)^k)\;mod\;n^2=D(g^{km_1}·r_1^kn)\;mod\;n^2=km_1\;mod\;n$

2. 改进版Paillier

2.1 简介

参考论文：

• Jiang Z T, Liu J W, Wang Y M. Improvement on Paillier-Pointcheval probabilistic public-key encryption scheme[J]. Comput. Eng, 2008, 34(3): 38-39.

• Liang W, Yang Y, Yang C, et al. PDPChain: A consortium blockchain-based privacy protection scheme for personal data[J]. IEEE Transactions on Reliability, 2022.

2.2 算法过程

2.2.1 密钥产生

选取两个随机的大素数 $p,q$ ，计算 $n=p∗q$ 和 $\lambda=lcm(p−1,q−1)$， $lcm$ 为两个参数的最小公倍数。

选取$g=n+1$, $μ=\lambda^{-1}mod\;n$

函数 $L(x)$ 的定义如下 $L(x)=\frac{(x−1)}{n}$

此时，公钥为$(n)$ ，私钥为$(λ, μ)$ (这里λ, μ知其一则可计算出另一变量)。

2.2.2 加密过程

对于明文$m$ ， $m∈Z_n$，选择随机数$r<n$, 加密过程为:

$c=$(1+nm)$r^n(mod\;n^2)$ (公式3)

2.2.3 解密过程

对于密文 $c$ 解密过程为

$m=L(c^\lambda mod\;n^2)μmod\;n=$$\frac{L(c^\lambda mod\;n^2)}{\lambda \; mod\;n}$ (公式4)

2.3 正确性分析

2.3.1 加密

公式(3)中的1+mn代替了公式(1)中的$g^m$，我们接下来证明二者相等。

将$g=n+1$代入得到：$g^m=(n+1)^m\;mod\;n^2$

根据二项式定理可得：$g^m=(n+1)^m≡1+mn\;mod\;n^2$

由此可得公式(1)和(3)等价

2.3.2 解密

公式(2)与公式(4)不同点在于将$L(g^λmod\;n^2)$换成$\lambda mod\;n$，所以我们证明二者相等即可。

由$g=n+1$，可得：

$L(g^λmod\;n^2)=L((n+1)^λmod\;n^2)=L((1+n\lambda) mod\;n^2)=\frac{1+n\lambda-1}{n} mod\;n^2 =\lambda mod\;n^2=\lambda mod\;n$

3. 参考

1. Paillier算法简介
2. GCAC47 Paillier加法同态加密算法