安全椭圆曲线的ElGamal

Question

我只知道ElGamal属于基于DDH或CDH硬问题的注册会计师。

但是，如果我想证明ElGamal的CPA安全性，那么我应该基于什么困难的问题呢?DLP？

ElGamal算法：椭圆曲线的ElGamal

如果有相关文献的来源，会更好！非常感谢！！

Answer 1

但是，如果我想证明ElGamal的CPA安全性，那么我应该基于什么困难的问题呢？DLP？

很容易证明它与DDH问题是等价的。

将注册会计师的安全性降低到DDH：

给出一个公钥aG，以及明文P的可能加密，即X, Y；如果它实际上是ElGamal，那么X = bG, Y = abG + P用于一些随机的b。

然后我们检查aG, X, Y-P是否是DDH-三重奏；很容易看出，如果给我们一个ElGamal密文，那么它就是。

将DDH降低为CPA安全：

给出一个潜在的DDH-三重态X, Y, Z (如果它是三重态的话是aG, bG, abG )，那么我们选择一个任意的明文P，并将公钥X和密文Y, Z+P传递给我们的CPA-oracle；如果它说这是一种El Gamal加密，那么我们就说它是DDH-三重奏。