I'm looking into the Diffie-Hellman key exchange paper (New Directions in Cryptography, 1976) as part of a series of classic papers in Cryptography for my Ph.D and I was wondering if someone could give a reason for something that has always seemed very strange to me.

ElGamal seems like a natural thing to immediately try, so it seems odd that there was a nine year gap between this paper and the introduction of ElGamal (to the best of my knowledge, 1985). Was there a theoretical reason for this? Or was it simply "not spotted".

  • 2
    $\begingroup$ For me ElGamal seems very unnatural compared to DLIES, which was invented even later. $\endgroup$ – CodesInChaos Oct 28 '16 at 14:57

Actually, if you read Diffie and Hellman's paper closely, you'll see that they explicitly talk about taking another's party value from a public file. Thus, it really already does public-key encryption. However, they didn't call it that, and people didn't view it as public-key encryption, but rather as key distribution.

The reason for this is that at the time, the understanding was that public-key encryption required a "trapdoor function" that can be inverted using the secret key. In fact, this is how Diffie and Hellman defined it, and thus they couldn't achieve it.

Now, El Gamal explicitly stated that the technical construction is just Diffie-Hellman. However, his conceptual contribution is enormous; he recognized that public-key encryption does not need to be an invertible function. By the way, the majority of his paper is about the digital signatures and this is novel.

This discussion raises an interesting point which is that some important results are completely non-technical and are important because they make us look at things differently. This is exactly what the El Gamal paper did.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.