2
$\begingroup$

When I look at some demos which demonstrate that DDH is easy if a pairing function $e$ exists, I usually see if $e(g,g^c)=e(g^a,g^b)$. Then we can know that $g^c=g^{ab}$, but why is this so? How do we remove the $e$? Let's imagine this is a symmetric-key cypher problem and $e:G_1 \times G_1 \rightarrow G_2$.

For example: here.

$\endgroup$
  • $\begingroup$ The pairing does not occur just randomly in some groups. You have to actually generate the group in a certain way to get such a group. But such groups exist, so in general being able to solve DDH does not automatically break CDH. And the reason is, you can not remove $e$. $\endgroup$ – tylo Jul 26 at 10:35
4
$\begingroup$

You don't 'remove the e', instead, you use the mathematical properties of it.

e satistifies the identities:

$$e(a^x, b) = e(a, b)^x$$

$$e(a, b^y) = e(a, b)^y$$

for any $a, b, x, y$

We also assume that the pairing is nontrivial (that is, $e(g,g) \ne 1$); typically, we further assume that $g$ generates a prime order group, this implies that $e(g,g)$ generates a group of the same order.

So, we have $e(g, g^c) = e(g, g)^c$ (second identity).

We also have $e(g^a, g^b) = e(g, g^b)^a = e(g, g)^{ab}$ (first and second identities).

So, if we have $e(g, g)^c = e(g, g)^{ab}$, because we know that the group generated by $e(g, g)$ and $g$ are isomorphic (even if we cannot compute that isomorphism in the $e(g,g)$ to $g$ direction; that's because all prime order groups of the same prime order are isomorphic), we then have $g^c = g^{ab}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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