Key exchange from discrete logarithm only

user4242

6/25/24, 12:37 AM

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?

2 + 1

discrete-logarithm

key-exchange

diffie-hellman

Marc Ilunga

6/25/24, 12:22 PM

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.

Score:2

Crypto

Daniel S

6/25/24, 9:32 AM

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.

+ 1

user4242

6/25/24, 10:19 AM

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.

Score:0

Crypto

user4242

6/25/24, 12:47 PM

Looking around some more, according to these lecture notes, 9.10, this is an open problem.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Key exchange from discrete logarithm only

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.