Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / elliptic curve

Date: received 23 Oct 2014, last revised 24 Feb 2015

Contact author: dbrown at certicom com

Available format(s): PDF | BibTeX Citation

Note: A few corrections (but many still needed)

Version: 20150224:181907 (All versions of this report)

Short URL: ia.cr/2014/877

Discussion forum: Show discussion | Start new discussion