# understanding pairing $e:G \times G \to G_T$ and ( Decision)BDH assumption

From DrLecter's comment, I know that DDH problem can be efficiently solved with this $$e(g^a,g^b)\stackrel{?}{=} e(g,g^z).$$

I have some trouble to understand this map $e:G \times G \to G_T$. Am I right to understand this to be the "multiplication" of two elements in $Z_p^*$ where $p$ is prime. For example, can $e(U=g^u,V=g^v)$ be "seen" as the form $UV$ in $Z_p^*$ ?

Another problem is about the BDH assumption, which says that given $g^a,g^b,g^c$ compute $e(g,g)^{abc}$. There are also the Decision-BDH which says that given $g^a,g^b,g^c$ and $e(g,g)^z$, determine whether $$e(g,g)^z \stackrel{?}{=} e(g,g)^{abc}.$$

As to this two assumptions, where the obstacle lies?

At last, as $e(g^a,g^b)$ can be efficiently solved, what's the algorithm it involved? And could someone do me a favor to give me the source code of the algorithm? If that I will deeply appreciate it.

-
As long as you use a secure pairing friendly curve, it should be secure. Curves with a pairing to a binary field have been seriously weakened recently and should be avoided. – CodesInChaos Sep 28 '13 at 14:57
You should have $\: v = g^x \:$, $\:$ not $\: v = g^* \;$. $\;\;\;$ – Ricky Demer Sep 28 '13 at 22:10
Security: Unexistentially forgeable under adaptive chosen message attack in the random oracle model, assuming that the CDH is hard on certain elliptic curves over a finite field of characteristic 3. – e-sushi Sep 29 '13 at 8:24
I think the basic problem is, that you assume the computations in the group $\mathbb{Z}_p^{*}$. This is not a pairing friendly group, we don't know any efficiently computable pairing for this. The only pairing friendly groups we know are all elliptic curves. The reason why it is so hard to find a suitable pairing (simplified): CDH has to be hard in the domain; CDH has to be hard in the target group; the pairing needs to be a nondegenerate bilinear function. Finding something which fits one or two of these criteria is possible... but for all three we are stuck with elliptic curves so far. – tylo Oct 18 '13 at 11:50
@tylo : "The only pairing friendly groups we know are all elliptic curves", can you show me some references to support this ? – T.B Apr 15 '14 at 8:39

Your misunderstanding comes from the fact that often in pairing based crypto there is a "slight" abuse of notation. I will use symmetric pairings in the following for simplicity.

Often one finds $e: G\times G\rightarrow G_T$ be a pairing, the groups $G,G_T$ are of prime order $p$ and $G$ is generated by $g$. This may mislead you to think that one works in a prime order $p$ subgroup of some prime field $Z_q$, which however is not the case.

But, we are talking of an elliptic curve group $E(\mathbb{F}_q)$ and more precisely a $p$-torsion subgroup $E(\mathbb{F}_q)[p]$, i.e., the subgroup containing elements of order $p$ and $G_T$ is a subgroup of $\mathbb{F}_{q^k}$ of order $p$, where $k$ is the so called embedding degree. Consequently, it would be more appropriate to use additive notation for $G$ and multiplicative notation for $G_T$. However, as said above, often one also misuses multiplicative notation for $G$ (I guess because it is easier to read and people are more familiar with this notation).

Now, say $G$ is generated by any point $P\in E(\mathbb{F}_q)[p]$ and then the DDH problem in $G$ would be given $(P,aP,bP,cP)$ with $a,b,c\in Z_p$ to decide whether $cP=abP$ holds. Obviously, you cannot compute $abP$ given $aP$ and $bP$ in $G$, since this is the CDH in $G$. However, as you already noticed, the pairing $e$ gives you a DDH oracle, by simply checking $e(aP,bP)\stackrel{?}{=}e(cP,P)$ (in this case one often also reads gap-DH groups, since there is a difficulty gap between the DDH and CDH problem).

Now, lets come to the bilinear versions of the DDH/CDH problems. Having $(P,aP,bP,cP)$, you have to compute $e(P,P)^{abc}$ or $g_T^{abc}$ for $g_T=e(P,P)$ being a generator of $G_T$. Notice, however, that when you compute any pairing evaluation of 2 out of the three points $aP,bP,cP$, e.g., $e(aP,bP)$ this gives you an element in $G_T$. And now you cannot apply the pairing to an element of $G_T$ anymore. So, you are limited to compute $e(aP,bP)\cdot e(cP,P)=g_T^{ab+c}$, which however does not solve the bilinear CDH problem. Same argumentation holds for the bilinear DDH problem. You may have to play around a bit to see that the bilinear versions are indeed (intuitively) hard.

p.s. I agree with tylos comment, that you should not change the initial question, since now all other answers are no longer related to the updated question.

-
you are right in your p.s. , i realised that problem, i'll be careful with that in future – T.B Oct 18 '13 at 12:54
sorry to interrupt you again. if $\alpha=e(P,Q)$, and $\alpha,P( or Q)$ are known, are there some methods to get $Q (or P)$ easily? – T.B Oct 20 '13 at 0:57
This is the so called fixed argument pairing inversion problem. The best way to solve this is to compute discrete logarithms in $G_T$ (which you can do in subexponential time - you have to solve discrete logs in finite fields - and is required to be hard for all pairing based cryptosystems). You may also take a look here – DrLecter Oct 21 '13 at 7:10
what about the efficiency of computing $e(P,Q)$, compared with $g^a \pmod{p}$? – T.B Oct 21 '13 at 23:35
This seems to be growing to a selection of many different (non-related) questions ;) I guess it would be better to post them as new questions. – DrLecter Oct 23 '13 at 10:32

An attack against the signature scheme over some group where DDH is easy, can be turned into a solver for the CDH problem over the same group, as is shown in Section 2.3 in the Asiacrypt paper you refer to.

So what you are really asking is: In what groups where DDH is easy is CDH still hard?

I would not use elliptic curves over extension fields of low characteristic. Using ordinary elliptic curves over prime fields with a relatively small embedding degree seems ok.

-
can you illustrate with an pratical example thanks – T.B Oct 6 '13 at 23:54
What would be a practical example? – K.G. Oct 7 '13 at 7:30
a elliptic curve over a finite field – T.B Oct 7 '13 at 11:34
Does this help: theory.stanford.edu/~dfreeman/papers/taxonomy.pdf ? – K.G. Oct 7 '13 at 13:41
i just want an example on which DDH is easy but CDH hard. – T.B Oct 7 '13 at 14:10

Yes. $\:$ The two publicly known attacks are

find a collision in $H$
$\;\;$ and
solve $\: g^x = v \:$ for $x$

.

The first of those only gives an existential forgery after a chosen message,
but uses precomputation to break every key-pair that uses $H$,
The second of those will be able to act identically to the real signer,
but needs to do a presumably infeasible amount of computation for each public key.

-