Paillier's cryptosystem revisited
Paillier's cryptosystem revisited
复制标题
DOI：
10.1145/501983.502012
复制
发表时间：
2001-11
期刊：
影响因子：
--
通讯作者：
D. Catalano;R. Gennaro;Nick Howgrave-Graham;Phong Q. Nguyen
中科院分区：
文献类型：
--
作者：
D. Catalano;R. Gennaro;Nick Howgrave-Graham;Phong Q. Nguyen
我们重新检查Paillier的密码系统，并表明，通过选择一个特定的离散对数基g，并通过引入一个替代的解密过程，我们可以扩展该计划，以允许一个任意的指数e而不是N。低指数的使用大大提高了该方案的效率。语义安全性基于一个新的判定假设，即判定一个元素是否是模N2的“小”e次剩余的困难性。我们还展示了如何利用Paillier的原始密码体制构造陷门承诺方案。这个新方案在信息理论上是私有的，并且具有计算约束力（在假设指数为N的RSA函数很难求逆的情况下，该属性成立）。这种新的承诺方案的一个新特性是，在知道想要提交的消息之前，大部分工作可以离线完成。一旦消息已知，只需要两次乘法。这是第一个陷门承诺方案，这种在线离线效率的属性，这也是长度保持。
We re-examine Paillier's cryptosystem, and show that by choosing a particular discrete log base g, and by introducing an alternative decryption procedure, we can extend the scheme to allow an arbitrary exponent e instead of N. The use of low exponents substantially increases the efficiency of the scheme. The semantic security is now based on a new decisional assumption, namely the hardness of deciding whether an element is a "small" e-th residue modulo N2.We also show how to use Paillier's original cryptosystem to build a trapdoor commitment scheme. This new scheme is information-theoretically private, and computationally binding (this property holds under the assumption that the RSA function with exponent N is hard to invert). A novel property of this new commitment scheme is that most of the work can be done offline before knowing the message one wants to commit to. Once the message is known only two multiplications are required. This is the first trapdoor commitment scheme with this online-offline efficiency property which is also length-preserving.