Chromotopy

February 27, 2010, by Stephen Checkoway

Pairing-based elliptic curve crypto relies on a nondegenerate, bilinear map, called a pairing, $e\colon G_1\times G_2\to G_T$ where $G_1$ , $G_2$ , and $G_T$ are (usually) three distinct groups of prime order $p$ . The two groups $G_1$ and $G_2$ correspond to subgroups of $K$ -rational points $E(K)$ of an elliptic curve $E$ over a finite field $K$ with characteristic $q$ different from $p$ . In fact, $G_1$ and $G_2$ correspond to subgroups of the $p$ -torsion points $E[p]\cong \mathbb Z/p\mathbb Z\times \mathbb Z/p\mathbb Z$ . The target group, $G_T$ is the group of $p$ th roots of unity in $K$ .

For reasons I’ll get to shortly, I’d like an efficiently computable isomorphism $G_T\stackrel\sim\to G_1$ mapping $e(g_1,g_2)\mapsto g_1$ where $g_i$ is a (fixed) generator of $G_i$ . By bilinearity, this map sends $e(g,g_2)\mapsto g$ for any $g\in G_1$ . [This follows from $g_1$ being a generator of $G_1$ so $e(g_1^x,g_2)=e(g_1,g_2)^x\mapsto g_1^x$ .] Since both groups are isomorphic to $\mathbb Z/p\mathbb Z$ , such an isomorphism must exist. The question is whether this is efficiently computable. For example, the particular groups used for crypto admit an efficiently computable isomorphism $G_1\stackrel\sim\to G_2$ but the inverse is only computable for some curves.

One reason an isomorphism from the target group to $G_1$ is so interesting is that allows breaking a number of crypto systems. For example, any system whose proof of security relies on the hardness of the decisional bilinear Diffie-Hellman problem (DBDH) would be compromised. DBDH is the problem where given $g_1,g_1^a,g_1^b,g_1^c,\eta\in G_1$ where $g_1$ is a generator of $G_1$ , one must decide if $\eta=g_1^{abc}$ . With $f\colon G_t\stackrel\sim\to G_1$ mapping $e(g_1,g_2)\mapsto g_1$ and $\psi\colon G_1\stackrel\sim\to G_2$ mapping $g_1\mapsto g_2$ , one can decide DBDH by computing

$\displaystyle e\big(f\big(e(g_1^a,\psi(g_1^b))\big),\psi(g_1^c)\big)=e\big(f\big(e(g_1,g_2)^{ab}\big),g_2^c\big)=e(g_1^{ab},g_2^c)=e(g_1,g_2)^{abc}$ and comparing with $e(\eta,g_2)$ . This works since

$e(g_1,g_2)^{abc}=e(g_1^{abc},g_2)=e(\eta,g_2)$

if and only if $\eta=g_1^{abc}$ . Of course, given $f$ , we can compute $g_1^{abc}=f\big(e(g_1,g_2)^{abc}\big)$ directly.

There is apparently some evidence that such an efficiently computable $f$ may not exist, at least not with some curves. The open question is can it be computed for some particular curves and groups? Given that crypto systems, such as the Boneh-Franklin IBE, use DBDH in their security proofs, the assumption is that such an isomorphism is hard to compute. A proof of its hardness would be interesting as would an explicit construction.