ECDLP can be solved in 24-th root time

We report breaking news of an O( q^{1/24} ) time algorithm for the ECDLP in any elliptic curve E( F_q ). While still exponential complexity, this result will require a major increase in parameter for elliptic curve cryptosystems.

Full details are yet to be released, but the main idea is to exploit recent work by
Maryna Viazovska on sphere packings.

Her work on the 8-dimensional packing seems to lead to an O( q^{1/8} ) algorithm, which would already require a major change in elliptic curve key sizes. But her new joint work with Cohn, Kumar, Miller and Radchenko on sphere packings in dimension 24 gives a much stronger result. As a result we recommend increasing elliptic curve key sizes from 256 bits to 3072 bits.

The method is an index calculus approach. The factor base is chosen by combining two standard results:

  1. The connection between the elliptic curve discrete logarithm problem and the minimal distance of an elliptic codes, and sphere packings (see for example
    this blog post.

  2. The connection between minimal distances of codes and sphere packings.

The decomposition algorithm for the factor base therefore gets translated to a sphere packing problem in 24 dimensions, now solved by Viazovska and her collaborators.

More details to follow. Watch this space.

— Steven Galbraith, April 1, 2016.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to ECDLP can be solved in 24-th root time

  1. Vanessa Vitse says:

    I am quite skeptical because of the hidden constant in the complexity, which obviously depends on the kissing number, see http://www.mathnet.ru/links/7eec02cac3c70f110fe87e7bd082d5a2/ppi457.pdf
    More generally one should expect for any n an algorithm with a complexity in O(k(n)q^(1/n)). The case n=24 is of course special because of the existence of the Leech lattice and its Poisson superalgebra.
    Thanks anyway to Steven for sharing this outlandish result.

  2. Mike Scott says:

    Good to see that the Aprils fool joke is alive and well. Still gets me every time….

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s