多密钥的公钥加密方案 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)$，可以用 $\text{lcm}(a,b)\cdot gcd(a,b)=a\cdot b$ 来计算
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 }\equiv 1(\mathrm{mod}n)$。 因此存在唯一的 $k\in {\mathbb{Z}}_n$ 使得：

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

证明

记 $n=pq$，且 $\lambda =\mathrm{lcm}(p-1,q-1)$。

因为 $x\in {\mathbb{Z}}_{n^2}^{\ast }$，所以 $gcd(x,n)=1$，从而 $xmodp\in {\mathbb{Z}}_p^{\ast }$ 且 $xmodq\in {\mathbb{Z}}_q^{\ast }$。

由费马小定理：

$$x^{p-1}\equiv 1(\mathrm{mod}p),x^{q-1}\equiv 1(\mathrm{mod}q)$$

又因为 $\lambda$ 同时是 $p-1$ 与 $q-1$ 的倍数，所以：

$$x^{\lambda }\equiv 1(\mathrm{mod}p),x^{\lambda }\equiv 1(\mathrm{mod}q)$$

由中国剩余定理（CRT）得到：

$$x^{\lambda }\equiv 1(\mathrm{mod}pq)(=(\mathrm{mod}n))$$

于是存在 $k\in \{0,1,\dots ,n-1\}$ 使得

$$x^{\lambda }=1+kn$$

把上式视为模 $n^2$ 的同余式即可写作 $x^{\lambda }\equiv 1+kn(\mathrm{mod}{n}^2)$。

因此（这里的 $L$ 函数只对形如 $1+n\cdot (\cdot )$ 的元素使用）

$$L(x^{\lambda })=\frac{x^{\lambda }-1}{n}\equiv k(\mathrm{mod}n)$$

证毕。

算法步骤：

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}$$

证毕。

加法同态

给定两条消息 $m_1,m_2$ :

$$Enc(m_1)=(A_1,B_1)=(g^{r_1},h^{r_1}(1+m_{1}n))$$$$Enc(m_2)=(A_2,B_2)=(g^{r_2},h^{r_2}(1+m_{2}n))$$

加法：

$$\begin{array}{rl}Enc(m_1)\oplus Enc(m_2)& =(A_1\cdot A_{2}mod{n}^2,B_1\cdot B_{2}mod{n}^2)\\ & =(g^{r_1+r_2}mod{n}^2,h^{r_1+r_2}(1+(m_1+m_2)n)mod{n}^2)\\ & =Enc(m_1+m_2)\end{array}$$

标量乘 $\to$ 幂运算 $\approx$ 乘法:

$$\begin{array}{rl}Enc(m{)}^k& =(A^{k}mod{n}^2,B^{k}mod{n}^2)\\ & =(g^{rk}mod{n}^2,h^{rk}(1+(mk)n)mod{n}^2)\\ & =Enc(m\cdot k)\end{array}$$

使用加法同态实现双方的乘法同态

假设有两个参与方：

1. 计算方 (Alice)：拥有密文 $Enc(a)$ 和 $Enc(b)$，以及公钥 $pk$。她想计算 $Enc(a\cdot b)$，但没有私钥。
2. 协助方 (Bob)：拥有公钥 $pk$ 和私钥 $sk$。

由于加法同态加密本身不支持直接的密文乘法（即 $Enc(a)\cdot Enc(b)\ne Enc(a\cdot b)$），需要通过交互协议来完成。

协议流程

1. 盲化 (Blinding/Masking) - Alice

计算方生成两个大的随机数 $r_1,r_2\in \mathbb{G}$，混淆原始密文：

$$\begin{array}{rl}Enc(a+r_1)& =Enc(a)\oplus Enc(r_1)\\ Enc(b+r_2)& =Enc(b)\oplus Enc(r_2)\end{array}$$

计算方将这两个掩盖后的密文发送给协助方。

2. 解密与计算 - Bob

