Paillier对RSA

Question

我在想，除了Pailliers是加性同态和RSA乘性之外，选择Paillier算法是否有主要的优缺点？

Answer 1

Paillier密码系统具有特定明文可能有许多不同密文的内置特性，这使得它对各种各样的密码攻击更加“开箱即用”。这是由于在加密中注入了额外的随机性，由于二次残差特性，加密可以用密钥进行删除。在实现中，RSA可以通过填充或其他方案实现类似的效果，但在Pallier中，它存在于算法的基础上，即所谓的“教科书”版本，而RSA“教科书”版本的情况并非如此。回想一下，pailler加密函数用于消息$m$、$r\in_R\mathbb{Z}_n$和标准值$$Enc(M)=g^mr^n^n^2$，因此每个消息$m$可能有许多同样有效的密文，这取决于$n$的大小和其中一些值之间的可分性关系。此外，为了安全起见，在RSA算法中添加填充以提高安全性，也会破坏乘法同态。下面是一个纸，它更深入地讨论了其中的一些细节。

Answer 2

当需要同态加密时，不应使用RSA。除非我们需要同态加密，否则没有理由使用Paillier。

RSA可以是语义安全，也可以是同态，而不是两者兼而有之。教科书RSA (密码文本只是$c=m^e\bmod N$)具有多重同态性，但存在一个主要缺陷:对纯文本$m$的猜测可能会被琐碎地检查，这通常是一种灾难(想想类卷上的名称，或者商品的价格)。在实际应用中，它使用的是RSA，其中$m$是在加密之前转换的，加上了随机性(如RSAES-OAEP)，这是安全的，但完全失去了同态性质。

相比之下，Paillier加密在语义上是安全的，并且是加性的同态。要付出的代价是一个更大的密码(在同等安全条件下是RSA的两倍大)，比RSA要昂贵得多，解密成本要高得多。