Paillier公钥密码体制是基于复合剩余问题构建的概率性公钥加密系统，具有同态特性和良好的安全性质
一、密钥生成
步骤：
- 选择两个大素数 \(p\) 和 \(q\)，计算 \(n = p \times q\)
- 计算卡迈克尔函数：\(\lambda(n) = \text{lcm}(p-1, q-1)\)
- 选择整数 \(g \in B\)，满足：
- \(\gcd(n, [g]_{n+1}) = 1\)
- \(\gcd(n, L(g^{\lambda(n)} \mod n^2)) = 1\)
- 其中 \(L(u) = \frac{u-1}{n}\)
密钥对：
- 公钥：\((n, g)\)
- 私钥：\((p, q)\)
二、加密过程
输入：明文 \(m \in [0, n-1]\)，公钥 \((n, g)\)
步骤：
- 选取随机数 \(r \in (0, n]\)
- 计算密文：\(c = g^m \cdot r^n \mod n^2\)
特点：
- 加密过程具有概率性（通过随机数 \(r\) 实现）
- 相同明文加密后得到不同密文
三、解密过程
输入：密文 \(c\)，私钥 \((p, q)\)
步骤：
- 验证 \(c < n^2\)
- 计算：
\(m = \frac{L(c^{\lambda(n)} \mod n^2)}{L(g^{\lambda(n)} \mod n^2)} \mod n\)
其中 \(L(u) = \frac{u-1}{n}\)
安全性分析
1. 单向性
- 条件：Paillier加密是单向的当且仅当\(Class[n]\)问题是困难的
- 含义：在没有私钥的情况下，从密文恢复明文在计算上是不可行的
2. 选择明文安全
- 条件：当且仅当\(CR[n]\)（复合剩余判定问题）是困难的
- 判定方法：给定两个明文 \(m_0\) 和 \(m_1\)，如果 \(c\) 是 \(m_0\) 的密文当且仅当 \(c \cdot g^{-m_0} \mod n^2\) 是一个n次剩余
3. 选择密文攻击
- 需要结合适当的填充方案（OAEP）来增强抗选择密文攻击能力
Paillier密码的特殊性质
1. 同态特性
Paillier密码具有加法同态性：
\(D(E(m_1) \cdot E(m_2) \mod n^2) = m_1 + m_2 \mod n\)
2. 陷门置换
- 可以构造陷门置换函数，将整数 \(w\) 映射到另一个整数
- 安全性基于\(RSA[n,n]\)求解的困难性
Paillier签名方案
密钥生成：
- 与加密方案相同，但需额外选择Hash函数 \(h: \mathbb{N} \rightarrow \{0,1\}^k \subseteq \mathbb{Z}_{n^2}^*\)
签名过程：
- 计算 \(h(m)\)
- 计算 \(s_1 = L(h(m)^{\lambda(n)} \mod n^2) \cdot L(g^{\lambda(n)} \mod n^2)^{-1} \mod n\)
- 计算 \(s_2 = g^{s_1} \cdot h(m)^{-s_1 \cdot n^{-1} \mod n} \mod n\)
- 签名为 \((s_1, s_2)\)
验证：
验证 \(s_2^n \equiv g^{s_1} \cdot h(m) \mod n^2\) 是否成立
与Damgard-Jurik方案的关系
Damgard-Jurik公钥加密是Paillier方案的泛化：
- 允许更灵活的加密指数
- 基于更一般的数论基础：设 \(s < p, q\)，则 \((1+n)\) 模 \(n^{s+1}\) 的阶为 \(n^s\)
实际应用考虑
- 密钥长度：通常需要2048位或更长的密钥以确保安全
- 性能优化：可使用中国剩余定理加速解密过程
- 安全性增强：建议结合适当的填充方案使用
Paillier公钥密码体制因其同态特性和可证明安全性，在电子投票、安全多方计算等隐私保护场景中有重要应用。