多密钥的公钥加密方案 BCP

类似于 $Paillier$, 这个方案是为了后面的 MPC 服务的。

BCP 是一种基于 Paillier 结构的双陷门公钥加密系统。它允许系统拥有一个主密钥（Master Key）和一个用户私钥（User Private Key）。

1. Setup

由可信第三方或分布式协议生成公共参数和主密钥：

1. 选择两个大素数 $p,q$ ，计算 $n=p\cdot q$
2. 计算 $\lambda =lcm(p-1,q-1)=gcd(p-1,q-1)\cdot (p-1)(q-1)$
3. 选择生成元 $g\in {\mathbb{Z}}_{n^2}^{\ast }$，使得 $g$ 的阶是 $n$ 的倍数（通常需满足 $gcd(L(g^{\lambda }mod{n}^2),n)=1$）
4. 计算 $\mu =L(g^{\lambda }mod{n}^2{)}^{-1}modn$。
   • 其中函数 $L(x)=\frac{x-1}{n}$

• 公共参数 (Params): $(n,n^2,g)$
• 主密钥 (MK): $(p,q,\lambda ,\mu )$

2. KeyGen

用户生成自己的公私钥对：

1. 用户随机选择私钥 $a\in {\mathbb{Z}}_{n^2}^{\ast }$
2. 计算公钥 $h=g^{a}mod{n}^2$

• 用户公钥 (PK): $h$
• 用户私钥 (SK): $a$

3. Encrypt

给定明文 $m\in {\mathbb{Z}}_n$ 和用户公钥 $h$：

1. 随机选择随机数 $r\in {\mathbb{Z}}_{n^2}^{\ast }$
2. 计算 $A=g^{r}mod{n}^2$
3. 计算 $B=h^r\cdot (1+m\cdot n)mod{n}^2$

• 密文 (Ciphertext): $C=(A,B)$

---

解密

BCP 方案支持两种解密方式。

方式一：使用用户私钥解密 (Exponent Decryption)

持有私钥 $a$ 的用户可以直接解密：

$$m=L\left(\frac{B}{A^a}mod{n}^2\right)$$

证明： 展开 $B$ 和 $A$：

$$\begin{array}{rl}\frac{B}{A^a}& =\frac{h^r\cdot (1+mn)}{(g^r{)}^a}mod{n}^2\\ & =\frac{(g^a{)}^r\cdot (1+mn)}{g^{ra}}mod{n}^2\\ & =\frac{g^{ar}\cdot (1+mn)}{g^{ar}}mod{n}^2\\ & =1+mnmod{n}^2\end{array}$$

应用 $L(x)$ 函数：

$$L(1+mn)=\frac{(1+mn)-1}{n}=\frac{mn}{n}=m$$

证毕。

方式二：使用主密钥解密 (Factor Decryption)

持有主密钥 $(p,q,\lambda ,\mu )$ 的一方（如监管者或 MPC 协议中的计算方）可以在不知道用户私钥 $a$ 的情况下解密。

核心性质： 对于任意 $x\in {\mathbb{Z}}_{n^2}^{\ast }$，有 $x^{\lambda }=1modn$。 在模 $n^2$ 下，有 Carmichael 定理的推广：

$$x^{\lambda }=1+n\cdot L(x^{\lambda })mod{n}^2$$

证明

Carmichael 定理：

对于任意 $x\in {\mathbb{Z}}_{n^2}^{\ast }$，有 $x^{\lambda (p-1,q-1)}=1modn$，这是显然的，$\because$ $\lambda (p-1,q-1)=\varphi (n)\ast gcd(p-1,q-1)$。

故而有 $x^{\lambda }=1+knmod{n}^2$，其中 $0\le k<n$。

所以 $L(x^{\lambda })=\frac{1+kn-1}{n}=kmodn$，证毕。

算法步骤：

1. 恢复随机数 $rmodn$：$$r^{\prime }=L(A^{\lambda })\cdot \mu modn$$
2. 恢复私钥 $amodn$：$$a^{\prime }=L(h^{\lambda })\cdot \mu modn$$
3. 计算中间项：$$\text{term}=L(B^{\lambda })\cdot \mu modn$$
4. 消除随机性：$$\mathrm{\Delta }=\text{term}-a^{\prime }\cdot r^{\prime }modn$$
5. 恢复明文：$$m=\mathrm{\Delta }\cdot L(g^{\lambda })\cdot {\lambda }^{-1}modn$$

详细证明：

Step 1: 展开 $L(A^{\lambda })$

$$A^{\lambda }=(g^r{)}^{\lambda }=(g^{\lambda }{)}^r=(1+nL(g^{\lambda }){)}^r=1+n\cdot r\cdot L(g^{\lambda })mod{n}^2$$

所以：

$$L(A^{\lambda })=r\cdot L(g^{\lambda })modn$$

乘以 $\mu =L(g^{\lambda }{)}^{-1}$ 后：

$$r^{\prime }=r\cdot L(g^{\lambda })\cdot L(g^{\lambda }{)}^{-1}=rmodn$$

Step 2: 展开 $L(h^{\lambda })$ 同理，因为 $h=g^a$：

$$L(h^{\lambda })=a\cdot L(g^{\lambda })modn\to a^{\prime }=amodn$$

Step 3: 展开 $L(B^{\lambda })$

$$\begin{array}{rl}{B}^{\lambda }& =(h^r\cdot (1+mn){)}^{\lambda }\\ & =(g^{ar}{)}^{\lambda }\cdot (1+mn{)}^{\lambda }\\ & =(g^{\lambda }{)}^{ar}\cdot (1+mn\lambda )\\ & =(1+nL(g^{\lambda }){)}^{ar}\cdot (1+nm\lambda )mod{n}^2\\ & =(1+n\cdot ar\cdot L(g^{\lambda }))\cdot (1+nm\lambda )mod{n}^2\\ & =1+n(arL(g^{\lambda })+m\lambda )mod{n}^2\end{array}$$

所以：

$$L(B^{\lambda })=arL(g^{\lambda })+m\lambda modn$$

乘以 $\mu$ 得到 term：

$$\text{term}=(arL(g^{\lambda })+m\lambda )\mu =ar+m\lambda \mu modn$$

Step 4: 计算 $\mathrm{\Delta }$

$$\begin{array}{rl}\mathrm{\Delta }& =\text{term}-a^{\prime }{r}^{\prime }\\ & =(ar+m\lambda \mu )-(a)(r)modn\\ & =m\lambda \mu modn\end{array}$$

Step 5: 恢复 $m$ 代码中最后计算 $m=\mathrm{\Delta }\cdot L(g^{\lambda })\cdot {\lambda }^{-1}$。 代入 $\mathrm{\Delta }$：

$$\begin{array}{rl}{m}_{\text{calc}}& =(m\lambda \mu )\cdot L(g^{\lambda })\cdot {\lambda }^{-1}\\ & =m\cdot (\lambda {\lambda }^{-1})\cdot (\mu L(g^{\lambda }))\\ & =m\cdot 1\cdot 1\\ & =mmodn\end{array}$$

证毕。