5
$\begingroup$

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
enter image description 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?

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ in your words, then the $G$'s order $q$ in the example must be composite number ,or the DDH will be hard on it, right? But it's rare to see a key-exchange protocol been designed on this kind of group. or maybe the example above made an wrong assumption? $\endgroup$
    – T.B
    Sep 22, 2013 at 8:03
  • $\begingroup$ For key exchange, we mostly care about CDH, not DDH. DDH is mainly used as a proof tool: the security of some other protocols can be reduced to that of DDH; in those cases, we need a group in which DDH is hard. In the usual practice of Diffie-Hellman for key exchange, the two parties just need to choose "large enough" private exponents, and they assume that the largest prime factor of the subgroup order is also large enough -- the order needs not be prime, and they need not know that order (that's how it goes for the client in SSL with a "DHE" cipher suite). $\endgroup$ Sep 22, 2013 at 12:16
  • $\begingroup$ thanks for what you have answered, but the answer you give isn't explicit. that won't do much help to clear my confusions $\endgroup$
    – T.B
    Sep 23, 2013 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.