A Group Where DDH Assumption Does (NOT) Hold
Note that DDH Assumption is a “belief” and not a “fact.” If it is proven that such groups exist where DDH assumption holds, then this proof will also imply that . So we can only find that the DDH hypothesis does NOT hold in some groups, and it seems impossible to prove that the DDH hypothesis holds in some groups.
We already know that DDH assumption does not hold in groups where computing DLOG is easy, so does in the groups have parings.
We present here that in a common group (where is a prime), DDH assumption does not hold as well.
Let be a polynomial-time algorithm that, on input outputs a prime with and a generator of Prove that the DDH problem is not hard relative to
Quadratic Residues Modulo a Prime
In , is a quadratic residue if there exists an with mod .
We denote the set of quadratic residues modulo by and the set of quadratic non-residues by
Exactly half the elements of are quadratic residues.
For prime:
Define the Jacobi symbol of modulo as follows. Let be prime, and Then
The quadratic residues in are exactly those elements that can be written as with an even integer.
Algorithm: Deciding quadratic residuosity modulo a prime
Input: A prime , an element
Output: (or, equivalently, whether is a quadratic residue or quadratic non-residue)if return "quadratic residue" else return "quadratic non-residue"
To Distinguish DDH Tuple
Given we can (efficiently compute and) check or not. Due to the algorithm above, this test identifies whether is even or not, where .
For brevity, we shall say that is an even power, if and is even. Similarly, we shall say that is an odd power, if and is odd.
So, given and we can determine if or is an even power. If or is an even power then is an even power as well ! However, the element shall be an even power only with probability .
Efficiently distinguish samples from the distribution (A, B, C) from (A, B, R)
Suppose we are given elements . We perform the following test
Is an even power and Is an even power?
Note that the probability that or is an even power is .
Suppose Conditioned on being an even power, the probability that is an even power is . So, the probability that this test returns true is
Suppose Conditioned on being an even power, the probability that is an even power is . So, the probability that this test returns true is
So, this test distinguishes the distribution (A, B, C) from (A, B, R).