17
$\begingroup$

For what kind of usage should we prefer using Diffie-Hellman in order to exchange keys instead of ElGamal, and most important why should we use one or the other?

I do not see a clear difference between these two algorithms. What are their respective advantages?

$\endgroup$
1
  • $\begingroup$ One is a key agreement protocol, the other an encryption scheme. They are not interchangeable. However, they are two mechanisms based on the same computational problem, which is the CDH problem. $\endgroup$
    – tylo
    Commented Jul 23, 2014 at 13:09

1 Answer 1

23
$\begingroup$

Diffie Hellman

Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme.

I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ generated by $g$. Party $A$ chooses random $a\in \mathbb{Z}_p^*$ and sends $g^a$ to $B$ and $B$ chooses random $b\in \mathbb{Z}_p^*$ and sends $g^b$ to $A$ and both compute $g^{ab}$ as their common DH key.

Plain (unauthenticated) Diffie Hellman is known to be susceptible to person-in-the-middle attacks and this can be circumvented (as for instance done in TLS) by authenticating Diffie Hellman either

  • by including the static Diffie Hellman paramters $(p,g,g^b)$ of one party (the server in TLS) into a certificate which is signed by a trusted authority (where the static parameters stay the same for all key exchanges) or
  • by requiring the server to sign the ephemeral Diffie-Hellman key, i.e., $g^b$ where $b$ is chosen randomly for every new interaction, sent to the other party (the client). Thereby, the public verification key corresponding to the signing key is put into a certificate which is signed by a trusted authority.

Using a static DH key is in principle very similar to how ElGamal works, but ElGamal encryption is non-interactive.

ElGamal Encryption

ElGamal encryption in contrast to DH is a public key encryption scheme and may be seen as a non-interactive DH key exchange where the public key of $B$ is $g^b$ and the computed DH key $g^{ab}$ is used as a one-time-pad to encrypt a message $m\in \mathbb{Z}_p^*$ which is a group element of the respective group used, typically the encryption operation is defined as multiplying the message with the DH key, or xoring the message with a hash of the DH key.

The ciphertext is then a tuple $(c_1,c_2)$ consisiting of the message encrypted with the DH key $m\cdot g^{ab}$ and the part $g^a$ of the DH key computed by the encrypting party. But the entire process is conducted by one party, i.e., the party encrypting the message. This party then sends the tuple $(c_1,c_2)=(g^a,m\cdot g^{ab})$ to the receiver $B$.

In a practical setting, ElGamal encryption does not really give a benefit when using it as an encryption scheme as it is, since it does only support message of size of elements of the group being used and parameters must be chosen carefully in order to obtain IND-CPA security (holds always in elliptic curves but you have to choose a suitable subgroup of $\mathbb{Z}_p^*$ to obtain it). However, it can be turned into a hybrid encryption scheme. But when one wants to use such a hybrid encryption scheme IES/ECIES is a better choice. ElGamal encryption, when the paramters are chosen in the right way achieves the weaker notion of indistinguishability under chosen plaintext attacks (IND-CPA), where IES/ECIES achieves stronger security, namely indistinguishability under chosen ciphertext attacks (IND-CCA).

ElGamal still has some benefits, which however, are more interesting when using ElGamal encryption as a building block for "larger" cryptographic protocols. For instance:

  • It is a homomorphic encryption scheme which allows multiplying plaintext hidden inside of ciphertexts and when using the homomorphic property with an encryption of the identity element $1$ of the group allows to publicly re-randomize ElGamal ciphertexts, i.e., obtain new ciphertexts for the same message which are unlinkable to the original ciphertexts. Using exponential ElGamal obtained from ElGamal by encoding the message $m$ as $g^m$, i.e., as exponent of the generator $g$, ElGamal can also be made additively homomorphic for polynomial sized message spaces (since decrypting involves computing discrete logarithms).

  • There are efficient honest-verifier zero-knowledge proofs of knowledge to prove properties of ElGamal ciphertexts without revealing the plaintext, e.g., equality of plaintexts.

  • ElGamal can be used to construct a threshold cryptosystem, i.e., there are $n$ parties holding shares of the secret decryption key and a ciphertext can only be decrypted if at least $k$ of these $n$ parties are involved in the decryption process but fewer then $t$ parties will fail in decrypting.

DH or ElGamal

For what kind of usage should we prefer using Diffie Hellman in order to exchange keys instead of Elgmal, and most important why should we use one or the other ?

That heavily depends on your application scenario. For instance, are sender and receiver on line or not? Do you want to simply encrypt data for confidential storage or communicate with some other guy? One feature that can be achieved for confidential communication when exchanging keys using a key exchange protocol such as DH is forward secrecy, which you will not have when using asymmetric encryption and sending encrypted messages under a fixed ElGamal/IES/ECIES public key to a receiver.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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