Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

There is a good introduction to the Tate Pairing in the book Martin, L. Introduction to identity-based encryption. London: Artech House., 2008. There are also many simple examples in this book. a natural way to look at the Weil pairing is given in The Weil pairing on elliptic curves over C by Steven D. Galbraith.