Foundation of modern cryptography: Discrete Log, Diffie-Hellman and ElGamal

In which we show that how secure communication is possible without any prearrangement or any shared randomness.

Preliminaries

• : ring of integers modulo , which is defined over with addition and multiplication modulo

• : multiplicative group defined by , which is defined over with multiplication modulo .

• : the set of all -bit primes, i.e., all primes in . By the Prime number theorem, we know that there is fraction of -bit numbers are primes.

• : set of all generators of a cyclic group . is a generator of the group if .

From now, we assume is a -bit prime. As the consequence, is a cyclic group over with generators.

We have the hardness of some arithmetic operations in :

• Multiplication: using naive algorithms, using FFT algorithm.

• Exponentiation: using repeated squaring method ( time to compute where is the time for multiplication).

• Inverse: same as exponentiation, which is . This is because by the Fermat’s little theorem.

Discrete logarithm problem

For a generator and , there must be an such that . This number is called the discrete logarithm of w.r.t. the generator , denoted by .

Unlike the three operations mentioned previously, discrete log is believed to be hard: trivial bruteforce requires time , which is exponential in . All existing algorithms, either for general groups (like Baby-step Giant-step and Pohlig–Hellman algorithms) or for specific (like Index-Calculus and Number field sieve algorithms) require time exponential in . Therefore, it is believed that the problem is hard to solve:

Here, our assumption is that the discrete-log problem is not just hard but even hard on average, as all are random.

Note: asymmetric cryptography we are using today relies on the assumption regarding the hardness of two computational problems: one is the above Discrete-log (used in Diffie-Hellman, DSA/ECDSA, and Elliptic Curve Cryptography) and the another is the Integer Factorization (used in the RSA algorithm). This seems to be... embarrassing!?! The quote below is from the introduction of Foundations of Cryptography – A Primer by Oded Goldreich:

“The way to demonstrate that a definition is viable (and that the corresponding intuitive security concern can be satisfied at all) is to construct a solution based on a better understood assumption (i.e., one that is more common and widely believed). [...] Thus, facts that were not known to hold at all (and even believed to be false), were shown to hold by reduction to widely believed assumptions (without which most of modern cryptography collapses anyhow). To summarize, not all assumptions are equal, and so reducing a complex, new and doubtful assumption to a widely-believed simple (or even merely simpler) assumption is of great value."

More note: in 1994, Peter Shor discoverd that quantum computer can solve Discrete-log and Integer Factorization in polynomial time (FOCS’94). The algorithm is now named after him, the Shor’s algorithm. Before that, quantum computing was essentially a physics toy or a theoretical concept discussed by people like Richard Feynman. Shor’s algorithm turned this scientific curiosity into a national security priority.

Constructing OWF from Discrete-log: the simplest way to constructing a OWF under the assumption about hardness of discrete-log is: where is a -bit prime, is a generator of , and . Here, no adversary can recover given with noticeable advantage since finding given is assumed to be hard.

Diffie-Hellman (DH) Problem

Let be a PPT algorithm that, given an input , outputs a description of a cyclic group , which includes a prime and a generator .

If we can solve the DL efficiently then clearly we can also solve CDH efficiently. On the other hand, if DL is hard, then it is, again, believed that CDH is also hard:

We often use the following stronger assumption:

Diffie-Hellman key exchange

The protocol is as follows:

1. . This group description is publicly known

2. Alice samples and sends to Bob

3. Simultaneously, Bob samples and sends to Alice

4. Alice computes , Bob computes

Clearly, Alice and Bob both have as the shared random string at the end of the protocol. What the adversary can see over the channel is . Then,

• If we assume CDH: the adversary can not compute the string in polynomial time. Alice can use a hardcore predicate for the OWF to pad the secret message to Bob.

• If we assume DDH: the adversary can not distinguish from a truly random string, so Alice can use to pad the secret message to Bob.

Note: the secret message in the above context is the key need to be exchanged (?). Additionally, this protocol is vulnerable to a man-in-the-middle attack.

ElGamal Encryption

The Elgamal encryption scheme is a public-key encryption scheme based on DDH. The scheme is as follows:

• Key generation :

  1. Generate group :

  3. Output public key and secret key

• Encryption :

  2. Output

• Decryption :

  1. Extract from

  2. Extract and from

  3. Compute

  4. Output .

The correctness of the scheme is immediate. The following theorem shows the security of the scheme: