Question

Briefly describe the idea behind the ElGamal cryptosystem.

(a) What is the one‐way function in this system, if any?

(b) What is the trap door in this system?

(c) Define the public and private keys in this system.

(d) What are the drawbacks, if any?

Answer 1

a)

ElGamal encryption is an example of public-key or asymmetric cryptography. The cryptosystem takes its name from its founder the Egyptian cryptographer Taher Elgamal who introduced the system in his 1985 paper entitled “A Public Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms”.

As this title suggests the security of this cryptosystem is based on the notion of discrete logarithms. This is the ‘one way function’ at the heart of ElGamal’s encryption and decryption algorithms.

In summary: User A (Alice) wants to set up the capability for anyone in the world to send her secret messages. ... Now User B (Bob) can send her secret messages using ElGamal encryption, and only Alice knows the secret key a needed to decrypt the messages. Of course, this is a one-way communication.

b)

A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor". Trapdoor functions are widely used in cryptography.

In mathematical terms, if f is a trapdoor function there exists some secret information y, such that given f(x) and y it is easy to compute x. Consider a padlock and its key. It is trivial to change the padlock from open to closed without using the key, by pushing the shackle into the lock mechanism. Opening the padlock easily, however, requires the key to be used. Here the key is the trapdoor.

Trapdoor functions came to prominence in cryptography in the mid-1970s with the publication of asymmetric (or public key) encryption techniques by Diffie, Hellman, and Merkle. Indeed, Diffie and Hellman first coined the term (Diffie and Hellman, 1976). Several function classes have been proposed, and it soon became obvious that trapdoor functions are harder to find than was initially thought. For example, an early suggestion was to use schemes based on the subset sum problem. This turned out -- rather quickly -- to be unsuitable.

As of 2004 , the best known trapdoor function (family) candidates are the RSA and Rabin families of functions. Both are written as exponentiation modulo a composite number, and both are related to the problem of prime factorization.

Functions related to the hardness of the discrete logarithm problem (either modulo a prime or in a group defined over an elliptic curve) are not known to be trapdoor functions, because there is no known "trapdoor" information about the group that enables the efficient computation of discrete logs. However, the discrete logarithm problem can be used as the basis for a trapdoor when the related problems called the computational Diffie–Hellman problem (CDH) and/or its decisional variant are used. The semantically secure version of the ElGamal Cryptosystem relies on the decision Diffie–Hellman problem (DDH). The Digital Signature Algorithm is based on CDH in a prime order subgroup.

A trapdoor in cryptography has the very specific aforementioned meaning and is not to be confused with a backdoor (these are frequently used interchangeably and this is incorrect). A backdoor is a deliberate mechanism that is added to a cryptographic algorithm (e.g., a key pair generation algorithm, digital signing algorithm, etc.) or operating system, for example, that permits one or more unauthorized parties to bypass or subvert the security of the system in some fashion.

d)

Disadvantages: 1. Its need for randomness, and its slower speed(especially for signing). 2. The potential disadvantage of the ElGamal system is that message ex- pansion by a factor of two takes place during encryption( means the ciphertext is twice as long as the plaintext.

c)

ElGamal is a public key cryptosystem: The encryption key is published, and the decryption key is kept private. ... In ElGamal, the underlying mathematical relationship between the encryption and decryption keys relies upon the so-called discrete log problem, which will be described a bit later.