**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

[ Cryptology ePrint archive ]