Paillier同态加密算法

作者: 十月里的男艺术家 | 来源:发表于2023-02-16 15:59 被阅读0次

Paillier同态加密算法
python3同态加密算法实现
Paillier同态加密算法
简单数学3：同态与同构的群及变换群
同态加密
近世代数理论基础14：同构定理
近世代数理论基础21：环的同态与同构
同态加密(1) GSW同态加密方案
IOS开发——各类加密算法总结（MD5,CHA,BASE64,A
常用加密算法

Paillier同态加密算法

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

$D(E(m_1)\cdot E(m_2))=m_1+m_2$

标量乘法同态，即标量k乘以

$D(k*E(m1)) = k*m1$

1. Paillier方案描述

原版Paillier方案于论文[1]中提出，下面对方案进行描述：

1.1 密钥生成

选两个大素数 $p, q$ , 需要满足条件 $gcd(pq, (p-1)(q-1))=1$ , 不满足就重新选择随机数；
计算 $n = pq, \lambda = lcm(p-1,q-1)$ ，这里 $lcm$ 表示最小公倍数（Least Common Multiple）；
定义 $L(x)= \left \lfloor \frac{x-1}{n} \right \rfloor$ , 这里除法后向下取整；
随机选取一个小于 $n^2$ 的正整数 $g$ ，并且存在 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n$ ，如果不存在这样的 $u$ ，则要重新选择 $g$ ，或者从第1步重新开始。

得到的公钥为 $(n, g)$ , 私钥为 $(\lambda, u)$

快速生成私钥

如果素数 $p, q$ 长度相等，则可以采用一种简化的方式来生成Paillier的公钥和私钥，第3、4步改为：

$g=n+1, \ \lambda = \phi(n), \ u=(\phi(n)-1）mod\ n$

其中 $\phi(n)$ 为欧拉函数，即 $\phi(n) = (p-1)*(q-1)$ 。

1.2 加密

明文为 $m, 0 < m < n$ ;
随机选择 $r$ , 满足 $0<r<n$ 且 $r \in Z_{n^2}^*$ , $r$ 和 $n$ 互质；
计算密文： $c=g^mr^n \ mod \ n^2$

1.3 解密

计算明文 $m=L(c^{\lambda} \ mod \ n^2)*u \ mod \ n$

2. Paillier加解密实例

生成密钥对：

随机选择素数 $p=13, q=17$
计算 $n=13*17=221$
$\lambda = lcm(p-1, q-1) = lcm(12, 16) = 48$
随机选择小于 $n^2 = 221^2$ 的正整数 $g=4886$
计算 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n = (L(4886^{48}mod\ 48841))^{-1} \ mod\ 221 =159$

则公钥为 $(n,g)=(221, 4886)$ ，私钥为 $(\lambda , u)=(48, 159)$ 。

假设要对消息 $m=123$ 进行加密，则加密过程：

随机选择 $r=666$ ，且 $r$ 和 $n$ 互素
计算加密结果 $c=g^m r^n mod n^2 = 4886^{123} * 666^{221} \ mod \ 48841 = 25889$

解密过程：

$m = L(c^{ \lambda } mod n^2) * u \ mod \ n=L(25889^{48} \ mod \ 48841) * 159 \ mod \ 221 = 123$

3. Paillier的设计思路

下面介绍一下 Paillier 加密方案的设计思路。

根据 Binomial theorem ，有：

$(1+n)^x = \sum_{k=0}^x {x \choose k} n^k = 1 + nx + {x \choose 2}n^2 + {\text{higher powers of }}n$

这意味着：

$(1+n)^x = 1 + nx \pmod {n^2}$

如果定义：

$y = (1+n)^x \pmod {n^2}$

那么：

$x = \frac{y-1}{n} \pmod {n^2}$

从而有：

$L((1+n)^x \bmod n^2) = x \pmod n$

这里 $L(x)= \left \lfloor \frac{x-1}{n} \right \rfloor$

4. Paillier具备“加同态”性质

加法同态

Paillier加密的两个密文消息相乘的结果解密后得到两个消息相加的结果。

对于两个密文 $c_1 \equiv g^{m_1}.r_1^n \bmod n^2 和 c_2 \equiv g^{m_2}.r_2^n \bmod n^2$

$c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \bmod n^2 \\ \Rightarrow c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \equiv g^{m_1+m_2}.(r_1.r_2)^n \bmod n^2$

其中 $r_1$ 和 $r_2$ 都是 $Z_{n^2}^*$ 中的元素，因此 $r_1r_2$ 也属于 $Z_{n^2}^*$ , 并具有相同的性质，所以 $c_1c_2$ 可以看作是 $m=m_1+m_2$ 加密的密文， $c_1*c_2$ 的解密结果为 $m$ 。

同态标量乘法

对于密文 $c_1$ 和标量 $k$ ，计算 $c = c_1^k \bmod n^2$

需要说明的是，对于 Paillier 加密方案，给出公钥和两个加密后的消息 $E(m_1)$ 和 $E(m_2)$ ，无法计算出 $m_1 * m_2$ 的密文。也就是说 Paillier 没有“乘同态”性质。

4.1 具备“乘同态”性质的加密方案（Unpadded RSA，ElGamal）

Unpadded RSA，ElGamal 加密方案都具备“乘同态”性质。

下面以 RSA 为例，介绍一下它的“乘同态”性质。我们知道对于 RSA，加密算法为 $E(m) = m^e \bmod n$ ，从而可以推出它的“乘同态”性质:

$\begin{aligned} E(m_1) \cdot E(m_2) & = m_1^e \cdot m_2^e \bmod n\\ &= (m_1 \cdot m_2)^e \bmod n \\ &= E(m_1 \cdot m_2) \end{aligned}$

总结

常见的同态加密算法中，Paillier算法和Benaloh算法仅满足加法同态，RSA算法和ElGamal算法只满足乘法同态，而Gentry算法则是全同态的。

参考

Paillier同态加密算法
Paillier同态加密算法 Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，...
python3同态加密算法实现
目前同态加密算法分为加法同态和乘法同态，而加法同态中最经典的是paillier算法，乘法同态中最经典的是rsa算法...
Paillier同态加密算法
Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即： ...
简单数学3：同态与同构的群及变换群
同态映射同态的映射就是能够保持运算的映射，即对于一个到的映射，中有运算，中有运算，如果同态的群如果上面的同...
同态加密
定义同态加密（Homomorphic Encryption）是一种特殊的加密方法，允许对密文进行处理得到仍然是加...
近世代数理论基础14：同构定理
同构定理同态的基本性质设是同态映射,,令为S在映射f下的像集,对,令为集合的原像引理：设是满同态,则有 1....
近世代数理论基础21：环的同态与同构
环的同态与同构同态映射定义：设R和是两个环,是到的一个映射,若,有 1. 2. 则称为同态映射注：等式左边的...
同态加密(1) GSW同态加密方案
所有的更新都放在我的博客中, 本文地址为https://lingeros-tot.github.io/2019/0...
IOS开发——各类加密算法总结（MD5,CHA,BASE64,A
一.MD5加密算法二.sha1加密算法三.base64加密算法四.AES 256加密算法五.加密算法分析 ...
常用加密算法
1 常用加密算法常用加密算法有对称加密算法、非对称加密算法、Hash算法对称加密算法加密和解密使用相同的秘...