ECC 2014, Chennai, India, October 8–10.

The 2014 conference on Elliptic Curve Cryptography will be held in Chennai in October. For more details visit the ECC conferences webpage.

While you visit this page you can find a further memorial article about Scott Vanstone, and a link to a video of Scott’s acceptance speech from when he was presented a special award at the ECC2010 conference for “seminal contributions to research, development, standardization and commercialization of elliptic curve cryptography”. The speech recalls the history of his interest in cryptography and of the company Certicom. It is worth watching.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Scott Vanstone

Scott Vanstone died on March 2, 2014. Four of his close colleagues have written an obituary.

Scott did more than anyone else to raise the profile of Elliptic Curve Cryptography, and its adoption into real-world systems.  His impact on the development of this subject was enormous.

  — Steven Galbraith

Posted in Uncategorized | Leave a comment

New discrete logarithm records, and the death of Type 1 pairings

In the last few days there have been several announcements of record-breaking discrete logarithm computations:

All these papers are using the algorithmic ideas introduced by Joux and others in 2013.

The third result listed above is a continuation of the sort of records previously announced, in particular, since 9234 = 18 * 513 and 513 = 2^9 + 1, it is again using “twisted Kummer” extensions over GF( 2^9 ). This result breaks by a large margin the previous world-record for finite field discrete logarithm computations. It is a great result.

However, the first two results are particularly interesting from the point of view of pairing-based cryptography. Both of the computations are for fields that very naturally arise in pairing-based cryptography using supersingular curves. Importantly, the “large prime” in the field size is not a power of 2 plus or minus 1. Hence these records have shown that the new algorithmic ideas can be applied to a wider range of fields than the previous computations might suggest. This gives evidence that all supersingular elliptic and hyperelliptic curves over moderately-sized fields of small characteristic are not secure for pairing-based cryptography.

One interesting consequence of these works is that “Type 1″ pairings are now essentially dead. Recall that Galbraith, Paterson and Smart “Pairings for cryptographers” (Discrete Applied Mathematics, 2008) introduced a classification of pairings into Type 1, Type 2 and Type 3 (there is also a Type 4, but it is rarely used). Type 3 pairings are usually the most efficient, but some authors have preferred Type 1 pairings as they are convenient in certain applications. Hence, there are a lot of cryptographic protocols in the literature that have been designed only for Type 1 pairings.

The main way to implement Type 1 pairings is to use supersingular curves. There are traditionally two choices:

  1. using fields of characteristic 2 or 3;
  2. using supersingular elliptic curves (embedding degree 2) over GF( p ) where p is at least a 500-bit prime (and, nowadays, probably at least a 1500-bit prime).

The first option was by far the most efficient, but the recent discrete logarithm algorithms and computational records mean it must now be considered insecure. Hence we are stuck with the relatively slow choice of elliptic curves over GF( p ). It means that Type 1 pairings will now be much much slower than Type 3 pairings. It would be better in future to design protocols that do not require Type 1 pairings.

One technical remark:  One can implement Type 1 pairings using ordinary elliptic curves over any field.  One works in a subgroup that is not an eigenspace for Frobenius, and uses the trace map as a “distortion map” to ensure a non-degenerate pairing.  However this approach is also extremely inconvenient: there is no compact representation for elliptic curve points, and the pairing computation is also slow.  So the claim that Type 1 pairings are dead remains true.

— Steven Galbraith

Posted in Uncategorized | 2 Comments

Algorithmic Number Theory Conference, 2014

The call for papers is now available for the ANTS conference.

This year the proceedings will be published in the open access London Mathematical Society Journal of Computational Mathematics. The submission deadline is February 20.

 – Steven Galbraith

Posted in Uncategorized | Leave a comment

ASIACRYPT 2013, Bangalore

What do you mean when you say

“…assuming there exists no algorithm that can solve the ECDLP in fewer than O(N^{1/2}) steps…”?

A quick survey of the people around me during Dan Bernstein and Tanja Lange’s “Non-Uniform Cracks in the Concrete” talk at ASIACRYPT suggested that most people were sure they knew what they mean—and they’re pretty sure they knew what anyone else who writes this kind of thing means, too.  Maybe that’s the problem.  To give a ridiculously oversimplified sketch of the idea: Everyone knows (or should know) that there exist faster algorithms, but they take longer to write down/precompute.  For example, the statement above is strictly false: for any group G of prime order N, given O(N^{2/3}) steps of precomputation, you can compute an algorithm that will solve DLP instances in G in O(N^{1/3}) steps.  On one hand, this renders some theorems in the literature false, because they make careless assumptions (which could, presumably, be easily fixed).  But on the other hand, you might think you still know what you mean—it all depends on your model of computation.  If you want to check, there’s now a choice: the 53-page full version (free) or the 20-page conference version (paywalled).  This paper caused a bit of a stir back when it first appeared, but a year and a half later the controversy has mostly cooled down; it was nice to be able to have a few civilised chats about it at a well-organised conference (with rather good food).

