some of my confusions about DDH assumption

Question

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?

Answer 1

For the Legendre symbol and DDH: when working modulo a prime $p$, you can have have a group where DDH (apparently) holds. Namely, suppose that there is a known prime $q$ which divides $p-1$, and $g$ has order exactly $q$. This is easy to achieve if you generate $q$ first, then look for a prime $p = qr + 1$ for some random values of $r$; then, to compute $g$, take a random $h$ modulo $p$ and compute $g = h^r$ (still modulo $p$)(if you end up with $g = 1$, try again, but probabilities are very low of this occurring). It can be shown that $g$ is a square modulo $p$, which implies that $\left(\frac{g^a}{p}\right) = 1$ for all $a$.

In fact, the Legendre symbol is just a special case of a more generic method. Suppose that $g$ has order $n$, and $k$ is a non-trivial prime divisor of $n$. Then, given $g^a$ for some unknown $a$ modulo $n$, you can compute $(g^a)^{n/k}$, which will be one of the $k$ values generated by $g^{n/k}$. This reduces DDH to a group of size $k$; if $k$ is small then DDH becomes easy. The method with the Legendre symbol really is the case $k = 2$.

By choosing $g$ to have a prime order $q$ exactly, this method is fully countered, and DDH is hard again.

For groups where DDH is easy, but CDH is hard: the method above is only partial: it makes DDH easy in some cases, in that it can detect some situations where a given triplet $(g^a,g^b,g^c)$ is not a DH triplet ($c \neq ab$), but not all. To have a group where DDH is invariably easy, but CDH still hard, you need some more mathematics. The only known really practical solution (so far) uses pairings on elliptic curves. This requires choosing curves with some specific characteristics.