Paillier同态加密算法

2021-04-19 本文已影响0人雪落无留痕

Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即：
$D(E(m_1)\cdot E(m_2))=m_1+m_2$

算法描述

密钥生成

选两个大素数 $p, q$ , 保证 $gcd(pq, (p-1)(q-1))=1$
计算 $n = pq$ , $\lambda = lcm(p-1,q-1)$
定义 $L(x)=\frac{x-1}{n}$ , 这里分式是除法
随机选取一个小于 $n^2$ 的正整数 $g$ ，并且存在 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n$
公钥为 $(n, g)$
私钥为 $(\lambda, u)$

快速生成私钥

在密钥相同的情况下，可以快速生成密钥：

$g=n+1, \lambda = \phi(n), u=(\phi(n)-1）mod\ n$ , $\phi(n)$ 为欧拉函数，即 $\phi(n) = (p-1)*(q-1)$

加密

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

解密

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

加法同态

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

对于两个密文 $c_1\equiv g^{m_1}\cdot r_1^n mod\ n^2$ 和 $c_2 \equiv g^{m_2}\cdot r_2^n mod\ n^2$
$c_1\cdot c_2 \equiv g^{m_1}\cdot g^{m_2}\cdot r_1^n\cdot r_2^n mod\ n^2 \\ \Rightarrow c_1\cdot c_2\equiv g^{m_1}\cdot g^{m_2}\cdot r_1^n\cdot r_2^n\equiv g^{m_1+m_2}\cdot (r_1\cdot r_2)^n mod\ n^2$
其中 $r_1$ 和 $r_2$ 都是 $\mathbb{Z}_{n^2}^*$ 中的元素，因此 $r_1\cdot r_2$ 也属于 $\mathbb{Z}_{n^2}^*$ , 并具有相同的性质，所以 $c_1\cdot c_2$ 可以看作是 $m=m_1+m_2$ 加密的密文， $c_1\cdot c_2$ 的解密结果为 $m$ 。

总结

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

参考

https://en.wikipedia.org/wiki/Paillier_cryptosystem

https://blog.csdn.net/sinianluoye/article/details/82855059

http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf

上一篇下一篇

猜你喜欢

热点阅读