We report breaking news of an time algorithm for the ECDLP in any elliptic curve . 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 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.