Paillier加法同态加密
基础知识
-
算术基本定理（唯一分解定理）：任何大于１的自然数，都可以唯一分解成有限个质数的乘积，记为 n = p 1 a 1 p 2 a 2 ⋯ p k a k = Π i = 1 k p i a i n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}=\Pi_{i=1}^k p_i^{a_i} n=p1a1p2a2⋯pkak=Πi=1kpiai，其中 p i p_i pi为素数， a i a_i ai为正整数。
-
欧拉函数：计算不大于n且与n互素的正整数的个数，用φ(n)表示。这些正整数的集合记为 Z n ∗ \mathbb{Z}_n^* Zn∗，则 φ ( n ) = ∣ Z n ∗ ∣ φ(n)=|\mathbb{Z}_n^*| φ(n)=∣Zn∗∣。
-
引理一：若 p p p为素数，则 Z p = Z p ∗ \mathbb{Z}_p = \mathbb{Z}_p^* Zp=Zp∗，且 φ ( p ) = p − 1 φ(p)=p-1 φ(p)=p−1。
证明：
-
引理二：若 p p p为素数，任一整数r，则 φ ( p r ) = p r − 1 φ ( p ) = p r − 1 ( p − 1 ) φ(p^r)=p^{r-1} \varphi(p) = p^{r-1}(p-1) φ(pr)=pr−1φ(p)=pr−1(p−1)。
证明：
-
引理3：设 m = m 1 m 2 m=m_1 m_2 m=m1m2，若 m 1 m_1 m1和 m 2 m_2 m2互素且均为大于1的整数，则 φ ( m ) = φ ( m 1 ) φ ( m 2 ) φ(m)=φ(m_1) φ(m_2) φ(m)=φ(m1)φ(m2)。
证明：证明过程较长，可参考这里。 -
引理4（引理3的扩展通用形式）： φ ( x ) = x Π i = 1 k ( 1 − 1 p i ) φ(x)=x \Pi_{i=1}^k (1-\frac{1}{p_i}) φ(x)=xΠi=1k(1−pi1)，其中 x > 1 x>1 x>1， p i p_i pi为 x x x的所有素因数。
证明：根据算术基本定理， x = p 1 a 1 p 2 a 2 ⋯ p k a k = Π i = 1 k p i a i x=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}=\Pi_{i=1}^k p_i^{a_i} x=p1a1p2a2⋯pkak=Πi=1kpiai；显然 p i p_i pi两两之间互素，易证若干素数的幂方乘积与另外若干不同素数的幂方乘积互素；根据引理3， φ ( x ) = Π i = 1 k φ ( p i a i ) φ(x)=\Pi_{i=1}^k φ(p_i^{a_i}) φ(x)=Πi=1kφ(piai)；根据引理2， φ ( x ) = Π i = 1 k [ p i a i − 1 ( p i − 1 ) ] = Π i = 1 k [ p i a i ( 1 − 1 p i ) ] = x Π i = 1 k ( 1 − 1 p i ) φ(x)=\Pi_{i=1}^k [p_i^{a_i-1}(p_i -1)] = \Pi_{i=1}^k [p_i^{a_i}(1-\frac{1}{p_i})] = x \Pi_{i=1}^k (1-\frac{1}{p_i}) φ(x)=Πi=1k[piai−1(pi−1)]=Πi=1k[piai(1−pi1)]=xΠi=1k(1−pi1)。 -
欧拉定理：正整数n， a ∈ Z n a \in \mathbb{Z}_n a∈Zn，若a与n互素，即 a ∈ Z n ∗ a \in \mathbb{Z}_n^* a∈Zn∗，则 a φ ( n ) ≡ 1 m o d n a^{\varphi(n)} \equiv 1 \mod n aφ(n)≡1modn。
-
引理5（乘法逆元）：根据欧拉定理， a φ ( n ) ≡ 1 m o d n a^{\varphi(n)} \equiv 1 \mod n aφ(n)≡1modn，则有 a a φ ( n ) − 1 ≡ 1 m o d n a a^{\varphi(n)-1} \equiv 1 \mod n aaφ(n)−1≡1modn，因为 a a − 1 ≡ 1 m o d n a a^{-1} \equiv 1 \mod n aa−1≡1modn，显然乘法逆元必定存在，且 a − 1 = a φ ( n ) − 1 a^{-1} = a^{\varphi(n)-1} a−1=aφ(n)−1。
-
费马小定理（欧拉定理的特例）：大素数p， a ∈ Z p a \in \mathbb{Z}_p a∈Zp，显然 Z p = Z p ∗ \mathbb{Z}_p = \mathbb{Z}_p^* Zp=Zp∗，则有 a φ ( p ) = a p − 1 ≡ 1 m o d p a^{\varphi(p)} = a^{p-1} \equiv 1 \mod p aφ(p)=ap−1≡1modp，即 a p ≡ a m o d p a^{p} \equiv a \mod p ap≡amodp。
-
二项式定理：泰勒展开 y = ( 1 + n ) x = ∑ k = 0 x C x k n k = 1 + n x + C x 2 n 2 + 更 高 阶 可 以 被 n 2 整 除 的 部 分 y = (1+n)^x = \sum_{k=0}^x C_x^k n^k = 1+nx+ C_x^2 n^2 + 更高阶可以被n^2整除的部分 y=(1+n)x=∑k=0xCxknk=1+nx+Cx2n2+更高阶可以被n2整除的部分，显然 ( 1 + n ) x ≡ 1 + n x m o d n 2 (1+n)^x \equiv 1+nx \mod n^2 (1+n)x≡1+nxmodn2。显然 y − 1 ≡ n x m o d n 2 y-1 \equiv nx \mod n^2 y−1≡nxmodn2，根据同余定理，同÷n， x ≡ y − 1 n m o d n x \equiv \frac{y-1}{n} \mod n x≡ny−1modn。故在Paillier方案中，会构造函数 L ( y ) = y − 1 n L(y)=\frac{y-1}{n} L(y)=ny−1，可得 L ( y m o d n 2 ) ≡ x m o d n L(y \mod n^2) \equiv x \mod n L(ymodn2)≡xmodn。
Paillier密码系统
-
**生成：******()⟶(pk, sk)；
随机选取两个独立的大素数 p 和 q，且满足 ????????????(????????, (???? − 1)(???? − 1)) = 1，使得p 和 q长度相当。
计算 n =????????，???? = ????????????(???? − 1, ???? − 1)，随机选取 g ∈ Z n 2 ∗ g \in \mathbb{Z}_{n^2}^* g∈Zn2∗，简单起见，不如选择 g = n + 1 g=n+1 g=n+1，则令公钥 ???????? = (n, ????)，私钥 ???????? = (????)。 -
加密算法：Encryption(pk, m)⟶c；
随机选择 r ∈ Z n ∗ r \in \mathbb{Z}_{n}^* r∈Zn∗，显然 r ∈ Z n 2 ∗ r \in \mathbb{Z}_{n^2}^* r∈Zn2∗同样成立，计算密文 c = g m r n m o d n 2 c = g^m r^n \mod n^2 c=gmrnmodn2。 -
解密算法：Decryption(sk, c)⟶ m；
令函数 L ( x ) = x − 1 n L(x)=\frac{x-1}{n} L(x)=nx−1，可以计算明文 m = L ( c λ m o d n 2 ) L ( g λ m o d n 2 ) m o d n m = \frac{L(c^{\lambda} \mod n^2)}{L(g^{\lambda} \mod n^2)} \mod n m=L(gλmodn2)L(cλmodn2)modn。 -
正确性证明：
( r n λ ) ≡ 1 m o d n 2 (r^{n \lambda}) \equiv 1 \mod n^2 (rnλ)≡1modn2利用Carmichael定理证明，如下：
-
加法同态性质：
-
扩展至批量乘法（常数与明文相乘等同于密文的常数次幂）：
( E ( m 1 ) ) k = ( g m 1 r n ) k m o d n 2 = g k × m 1 ( r k ) n m o d n 2 = E ( k × m 1 ) (E(m_1))^k = (g^{m_1} r^n)^k \mod n^2 = g^{k \times m_1} (r^k)^n \mod n^2 = E(k \times m_1) (E(m1))k=(gm1rn)kmodn2=gk×m1(rk)nmodn2=E(k×m1)。