Efficient Implementation of Pairing-Based Cryptosystems

Pairing-based cryptosystems rely on the existence of bilinear, nondegenerate, efficiently computable maps (called pairings) over certain groups. Currently,all such pairings used in practice are related to the Tate pairing on elliptic curve groupswhose embedding degree is large enough to maintain a good security level, but small enoughfor arithmetic operations to be feasible. In this paper we describe how to constructordinary (non-supersingular) elliptic curves containing groups with arbitrary embeddingdegree, and show how to compute the Tate pairing on these groups efficiently.