Pairing-friendly elliptic curves of prime order

P.S.L.M. Barreto, M. Naehrig

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    472 Citations (Scopus)

    Abstract

    Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree k \leqslant 6 Unknown control sequence '\leqslant'. More general methods produce curves over \mathbb FpFp where the bit length of p is often twice as large as that of the order r of the subgroup with embedding degree k; the best published results achieve ¿ = log(p)/log(r) ~ 5/4. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree k = 12. The new curves lead to very efficient implementation: non-pairing operations need no more than \mathbb Fp4Fp4 arithmetic, and pairing values can be compressed to one third of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants D to minimize ¿; in particular, for embedding degree k = 2q where q is prime we show that the ability to handle log(D)/log(r) ~ (q–3)/(q–1) enables building curves with ¿ ~ q/(q–1).
    Original languageEnglish
    Title of host publicationSelected Areas in Cryptography (12th International Workshop, SAC 2005, Kingston ON, Canada, August 11-12, 2005, Revised Selected Papers)
    EditorsB. Preneel, S. Tavares
    Place of PublicationBerlin
    PublisherSpringer
    Pages319-331
    ISBN (Print)978-3-540-33108-7
    DOIs
    Publication statusPublished - 2006

    Publication series

    NameLecture Notes in Computer Science
    Volume3897
    ISSN (Print)0302-9743

    Fingerprint Dive into the research topics of 'Pairing-friendly elliptic curves of prime order'. Together they form a unique fingerprint.

    Cite this