Paillier 同态加密算法
Paillier加密是一种公钥加密算法,基于复合剩余类的困难问题。其满足于加法同态,即密文相乘等于明文相加,即: $$D(E(m_1)\cdot E(m_2))=m_1+m_2$$
在描述具体方案之前,我们先定义加法PHE。首先列举方案具有的所有算法。
KeyGen():密钥生成算法。用于产生加密数据的公钥PK(Public Key)和私钥SK(Secret Key),以及一些公开常数PP(Public Parameter); Encrypt():加密算法。使用PK对用户数据Data进行加密,得到密文CT(Ciphertext); Decrypt():解密算法。用于解密得到数据原文PT(Plaintext)。
HE除了加解密以外,还具有在密文上进行处理的能力,所以还应拥有“处理”算法。对于加法PHE,支持的算法有同态加以及同态标量乘(标量乘法可看作多次加法)。
Add():同态加算法。输入两个CT进行同态加运算。 ScalaMul():同态标量乘算法。输入一个CT和一个标量PT,计算CT的标量乘结果。
原版Paillier方案于论文[1]中提出,下面对方案进行描述:
密钥生成
公钥为$$(n, g)$$, 私钥为$$(\lambda, u)$$
快速生成私钥
$$g=n+1, \lambda = \phi(n), u=(\phi(n)-1)mod\ n, \phi(n) $$为欧拉函数,即$$\phi(n) = (p-1)*(q-1)$$
加密
解密
加法同态
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$$和$$r2$$都是$$ Z{n^2}^$$中的元素,因此$$r_1r2$$也属于$$ Z{n^2}^$$, 并具有相同的性质,所以 $$c_1c_2$$可以看作是$$m=m_1+m_2$$加密的密文,$$c_1*c_2$$的解密结果为 $$m$$。
常见的同态加密算法中,Paillier算法和Benaloh算法仅满足加法同态,RSA算法和ElGamal算法只满足乘法同态,而Gentry算法则是全同态的。
论文:https://link.springer.com/chapter/10.1007/3-540-48910-X_16
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!