Like every three years since 2010, CRYPTO and CHES this year were jointly held at the University of California Santa Barbara on the third week of August, and featured the usual chocolate strawberries, beach barbecue and India pale ale.

The scientific programs of both conferences overlapped somewhat (the CRYPTO program ran from Monday through Thursday morning, while CHES ran from Wednesday to Friday with optional tutorials on Tuesday), and CRYPTO now has parallel sessions, so attendees to both conferences effectively had to choose between three parallel tracks. Yet you could probably attend all the talks related to elliptic curve cryptography, as there just weren’t that many.

At CRYPTO, the two most relevant presentations were given in the Algorithmic Number Theory session on Wednesday morning:

• Taechan Kim presented his paper with Razvan Barbulescu, “Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case”, about which Aurore Guillevic wrote an extensive survey on this blog a few months ago. The paper obtains a better complexity for the discrete logarithm problem in some composite degree extensions of finite fields, and although Taechan spent a good part of his talk trying to downplay the concrete impact, it actually translates to a significant reduction in the security of the most popular pairing-friendly elliptic curves. In particular, after this attack, 256-bit Barreto-Naehrig curves no longer offer 128 bits of security, but perhaps closer to 96 or so.
• Craig Costello presented his paper with Patrick Longa and Michael Naehrig, “Efficient Algorithms for Supersingular Isogeny Diffie-Hellman”, which uses a number of clever tricks to implement the postquantum-secure isogeny-based key exchange protocol of De Feo, Jao and Plût significantly more efficiently than what previously thought possible. Although SIDH still lags behind other popular postquantum constructions based e.g. on lattices by several orders of magnitude in terms of performance, it uses comparatively short keys, can be combined with classical ECDH very cheaply, and in any case is based on a very different type of security assumption that may look more appealing to the algebraic geometrically inclined.

Other papers related to elliptic curves include:

• “Design in Type-I, Run in Type-III: Fast and Scalable Bilinear-Type Conversion using Integer Programming” by Masayuki Abe, Fumitaka Hoshino and Miyako Ohkubo, which explains how to algorithmically convert pairing-based protocols using symmetric pairings to the asymmetric setting at a minimal overhead using integer linear programming techniques;
• the CRYPTO best paper, “Breaking the Circuit Size Barrier for Secure Computation Under DDH“ by Elette Boyle, Niv Gilboa and Yuval Ishai, which is not elliptic curve crypto per se, but relies on an interesting observation regarding discrete logarithms. The idea is that if two parties hold a secret sharing of a small value in the exponent, i.e. and with , they can derive from that an additive secret sharing of itself without any interaction. To do so, they agree on a polynomially dense subset of distinguished points in the group, and count how many steps it takes to reach an element of from their respective share. If is small enough compared to the relative density of , they should reach the same element of with good probability, and in that case, if it took (resp. ) steps for the first (resp. second) party, we have , hence : is a secret sharing of obtained without interaction!

At CHES, on the other hand, there were several interesting papers about the implementation of elliptic and hyperelliptic curve cryptography on various platforms.

• On desktop CPUs: the paper by Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez, “Software Implementation of Koblitz Curves over Quadratic Fields”. Usual Koblitz curves are defined over and use the fast Frobenius endomorphism instead of doublings to speed up scalar multiplication. This paper instead investigates curves defined over together with the corresponding, slightly less fast Frobenius , and shows that the quadratic extension structure of the corresponding fields yields interesting performance benefits. The authors obtain a constant time scalar multiplication in under 70k cycles on Haswell and 52k cycles on Skylake at the 128-bit security level, which is quite respectable, even though they have to rely on a suboptimal field size of close to 300 bits to find a curve with a sufficiently large prime subgroup.
• On embedded CPUs: the paper by Leijla Batina, Joost Renes, Peter Schwabe and Benjamin Smith, “µKummer: Efficient Hyperelliptic Signatures and Key Exchange on Microcontrollers”. It is well-known that Kummer surfaces support a notion of scalar multiplication, but not point addition directly because it is not compatible with quotienting by . As a result, they would only be used for protocols like Diffie-Hellman, and not for e.g. signatures, which require point additions. However, Chung, Costello and Smith recently observed that you can simply lift back to the actual Jacobian after carrying out your fast variable base point multiplication on the Kummer, and doing so is likely to be faster than doing everything in a Jacobian, especially if you want constant time arithmetic. This CHES paper is a concrete demonstration of that idea on constrained software platforms (AVR ATmega and ARM Cortex M0), where the authors break earlier speed records for (H)ECC by wide margins.
• In hardware: the paper by Kimmo Järvinen, Andrea Miele, Reza Azarderakjsh and Patrick Longa, “FourQ on FPGA: New Hardware Speed Records for Elliptic Curve Cryptography over Large Prime Characteristic Fields”. FourQ is a very nice curve introduced by Costello and Longa at last year’s ASIACRYPT, which currently holds essentially all of the speed records on desktop CPUs for constant-time scalar multiplication (both fixed and variable base) by a comfortable margin. This CHES paper implements it on FPGA, and finds that it also performs faster than other implementations over large characteristic fields (although not nearly as fast as comparable binary field designs).

The CHES rump session also featured some annoucements of note, including a concrete complexity estimate by Francisco Rodríguez-Henríquez and his colleagues of the quasilinear attack on discrete logs in the formerly 128-bit secure field that used to be recommended for pairings (answer: if everybody in the world was working on it 8 hours per day, 1000 multiplications per hour, it would only take about 10 months!). The annoucement that personally got me the most excited is an improved implementation result for the binary curve GLS254 on desktop CPUs due to Thomaz Oliveira, Diego Aranha, Julio López and Francisco Rodríguez-Henríquez, who adapted techniques from the quadratic Koblitz paper above to blow up the competition again with that curve: at 48k cycles on Haswell and 38k cycles on Skylake for 128-bit secure scalar multiplication, it is even faster than Kummers and FourQ!

— Mehdi Tibouchi