Chromotopy

Watercooler research

On an isomorphism from G_T to G_1

February 27, 2010, by Stephen Checkoway

Pairing-based elliptic curve crypto relies on a nondegenerate, bilinear map, called a pairing, where , , and are (usually) three distinct groups of prime order . The two groups and correspond to subgroups of -rational points of an elliptic curve over a finite field with characteristic different from . In fact, and correspond to subgroups of the -torsion points . The target group, is the group of th roots of unity in .

For reasons I’ll get to shortly, I’d like an efficiently computable isomorphism mapping where is a (fixed) generator of . By bilinearity, this map sends for any . [This follows from being a generator of so .] Since both groups are isomorphic to , 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 but the inverse is only computable for some curves.

One reason an isomorphism from the target group to 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 where is a generator of , one must decide if . With mapping and mapping , one can decide DBDH by computing

and comparing with . This works since

if and only if . Of course, given , we can compute directly.

There is apparently some evidence that such an efficiently computable 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.