# Diffie-Hellman Assumptions

## Computational Diffie-Hellman (CDH) Assumption

```Definition: The computational CDH assumption is the assumption that a certain
computational problem within a cyclic group is hard. The CDH
assumption is related to the assumption that taking discrete
logarithms is a hard problem.

The assumption states that for a generator g and values a and b that
are all randomly selected, given

( g, g^a, g^b )

it is computationally intractable to compute the value

g^(ab)

which is the basis of the classical Diffie-Hellman key exchange algorithm.

Any cyclic group can be used. Thus working in GF(p) any prime number p can
be used. Especially p does not have to be a safe prime of the form

p = kq + 1

where k is a small prime factor (usually k = 2 is chosen) and q is a large prime.
As the base for the DH algorithm a generator g is usually selected which generates
all elements of the cyclic multiplicative group in GF(p).

Example:  p = 13 = 2*2*3 + 1,  g = 2  (p is not a safe prime)

0  1  2  3  4  5  6  7  8  9 10 11 12  x
1  2  4  8  3  6 12 11  9  5 10  7  1  g^x mod p

For the Diffie-Hellman algorithm to work, the secret factor s can be any value
of GF(p) in the unique range

0 <= s < p-1

These are the bounds which the Fundamentals of Computer Security
and Willi Meier are defining.

Since g^0 = 1 is not really a good choice for a public DH factor, though
with large groups it is rather improbable that s = 0 is randomly selected,
it might make sense to exclude this trivial value, thus arriving at

0 < s < p-1

Also since g^1 = g and due to the fact that the generator g is usually fixed
and published in some RFCs, it might also make sense to exclude s = 1, too,
although selecting it by random is improbable as well:

1 < s < p-1

This is what the German Wikipedia entry is defining. Actually any value
within a close range of 0 is potentially weak since an attacker might just
run a routine test e.g. on the first 100 values. Thus it might make sense

0 ≤ s < p-1
```

## Decisional Diffie-Hellman (DDH) Assumption

```Definition: The decisional Diffie-Hellman (DDH) assumption is a computational
hardness assumption about a certain problem involving discrete logarithms
in cyclic groups. It is used as the basis to prove the security of many
cryptographic protocols, most notably the ElGamal and Cramer-Shoup
cryptosystems.

The DDH assumption requires that the following two probability distributions are
computationally indistinguishable (in the security parameter q):

( g^a, g^b, g^(ab) )

where a and b are randomly and independently chosen from Zq, and

(g^a, g^b, g^c )

where a,b,c are randomly and independently chosen from Zq.

The El Gamal encryption algorithm

[c1, c2] = [g^r, m*h^r] = [g^r, m*g^(sr)]

with

h = g^s mod p

works perfectly well under the CDH assumption, since it is a hard
problem to decrypt message m if the secret s is not known. Also
it is always possible to decrypt the ciphertext [c1, c2] in a
unique way

m = c2 / c1^s = m*g^(sr)/g^(rs) = m

Problems occur if multiple messages containing the same plaintext m
are encrypted because with an arbitrary prime p the El Gamal cipher
is not semantically secure. This is the case in e-voting since
each voter encrypts e.g. either a "yes" or "no" message using the
same generator g and public key h = g^s.

Let's assume two voters A and B who encrypt the same message m and
choose for their random factor r the values a and b, respectively

A:  [g^a, m*g^(as)]

B:  [g^b, m*g^(bs)]

The two ciphertexts are different and look totally random so that A
who voted "yes" does not have a clue whether B voted "yes" or "no".
Thus at first glance the encryption seems to be semantically
secure, which depends on the DDH assumption stating that

g^(rs)

must look like a g^c with a random c, given

c1 = g^r and public key h = g^s

Unfortunately this is not the case for arbitrary primes p and
generators g.

Let us analyse our example with p = 13 an g = 2 by squaring
all elements v of the cyclic multiplicative group generated by g:

1  2  3  4  5  6  7  8  9 10 11 12  v
1  4  9  3 12 10 10 12  3  9  4  1  v^2 mod p

Thus only 1, 3, 4, 9, 10, and 12 are square numbers or
quadratic residues possessing two square roots each:

1:  1 and 12
3:  4 and  9
4:  2 and 11
9:  3 and 10
10:  6 and  7
12:  5 and  8

The remaining elements 2, 5, 6, 7, 8, and 11 of the cyclic

The Legendre symbol (v/p) determines whether a given value v
is a quadratic residue or not:

-
|  0 if v == 0 mod p
|
(v/p) = <  +1 if v != 0 mod p and for some integer x, x^2 = v mod p
|
| -1 if v != 0 mod p and if there is no such x
-

Thus multiples of p return 0, quadratic residues +1 and nonresidues -1.

The Legendre symbol can be computed using the formula

(v/p) = v^((p-1)/2) mod p

For p = 13:

(v/13) = v^6 mod 13

returns

+1 for 1, 3, 4, 9, 10, 12, i.e. in fact all quadratic residues

and

-1 for 2, 5, 6, 7, 8, 11, i.e. all quadratic nonresidues

The following multiplicative property of the Legendre symbol

(uv/p) = (u/p)(v/p)

nonresidues results in a quadratic residue but that the product of

As a consequence of this formula, a generator g must be a quadratic
nonresidue, otherwise it could not cover all elements of the
multiplicative cyclic group of GF(p). And in fact g = 2 is a quadratic
nonresidue in GF(13).

It is also evident that given g^a and g^b the Legendre symbol of g^(ab)
can be determined:

With g chosen as a quadratic nonresidue, an even exponent r would
result in a quadratic residue g^r mod p whereas an odd exponent would
result in a quadratic nonresidue. Thus g^(ab) will be a quadratic residue
if either a or b or both are even and a quadratic nonresidue otherwise.
This clearly violates the DDH assumption that g^(ab) should be totally
unrelated to g^a and g^b.

Even worse, since El Gamal computes

[g^r, m*g^(sr)]

the Legendre symbol of message m can be computed using the multiplication
formula. Thus if the message representing "yes" happens to be a quadratic
residue and the message for "no" a quadratic nonresidue, the content of
a ballot even though encrypted with a random r could be guessed. Thus
semantic security is not guaranteed.

On the other hand if the generator g were chosen as a quadratic residue
then it would generate a subgroup of GF(p) consisting of quadratic residues
only, thus fulfilling the DDH assumption and as a consequence guaranteeing
semantic security.

Using safe primes of the form

p = 2q + 1

guarantees the existence of a large subgroup of order q with all elements

Example:  p = 11, q = (p-1)/2 = 5

The Legendre symbol shows

+1 for 1, 3, 4, 5, 9    quadratic residues
-1 for 2, 6, 7, 8, 10   quadratic nonresidues

Generator g = 3 generates a multiplicative cyclic group of order q = 5

0  1  2  3  4  5   x
1  3  9  5  4  1   g^x mod p

which generates all quadratic residues. Thus if the El Gamal encryption
algorithm is to be secure under the DDH assumption, the secret s and
message m must be chosen among the elements of the multiplicative cyclic
subgroup of order q:

0 ≤ s < q

which is the definition of the English Wikipedia entry.
```

© 2009 by Andreas Steffen, HSR Hochschule für Technik Rapperswil