Paillier 同态加密算法

  • alphjon
  • 更新于 2022-11-28 17:28
  • 阅读 3669

Paillier 同态加密算法

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

1 加法同态加密定义

在描述具体方案之前,我们先定义加法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的标量乘结果。

2 Paillier方案描述

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

密钥生成

  1. 选两个大素数$$p, q$$ , 保证$$gcd(pq, (p-1)(q-1))=1$$,且满足$$p,q$$长度相等。
  2. 计算 $$n = pq, \lambda = lcm(p-1,q-1)$$, 这里lcm表示最小公倍数。
  3. 定义$$L(x)=\frac{x-1}{n}$$, 这里分式是除法
  4. 随机选取一个小于$$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)$$

加密

  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}.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

点赞 2
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
alphjon
alphjon
江湖只有他的大名,没有他的介绍。