协助方收到密文后，使用私钥 $sk$ 进行解密。由于引入了随机数 $r_1,r_2$，协助方只能看到掩盖后的值，无法得知 $a$ 和 $b$：

$$\begin{array}{rl}Dec(Enc(a+r_1))& =a+r_1\\ Dec(Enc(b+r_2))& =b+r_2\end{array}$$

协助方在明文空间计算这两个值的乘积，并将结果重新加密后发回给计算方：

$$\text{Result}=Enc((a+r_1)(b+r_2))$$

3. 去盲 (Unblinding) - Alice

计算方收到 $Enc((a+r_1)(b+r_2))$ 后，利用已知的 $r_1,r_2$ 和同态性质消除引入的随机项。

展开乘积公式：

$$(a+r_1)(b+r_2)=ab+a{r}_2+b{r}_1+r_1{r}_2$$

为了得到 $ab$，需要减去后三项：

$$ab=(a+r_1)(b+r_2)-a{r}_2-b{r}_1-r_1{r}_2$$

计算方利用标量乘同态性质（$Enc(m{)}^k=Enc(mk)$）计算这些中间项的负值密文：

1. 计算 $-a{r}_2$ 的密文：$Enc(-a{r}_2)=Enc(a{)}^{-r_2}$
2. 计算 $-b{r}_1$ 的密文：$Enc(-b{r}_1)=Enc(b{)}^{-r_1}$
3. 计算 $-r_1{r}_2$ 的密文：直接加密常数 $Enc(-r_1{r}_2)$

4. 最终聚合

计算方将所有部分通过同态加法聚合：

$$Enc(ab)=Enc((a+r_1)(b+r_2))\oplus Enc(-a{r}_2)\oplus Enc(-b{r}_1)\oplus Enc(-r_1{r}_2)$$

至此，计算方在未泄露 $a,b$ 的情况下，成功获得了 $Enc(a\cdot b)$。

多密钥的安全多方计算

各用户 $P_i$ 持有私有输入 $m_i$，分别用各自公钥 ${\text{pk}}_i$ 加密后上传至云服务器 C。要求在不泄露 $m_i$ 的前提下，计算函数 $f(m_1,...,m_n)$。

1. 初始化与上传

• 云服务器 S 执行 Setup，生成 $\text{PP}=(N,k,g)$，$\text{MK}=(p^{\prime },q^{\prime })$
• 广播 PP 给所有用户和云服务器 C
• 每个用户 $P_i$ 生成 $({\text{pk}}_i,{\text{sk}}_i)$，加密 $m_i$ 得到 $c_i=(A_i,B_i)$，上传至 C

此时，C 持有密文集合 $\{c_i={\text{Enc}}_{{\text{pk}}_i}(m_i){\}}_{i=1}^n$，但各密文使用不同公钥加密，无法直接同态运算。

2. 密文转换

步骤 A：C 对每个密文进行盲化

对每个 $c_i=(A_i,B_i)$，C 随机选择盲化因子 ${\tau }_i\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_N$，构造：

$${\tilde{m}}_i=m_i+{\tau }_{i}modN$$

但由于 C 无法解密，它利用 加法同态性 构造 ${\text{Enc}}_{{\text{pk}}_i}({\tilde{m}}_i)$ 如下：

• 生成 ${\text{Enc}}_{{\text{pk}}_i}({\tau }_i)=(g^{t_i},h_i^{t_i}(1+{\tau }_{i}N))$
• 计算：$${\tilde{c}}_i=c_i\oplus {\text{Enc}}_{{\text{pk}}_i}({\tau }_i)={\text{Enc}}_{{\text{pk}}_i}(m_i+{\tau }_i)$$

然后将 ${\tilde{c}}_i$ 发送给云服务器 S。

步骤 B：S 使用 MK 解密得到 ${\tilde{m}}_i$

S 利用主密钥 MK 和公钥 ${\text{pk}}_i$ 对 ${\tilde{c}}_i$ 执行 主密钥解密，得到：

