Paillier同态加密算法

作者: 雪落无留痕 | 来源:发表于2021-04-19 22:44 被阅读0次

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

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

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算法对称加密算法加密和解密使用相同的秘...