Diffie-Hellman key exchange is sometimes informally said to be hard under the discrete logarithm assumption in the chosen group. But if I am reading literature correctly, it actually uses a stronger assumption on the group and that's the assumption of Decisional Diffie-Hellman. Is there a key exchange whose SK-security is based solely on the hardness of discrete logarithm problem? Are there any other security notions/caveats to look out for in such a different key exchange?
1
-
$\begingroup$ It's hard to imagine an (A)KE from Dlog only. In most construction, à Diffie Hellman like operation is needed to obtain a fresh key/ or authente. Therefore, at least CDH is needed or any other Oracle DH assumption. In a group where Dlog would be (tightly) equivalent to CDH. I suppose, one can say the security is based on Dlog. $\endgroup$– Marc IlungaJun 25 at 12:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The difficulty ranking from hardest to easiest is discrete logarithm, computational Diffie-Hellman, decisional Diffie-Hellman. Consequently any security property that relies on the hardness of the decisional Diffie-Hellman problem can be solved if discrete logarithms can be efficiently calculated.
Different security properties of key exchanges can depend on different problems. For example in the classic El Gamal encryption scheme, private key recovery is as hard as the discrete logarithm problem, plaintext recovery is as hard as the computational Diffie-Hellman problem and distinguishing ciphertext is as hard as the decisional Diffie-Hellman problem.
-
$\begingroup$ I guess what I am thinking about is plaintext recovery given I am thinking of SK-security of the key exchange, so my question becomes, is there a key exchange where instead of computational Diffie-hellman, (partial) plaintext recovery becomes discrete log. $\endgroup$– IlkJun 25 at 10:19
$\begingroup$
$\endgroup$
Looking around some more, according to these lecture notes, 9.10, this is an open problem.