HSR logo MSE logo

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
to require only *uniqueness* and return to the original definition

  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
multiplicative group are quadratic noresidues.

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)

says that the product of two quadratic residues or two quadratic
nonresidues results in a quadratic residue but that the product of
a quadratic residue with a quadratic nonresidue gives a
quadratic nonresidue.

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
being quadratic residues.

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