2
$\begingroup$

For the Decisional Diffie-Hellman (DDH) assumption we know that:

Given $g^a$ and $g^b$ for uniformly and independently chosen $a,b \in Z_p$ the value of $g^{ab}$ looks like a random value in group $\mathbb{G}$.

For the Decisional Bilinear Diffie-Hellman (DBDH) assumption we know that:

In a group $\mathbb{G}_0$ of prime order $p$, let $a,b,c \in \mathbb{Z}_p$ be chosen at random and $g$ be a generator of $\mathbb{G}_0$. The adversary when given $(g,g^a,g^b,g^c)$ must be able to distinguish a valid tuple $e(g,g)^{abc} \in \mathbb{G}_T$ from a random element $R \in \mathbb{G}_T$.

I cannot clearly understand the difference between both. Can someone state the difference of each and when to consider each one. I know that DBDH is used when considering pairings but I am still confused about the difference of both.

$\endgroup$

2 Answers 2

2
$\begingroup$

I don't know if it can helps. But actually, you can win the DDH game if you are using pairings.

Suppose you are given $X = g^x$ and $Y = g^y$, you can apply $e(X,Y) = e(g,g)^{xy}$.

Given $Z$, your goal is to know if $(X,Y,Z)$ is a DDH triplet.

You can test, using useful properties of pairings, if $e(g,Z) = e(X,Y)$ and so you can distinguish from a random element.

So I think that's why we consider 3 numbers to distinguish.

You can also think about Key-exchange Diffie-Hellman and Joux "Tripartie DH" as described in this PDF.

$\endgroup$
1
$\begingroup$

In short, Decisional Diffie-Hellman(DDH) can be considered that it is hard to calculate the logrithm, eazy to calcuate the exponantial. As your notation, even you have $g,\space g^a,\space g^b$. you cannot calcuate $a$ and $b$ easily, that's why it is hard to calculate $g^{ab}$.

But in bilinear pairing (you can treat $e(n,\space m)$ as a new rule of operation), what we know is that $e(n^e,\space m^f)$ equal to $e(n,\space m)^{ef}$ and calcuate $e(\text{element1},\space \text{element2})$. So it is possible to calculate $e(g,\space g)^{ab}$ because it is equal to $e(g^a,\space g^b)$ and we have known $g^a,\space g^b$ according to your assumption. In a similar way, we can calculate $e(g,\space g)^{bc}$ or $e(g,\space g)^{ac}$ easily. But that's all we have (don't ask why, bilinear pairing is just a definition of a new operation), no other way to calculate $e(g,\space g)^{abc}$

$\endgroup$

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.