同态加密---Paillier算法

Paillier算法分析

本文参考知乎上一篇关于paillier算法的分析，纠正了一点错误，推理过程更加详细。

证明：

因为

λ = l c m ( p − 1 , q − 1 ) λ = lcm(p-1,q-1) λ=lcm(p−1,q−1)

所以

p − 1 ∣ λ ， q − 1 ∣ λ = > λ = a ( p − 1 ) = b ( q − 1 ) p-1|λ ，q-1|λ => λ = a(p-1) = b(q-1) p−1∣λ，q−1∣λ=>λ=a(p−1)=b(q−1)

由费马小定理可得

g λ = g a ( p − 1 ) ≡ 1 m o d p = > p ∣ g λ − 1 g^λ=g^{a(p-1)}\equiv1modp => p|g^\lambda-1 gλ=ga(p−1)≡1modp=>p∣gλ−1

同理

g λ = g b ( q − 1 ) ≡ 1 m o d p = > q ∣ g λ − 1 g^λ=g^{b(q-1)}\equiv1modp => q|g^\lambda-1 gλ=gb(q−1)≡1modp=>q∣gλ−1

因为p、q互素【见定理1】

所以

p q ∣ g λ − 1 = > n ∣ g λ − 1 = > g λ ≡ 1 m o d n = > g λ = k 1 n + 1 pq|g^\lambda-1 => n|g^\lambda-1 => g^\lambda\equiv1modn => g^\lambda=k_1n+1 pq∣gλ−1=>n∣gλ−1=>gλ≡1modn=>gλ=k1​n+1

同理

r λ = k 2 n + 1 r^\lambda=k_2n+1 rλ=k2​n+1

c λ = ( g m r n ) λ m o d ( n 2 ) = g m λ m o d ( n 2 ) . r n λ m o d ( n 2 ) = ( k 1 n + 1 ) m m o d ( n 2 ) . ( k 2 n + 1 ) n m o d ( n 2 ) c^\lambda=(g^mr^n)^\lambda mod(n^2)=g^{m\lambda}mod(n^2).r^{n\lambda}mod(n^2)=(k_1n+1)^mmod(n^2).(k_2n+1)^nmod(n^2) cλ=(gmrn)λmod(n2)=gmλmod(n2).rnλmod(n2)=(k1​n+1)mmod(n2).(k2​n+1)nmod(n2)

有以下性质

（ k n + 1 ) m o d ( n 2 ) = k n + 1 （ k n + 1 ) 2 m o d ( n 2 ) = 2 k n + 1 （ k n + 1 ) 3 m o d ( n 2 ) = 3 k n + 1 . . . （ k n + 1 ) m m o d ( n 2 ) = m k n + 1 （kn+1)mod(n^2) =kn+1\\ （kn+1)^2mod(n^2) =2kn+1\\ （kn+1)^3mod(n^2) =3kn+1\\ ...\\ （kn+1)^mmod(n^2) =mkn+1 （kn+1)mod(n2)=kn+1（kn+1)2mod(n2)=2kn+1（kn+1)3mod(n2)=3kn+1...（kn+1)mmod(n2)=mkn+1

所以

c λ = ( m k 1 n + 1 ) m o d ( n 2 ) . ( k 2 n 2 + 1 ) m o d ( n 2 ) = ( m k 1 n + 1 ) m o d ( n 2 ) c^\lambda=(mk_1n+1)mod(n^2).(k_2n^2+1)mod(n^2)=(mk_1n+1)mod(n^2) cλ=(mk1​n+1)mod(n2).(k2​n2+1)mod(n2)=(mk1​n+1)mod(n2)

所以

L ( c λ m o d ( n 2 ) ) L ( g λ m o d ( n 2 ) ) = m k 1 n n k 1 n n = m \frac{L(c^\lambda mod(n^2))}{L(g^\lambda mod(n^2))}=\frac{\frac{mk_1n}{n}}{\frac{k_1n}{n}}=m L(gλmod(n2))L(cλmod(n2))​=nk1​n​nmk1​n​​=m

加法同态性质分析

对明文 m 1 m_1 m1​和 m 2 m_2 m2​加密后，分别得到

E ( m 1 ) = g m 1 r 1 n m o d ( n 2 ) E ( m 2 ) = g m 2 r 2 n m o d ( n 2 ) E(m_1)=g^{m_1}r_1^nmod(n^2)\\ E(m_2)=g^{m_2}r_2^nmod(n^2)\\ E(m1​)=gm1​r1n​mod(n2)E(m2​)=gm2​r2n​mod(n2)

那么

E ( m 1 ) . E ( m 2 ) = g ( m 1 + m 2 ) ( r 1 . r 2 ) n = E ( m 1 + m 2 ) E(m_1).E(m_2) = g^{(m_1+m_2)}(r_1.r_2)^n=E(m_1+m_2) E(m1​).E(m2​)=g(m1​+m2​)(r1​.r2​)n=E(m1​+m2​)

证明过程使用到的定理:

1.费马小定理：

2.定理1

3.定理2