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