Crypto基础篇-同态加密

Paillier同态加密

密钥生成：

• 随机选择两个大素数$p,q$，满足$gcd(pq,(p-1)(q-1))=1$
• 计算$n = pq$，$\lambda =lcm(p-1,q-1)$
• 选择随机整数$g（g\in Z^*_{n^2}）$，定义$L(x)= \frac{x-1}{n}$，满足$gcd(L(g^\lambda \mod n^2),n)=1$
• 计算$\mu = (L(g^\lambda \mod n^2))^{-1}\mod n$
• 公钥为$(n,g)$，私钥为$(\lambda,\mu)$

二项定理：
$(1+kn)^m\equiv knm+1 \mod n^2$
此时有$g^\lambda\equiv 1\mod n$，$g^{n\lambda}\equiv 1 \mod n^2$

简化版：

• $g=n+1$
• $\lambda=\phi(n)=(p-1)(q-1)$
• $\mu = \phi(n)^{-1}\mod n$
  加密：
• 明文$m（0\leq m < n）$
• 选择随机数$r(0<r<n,r\in Z^*_{n^2})$，且$gcd(r,n)=1$
• 密文$c=g^mr^n\mod n^2$
  解密：
• 明文$m=L(c^{\lambda}\mod n^2)\mu \mod n$

性质：
$D(E(m_1,r_1)⋅E(m_2,r_2)\mod n^2)=m_1+m_2 \mod n$
$D(E(m_1,r_1)⋅g^{m_2}\mod n^2)=m_1+m_2 \mod n$
$D(E(m_1,r_1)^{m_2}\mod n^2)=m_1m_2\mod n$
$D(E(m_2,r_2)^{m_1}\mod n^2)=m_1m_2\mod n$
$D(E(m,r)^k\mod n^2)=km\mod n$
$D(E(m,r)⋅(1+n)^k\mod n^2)=m+k\mod n$

参考： 其他加密算法 | Lazzaro