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

Daniel R.  L.  Brown

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: 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},
      url = {https://eprint.iacr.org/2014/877}
}