4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 17 '17 at 13:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 17 '17 at 13:07
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 17 '17 at 13:07
1
$\begingroup$

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.

$\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.