Paper 2014/877

CM55: special prime-field elliptic curves almost optimizing den Boer's reduction between Diffie-Hellman and discrete logs

Daniel R. L. Brown

Abstract

Using the Pohlig--Hellman algorithm, den Boer reduced the discrete logarithm problem to the Diffie--Hellman problem in groups of an order whose prime factors were each one plus a smooth number. This report reviews some related general conjectural lower bounds on the Diffie-Hellman problem in elliptic curve groups that relax the smoothness condition into a more commonly true condition. This report focuses on some elliptic curve parameters defined over a prime field size of size 9+55(2^288), whose special form may provide some efficiency advantages over random fields of similar sizes. The curve has a point of Proth prime order 1+55(2^286), which helps to nearly optimize the den Boer reduction. This curve is constructed using the CM method. It has cofactor 4, trace 6, and fundamental discriminant -55. This report also tries to consolidate the variety of ways of deciding between elliptic curves (or other algorithms) given the efficiency and security of each.

Note: A few corrections (but many still needed)

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curve
Contact author(s)
dbrown @ certicom com
History
2015-02-24: revised
2014-10-28: received
See all versions
Short URL
https://ia.cr/2014/877
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/877,
      author = {Daniel R.  L.  Brown},
      title = {CM55: special prime-field elliptic curves almost optimizing den Boer's reduction between Diffie-Hellman and discrete logs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/877},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/877}},
      url = {https://eprint.iacr.org/2014/877}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.