Paillier同态加密

Paillier同态加密算法以及其正确性与安全性分析

万里烟

1813人浏览 · 2023-06-26 10:28:00

万里烟 · 2023-06-26 10:28:00 发布

一：概述

Paillier同态加密最著名的半同态加密方案，其是一个支持加法 PHE 的公钥密码系统，由 Paillier 在 1999 年的 eurocrypt 上首次提出，之后又在 PKC01 提出了简化版本，是当前 Paillier 方案的最优方案。

其基于复合剩余类的困难问题。满足加法同态，即密文相乘等于明文相加：

$D(E(m_{_{1}})\cdot E(m_{_{2}}))=m_{_{1}}+m_{_{2}}$

满足标量乘法同态，即

$D(E(m_{1})^{k})=k\ast m_{1}$

二：方案描述

密钥生成

选择两个长度相等的大素数p和q，满足gcd[pq,(p-1)(q-1)]=1
计算 $n=pq$ 和 $\lambda =lcm(p-1,q-1)$ ，lcm表示最小公倍数
选择一个随机数 $g\leftarrow Z_{n^{2}}^{\ast }$
定义函数 $L(x)=\frac{{x-1}{}}{n}$ ，计算 $\mu =[L(g^{\lambda }mod(n^{2})]^{^{-1}}mod (n)$
输出公钥 $PK=(n,g)$ ，私钥 $SK=(\lambda ,\mu )$

加密

输入明文消息m，满足0≤m<n
选择随机数 $r\leftarrow Z_{n^{2}}^{\ast }$ ，满足0≤r<n
计算密文 $c=g^{m}r^{n}mod(n^{2})$

解密

输入密文c，满足 $c\leftarrow Z_{n^{2}}^{\ast }$
计算明文 $m=[L(c^{\lambda }mod(n^{2}))]\cdot \mu mod(n)$

同态加法

对于密文 $c_{1},c_{2}$ ，计算 $c=c_{1}\cdot c_{2}mod(n^{2})$

同态标量乘法

对于密文 $c_{1}$ 和标量k，计算 $c=c_{1}^{k}mod(n^{2})$

三：正确性和安全性

加解密正确性

$Decrypt(c)=L(c^{\lambda }mod(n^{2}))\cdot \mu =L((g^{m}r^{n})^{\lambda }mod(n^{2}))\cdot \lambda ^{-1}=L((g^{m\lambda }mod(n^{2})))\cdot \lambda ^{-1}=\lambda \cdot m\cdot \lambda ^{-1}=mmod(n)$

具体分析，参考https://snowolf0620.xyz/index.php/crypto/459.html

同态加法正确性

$Decrypt(c_{1}\cdot c_{2}mod(n^{2}))=Decrypt(g^{m_{1}}r^{n}\cdot g^{m_{2}}r^{n}mod(n^{2}))=Decrypt(g^{m_{1}+m_{2}}(r^{2})^{n})=m_{1}+m_{2}$

因为 $r_{1},r_{2}$ 都是 $Z_{n^{2}}^{\ast }$ 中的元素，所以 $r_{1}r_{2}$ 也属于 $Z_{n^{2}}^{\ast }$ ，并具有相同的性质

同态标量乘法的正确性

$Decrypt(c_{1}^{a}mod(n^{2}))=Decrypt(g^{m_{1}a}r^{n}mod(n^{2}))=m_{1}a$

安全性

方案满足加密方案的标准安全定义：语义安全，也即在 CPA 下密文不可区分性（IND-CPA），直观的说就是密文不会泄露关于明文的任何信息，方案可归约到判定性合数剩余假设（DCRA，Decisional Composite Residuosity Assumption，给定合数 n 和整数 z，判定 z 是否在 $n^{2}$ 下是否是 n次剩余，目前暂未被攻破）

四：同态算法对比

同态加密更具其同态完备性不同可以分为全同态和部分同态，所谓全同态就是指加密方案支持乘法和加法同态，部分同态则是指其只满足加法或者乘法同态。Paillier就是具备良好的加法同态的部分同态加密算法，除了Paillier之外，还有支持乘法同态的RSA和EIGamal算法，以及支持比特异或同态的Goldwasser Micali算法。下表1对目前经典的三种同态加密方案从计算复杂度、安全性、同态性三个方面进行了对比。

同态加密算法	计算复杂度	原理	安全性	同态性
Paillier算法	较低	判断复合剩余类困难性	强	加法同态、明文乘法同态
RSA 算法	较低	分解大素数	较弱	乘法同态
Gentry 算法	高	离散子集求和问题	强	加法同态，乘法同态