Cryptology ePrint Archive: Report 2002/088

Constructing Elliptic Curves with Prescribed Embedding Degrees

Paulo S. L. M. Barreto and Ben Lynn and Michael Scott

Abstract: Pairing-based cryptosystems depend on the existence of groups where the Decision Diffie-Hellman problem is easy to solve, but the Computational Diffie-Hellman problem is hard. Such is the case of elliptic curve groups whose embedding degree is large enough to maintain a good security level, but small enough for arithmetic operations to be feasible. However, the embedding degree is usually enormous, and the scarce previously known suitable elliptic groups had embedding degree $k \leqslant 6$. In this note, we examine criteria for curves with larger $k$ that generalize prior work by Miyaji et al. based on the properties of cyclotomic polynomials, and propose efficient representations for the underlying algebraic structures.

Category / Keywords: public-key cryptography / elliptic curve cryptosystem

Publication Info: Accepted for presentation at SCN'02 (to be published in LNCS)

Date: received 2 Jul 2002, last revised 22 Feb 2005

Contact author: pbarreto at larc usp br

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Fixed the last example in appendix B and updated the references.

Version: 20050222:233404 (All versions of this report)

Short URL: ia.cr/2002/088

Discussion forum: Show discussion | Start new discussion