$${\tilde{m}}_i=m_i+{\tau }_i\mathrm{mod}N$$

步骤 C：S 用统一公钥重新加密

S 生成一个 临时统一公钥 ${\text{pk}}^{\ast }=g^{a^{\ast }}$，并加密所有 ${\tilde{m}}_i$：

$$c_i^{\ast }={\text{Enc}}_{{\text{pk}}^{\ast }}({\tilde{m}}_i)$$

发回给 C。

步骤 D：C 去除盲化因子

C 已知 ${\tau }_i$，可构造 ${\text{Enc}}_{{\text{pk}}^{\ast }}(-{\tau }_i)$，并计算：

$${\text{Enc}}_{{\text{pk}}^{\ast }}(m_i)=c_i^{\ast }\oplus {\text{Enc}}_{{\text{pk}}^{\ast }}(-{\tau }_i)$$

现在，C 拥有所有 $m_i$ 在 同一公钥 ${\text{pk}}^{\ast }$ 下的密文，记为 $\{{\text{Enc}}_{{\text{pk}}^{\ast }}(m_i)\}$。

---

3. 函数计算

加法（直接利用同态性）：

$${\text{Enc}}_{{\text{pk}}^{\ast }}\left(\sum _{i=1}^n{m}_i\right)=\underset{i=1}{\overset{n}{⨁}}{\text{Enc}}_{{\text{pk}}^{\ast }}(m_i)$$

乘法（需交互）：

要计算 ${\text{Enc}}_{{\text{pk}}^{\ast }}(m_i{m}_j)$，由于 BCP 不是乘法同态，采用如下协议：

1. C 随机选择 $r_1,r_2\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_N$
2. 计算：$$\text{Enc}(a+r_1),\text{Enc}(b+r_2)$$
3. 发送给 S，S 解密得 $a+r_1,b+r_2$
4. S 计算 $(a+r_1)(b+r_2)=ab+a{r}_2+b{r}_1+r_1{r}_2$
5. S 加密该值并返回：$\text{Enc}((a+r_1)(b+r_2))$
6. C 本地计算：$$\text{Enc}(ab)=\text{Enc}((a+r_1)(b+r_2))\ominus \text{Enc}(a{r}_2)\ominus \text{Enc}(b{r}_1)\ominus \text{Enc}(r_1{r}_2)$$其中 $\text{Enc}(a{r}_2)=\text{Enc}(a{)}^{r_2}$

4. 密文转换

最终结果为 ${\text{Enc}}_{{\text{pk}}^{\ast }}(f(m_1,...,m_n))$，以下记为$En{c}_{\text{pk}}^{\ast }(Res)$ 。由于用户无 ${\text{sk}}^{\ast }$，需 C 与 S 再次交互，将结果 转换回可由用户联合解密的形式。

1. C 盲化密文 $(C,D)$:

   • 选择 $\tau \stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{Z}}_N$
   • 计算 ${\text{Enc}}_{{\text{pk}}^{\ast }}(\tau )$
   • 计算并发送给 S: $(C,D)=En{c}_{{\text{pk}}^{\ast }}(Res+\tau )=En{c}_{{\text{pk}}^{\ast }}(Res)\oplus En{c}_{{\text{pk}}^{\ast }}(\tau )$

2. S 解密, 得到 $z=res+\tau \leftarrow De{c}_{{\text{pk}}^{\ast }}(C,D)$

3. S 使用用户公钥 ${\text{pk}}_i$ 加密 $z$，得到 $En{c}_{{\text{pk}}_i}(z)$

4. C 去盲:

• 计算 ${\text{Enc}}_{{\text{pk}}_i}(-\tau )$
• 计算最终结果:

$$En{c}_{{\text{pk}}_i}(Res)=En{c}_{{\text{pk}}_i}(z)\oplus En{c}_{{\text{pk}}_i}(-\tau )$$

• 发送给用户 $En{c}_{{\text{pk}}_i}(Res)$