The last twelve months has seen a curious new wave of papers about scalar multiplication on elliptic curves using efficiently computable endomorphisms, following on from the Gallant–Lambert–Vanstone and Galbraith–Lin–Scott constructions.  This year’s ASIACRYPT had two papers on the subject.  Sorina Ionica presented her joint work with Aurore Guillevic, which gave a generalization of Patrick Longa and Francesco Sica’s four-dimensional GLV+GLS construction presented at ASIACYRPT last year, viewed on both elliptic curves and genus 2 curves (via the Weil restriction).  The other paper was mine; it deals with the problem of constructing twist-secure elliptic curves with two-dimensional scalar decompositions over the fastest finite fields (this is basically just the minimal modification of GLS required to get twist-security). 

The rump session had a number of interesting results for curvists. Nadia Heninger presented joint work with Joppe Bos, Alex Halderman, Jonathan Moore, Michael Naehrig, and Eric Wustrow, which surveys how ECC is actually used in practice on the web today.  You’ll find a lot of interesting (and cute, and occasionally worrying) facts in the slides and the preprint.  We also saw some advertising for a range of projects involving Dan Bernstein and Tanja Lange: Elligator (encoding bitstrings into elliptic curve points, with Anna Krasnova and Mike Hamburg), MinimaLT (a fast replacement for TLS and TCP, with Michael Petullo, Xu Zhang, and Jon Solworth), and the safecurves page.

–Ben Smith

Posted in Uncategorized | Leave a comment

Pairing 2013

The 6th InternationalConference on Pairing-Based Cryptography (Pairing 2013) took place in Beijing from November 22 to 24. The event started with two tutorials on friday the 22nd targeting students starting in the area of elliptic-curve and pairing-based cryptography.  More senior attendees used the time for an excursion to the Great Wall.  

The main conference talks were held on saturday and sunday morning. As for ECC 2013 earlier this year, the major topic was the discrete-logarithm breakthroughs of this year. They were the subject of the invited talk “Computing discrete logarithms in finite fields of small characteristic” by Pierrick Gaudry and of two contributed talks (by Cécile Pierrot and by Gora Adj). A consequence of these breakthroughs is that most previously considered constructions of symmetric pairings are no longer considered secure. This fact was addressed by two papers (and corresponding talks, by Tadanori Teruya and Xusheng Zhang) that proposed new efficient constructions for symmetric pairings. Francisco Rodríguez-Henríquez in his invited talk focused on another research direction of pairing-based cryptography, namely efficient pairing-based-protocol implementations. The central point of his talk was to bring the “protocol community” and the “fast-implementation community” together to see more papers describing implementations of full pairing-based protocols in the future. The third invited talk was given by Xu Maozhi and described the state of the art in speeding up scalar multiplication on elliptic curves using efficiently computable endomorphisms. The sunday afternoon after the technical part of the conference was dedicated to a visit to the National Museum of Beijing, although some participants decided to rather enjoy the sunny weather for a visit to the Forbidden City.

  — Peter Schwabe

Posted in Uncategorized | Leave a comment

Elliptic Curve Cryptography in Practice

The recent paper Elliptic Curve Cryptography in Practice by Joppe W. Bos and J. Alex Halderman and Nadia Heninger and Jonathan Moore and Michael Naehrig and Eric Wustrow is well worth reading. The discovery in 2012 of a large number of RSA public keys with common factors showed that public key cryptography can go badly wrong in the real world. This paper reports on a thorough evaluation of ECC systems in the real world. Some of them, for example the Austrian e-ID citizen card, are found to have no weaknesses. However, serious issues are discovered with some other systems. In particular, the paper gives evidence that a theft of 59 bitcoins was achieved by an attacker exploiting duplicated nonces in ECDSA signatures. Further issues with bitcoin are discussed. The paper also reports some potentially serious bugs in TLS implementations in some commercially available devices. The paper does not reveal details of any companies or individuals affected by these issues.

— Steven Galbraith

Posted in Uncategorized | Leave a comment