Decisional Diffie Hellman problem

The Decisional Diffie Hellman Problem ( DDH for short ) is a variant of the Computational Diffie Hellman Problem ( CDH ), which deals with the difficulty of deciding whether a number has a certain form. For certain groups it is assumed that this problem is difficult, i.e. that it cannot be solved by a probabilistic polynomial time algorithm with a small error probability . This DDH assumption plays a major role in cryptography and especially in public key cryptography as a starting point for security proofs . The Decisional-Diffie-Hellman problem is related to the discrete logarithm ( DLOG ).

definition

A finite cyclic group with finite order and producer is given, usually written multiplicatively . This means that there is an exponent for each element of the group , so that . ${\ displaystyle \ mathbb {G}}$ ${\ displaystyle q}$ ${\ displaystyle g}$ ${\ displaystyle h}$ ${\ displaystyle x \ in \ mathbb {Z} _ {p}}$ ${\ displaystyle h = g ^ {x}}$

Let it be exponents. The Decisional-Diffie-Hellman problem is now for a triple in which and are random, to recognize whether or whether it is also random if both cases occur with a probability of ½ each. ${\ displaystyle x, y, z \ in \ mathbb {Z} _ {q}}$ ${\ displaystyle (g ^ {x}, g ^ {y}, g ^ {z})}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle x \ cdot y = z}$ ${\ displaystyle z}$

By guessing, a ½ probability of success can obviously be achieved. If there is no efficient algorithm in a group that solves the problem substantially better, it is said that the Decisional Diffie-Hellman assumption applies in this group . ${\ displaystyle \ mathbb {G}}$

requirements

The Computational Diffie Hellman Problem (CDH) is the problem of finding two elements and the element in such a group . If this problem is easy in a group, then obviously the DDH problem is also easily solvable and the DDH assumption in this group is consequently untrue. The reverse of this statement (i.e. that the CDH assumption would result in the DDH assumption) does not follow from this and there are groups known in which CDH seems to be difficult, but DDH can be easily solved. ${\ displaystyle g ^ {x}}$ ${\ displaystyle g ^ {y}}$ ${\ displaystyle g ^ {xy}}$

The discrete logarithm problem (DLog) is the problem about a group element 's exponent . If the DLog problem can be easily solved in a group, the CDH problem and thus also the DDH problem can be easily solved by pulling the DLog from and calculating from . In this case, both the DDH assumption and the analogously defined CDH assumption are therefore untrue. ${\ displaystyle g ^ {x}}$ ${\ displaystyle x}$ ${\ displaystyle g ^ {y}}$ ${\ displaystyle \ left [g ^ {x} \ right] ^ {y}}$

All three assumptions can be proven in the generic group model for groups, provided that their order is prime or secret. However, this only means that there are no attacks that only use the group operation, but does not exclude attacks that use a structure of the group in question that goes beyond this.

Examples

The classic example of a group in which most cryptologists out acceptance DDH of the validity of are subgroups primer order of with prime. ${\ displaystyle \ mathbb {Z} _ {p} ^ {\ times}}$ ${\ displaystyle p}$

It is true that the subgroup of the quadratic residues has prime order and is therefore a suitable candidate. ${\ displaystyle p = 2q + 1}$

On the other hand, it is easy in DDH, for example , because DLOG is easy there too. Since this is an additive group, the exponentiation here corresponds to the multiplication. Thus DLOG is only the division. Given you check whether . This is the case if is. The division is not a group operation in , but is still possible due to the special structure of the whole numbers (both the group elements and the “exponents” are whole numbers). ${\ displaystyle \ mathbb {Z} _ {q} ^ {+}}$ ${\ displaystyle (g, a \ cdot g, b \ cdot g, c \ cdot g)}$ ${\ displaystyle a \ cdot g = (c \ cdot g / (b \ cdot g)) \ cdot g}$ ${\ displaystyle c = from}$ ${\ displaystyle (\ mathbb {Z} _ {p}, +)}$

Individual evidence

↑ Jonathan Katz and Yehuda Lindell: Introduction to modern cryptography . 1st edition. Chapman & Hall / CRC, 2008, ISBN 978-1-58488-551-1 , chapter 7.3.3.

Web links

Dan Boneh: The Decision Diffie – Hellman Problem , ANTS 1998, pp. 48-63 .

[1] Jonathan Katz and Yehuda Lindell: Introduction to modern cryptography . 1st edition. Chapman & Hall / CRC, 2008, ISBN 978-1-58488-551-1 , chapter 7.3.3.