Question

What common elements do the ElGamal cryptosystem and Diffie-Hellman key exchange share?

Answer 1

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.

We have a group Z∗p for prime p generated by g. Party A chooses random a∈Z∗p and sends ga to B and B chooses random b∈Z∗p and sends gb to A and both compute gab 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,gb) 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., gb 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 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 gb and the computed DH key gab is used as a one-time-pad to encrypt a message m∈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 (c1,c2) consisiting of the message encrypted with the DH key m⋅gab and the part ga 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 (c1,c2)=(ga,m⋅gab) 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 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: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 gm, i.e., as exponent of the generator g

DH or ElGamal

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.

• 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 gm, 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.