Paper 2002/088

Constructing Elliptic Curves with Prescribed Embedding Degrees

Paulo S. L. M. Barreto, 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 . In this note, we examine criteria for curves with larger that generalize prior work by Miyaji et al. based on the properties of cyclotomic polynomials, and propose efficient representations for the underlying algebraic structures.

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

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Accepted for presentation at SCN'02 (to be published in LNCS)
Keywords
elliptic curve cryptosystem
Contact author(s)
pbarreto @ larc usp br
History
2005-02-22: last of 3 revisions
2002-07-04: received
See all versions
Short URL
https://ia.cr/2002/088
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/088,
      author = {Paulo S.  L.  M.  Barreto and Ben Lynn and Michael Scott},
      title = {Constructing Elliptic Curves with Prescribed Embedding Degrees},
      howpublished = {Cryptology {ePrint} Archive, Paper 2002/088},
      year = {2002},
      url = {https://eprint.iacr.org/2002/088}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.