### 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 $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.

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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2002/088

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},
note = {\url{https://eprint.iacr.org/2002/088}},
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.