**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

[ Cryptology ePrint archive ]