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