The wiki defines the decisional Diffie–Hellman assumption as follows:
Decisional Diffie–Hellman assumption
Consider a (multiplicative) cyclic group $G$ of order $q$, and with generator $g$. The DDH assumption states that, given $g^a$ and $g^b$ for uniformly and independently chosen $a$,$b$ $\in \mathbb{Z}_q$, the value $g^{ab}$ "looks like" a random element in $G$.
This intuitive notion is formally stated by saying 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 $\mathbb{Z}_q$
- $(g^a,g^b,g^c)$, where $a,b,c$ are randomly and independently chosen from $\mathbb{Z}_q$.
some confusions about DDH assumption
my confusion doesn't lie in the group that hold the DDH but that does not hold the DDH. The Wiki says
Importantly, the DDH assumption does not hold in the multiplicative group $\mathbb{Z}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the Legendre symbol of $g^{ab}$, giving a successful method to distinguish $g^{ab}$ from a random group element
poncho shows me how to do it. Next i will describe that in my understanding.
Given $(g^a,g^b,g^{ab})$ and $(g^a,g^b,g^c)$, such that $a,b,c$ are are randomly and independently chosen from $\mathbb{Z}^*_p$. if $\left(\frac{g^a}{p}\right)=1\Rightarrow a\equiv0\pmod2$, and if $\left(\frac{g^a}{p}\right)=-1\Rightarrow a\equiv1\pmod2$ , so does $\left(\frac{g^b}{p}\right)$ and $\left(\frac{g^c}{p}\right)$. So there are one occasion that can be distinguished correctly : if $ab\neq c\pmod2$ then we can faithfully say that $g^{ab}\neq g^c$.
This is error-free as poncho said. But when $ab\equiv c\pmod2 $ happens, we can not distinguish $g^{ab}$ from $g^c$.That is to say, we can only partially distinguish $g^{ab}$ from $g^c$.
But in practical, does the DDH Oracle really exist? if not, supposing the exist of DDH Oracle will mean nothing. Or in other words, in the real word this Oracle is hard to realize then this kind of assumption will do nothing(this is only my personal thought)
A practical example
Next i want to use an example to illustrate my confusions.This protocol comes from here
The writer just say that $\mathbb{G}=\langle g \rangle$(a cyclic group of order $q$) on which DDH problem can be efficiently solved. i guess that $q$ is prime. And i'm not sure whether the "on which DDH problem can be efficiently solved" refer to the method of quadratic residue above. if so, there are many occasions that the DDH() cannot give a right answer. so i think the "on which DDH problem can be efficiently solved" does not have much meaning. i don't know if there exist other way to efficiently solve DDH problem, i really think that the DDH() cannot fully guarantee the answer's correctness in this example.
so who can help to clear these confusions?