Paillier同态加密算法

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

算法描述

密钥生成

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

快速生成私钥

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

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

加密

  1. 明文为m , 0 < m < n；

  2. 随机选择 r, 满足 0<r<n 且 r\in Z_{n^2}^*, r 和 n互质；

  3. 计算密文： c = g^mr^n mod\ n^2

解密

  1. 计算明文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

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • BCP加密算法复现记录
    1.BCP算法简介 BCP加密算法是由Bresson,Catalano,Pointcheval三个人于2003提出...
    不懂球的2大业阅读 4,789评论 7赞 3
  • 区块链加密算法简介
    密码学相关的安全技术在整个信息技术领域的重要地位无需多言。如果没有现代密码学和信息安全的研究成果，人类社会根本无法...
    颍水书生阅读 1,616评论 0赞 2
  • PHP加密算法
    加密技术的重点是加密算法，加密算法主要分为三类： 对称加密 非对称加密 不可逆加密 对称加密算法 加密过程： 将明...
    飞越_7666阅读 1,254评论 0赞 0
  • PHP加密算法
    加密概要 在密码学中，加密（英语：Encryption）是将明文信息改变为难以读取的密文内容，使之不可读的过程。只...
    Gundy_阅读 767评论 2赞 9
  • 同态加密(1) GSW同态加密方案
    所有的更新都放在我的博客中, 本文地址为https://lingeros-tot.github.io/2019/0...
    NeptuneCS阅读 3,503评论 0赞 3

友情链接更多精彩内容