Asiacrypt 2018

Asiacrypt 2018 was held at QUT in Brisbane, Australia on December 2-6, 2018. It was wonderfully organised by Josef Pieprzyk.

The three plenary invited speakers were:

  • Mitsuru Matsui (Mitsubishi) “25 Years of linear cryptanalysis – Early History and Path Search Algorithm”

    Professor Matsui was the 2018 IACR Distinguished Lecturer. The talk reviewed the history and development of linear cryptanalysis.

  • Melissa Chase (Microsoft) “Picnic: Postquantum signatures from zero-knowledge proofs”

    Melissa gave an overview of the Picnic signature scheme, which beautifully combines ideas from multiparty computation and zero knowledge proofs, together with block ciphers and hash functions with low circuit complexity.

  • Vanessa Teague (Melbourne) “Democracy, security and evidence: Let’s have all three”

    Vanessa gave an overview of online voting schemes, including a detailed discussion of some real-world examples. The main focus of her talk was the problem of verifiable electronic voting.

The most relevant session for this blog was the session on isogeny crypto on the final morning. There were three talks:

  • Jean Kieffer “Towards practical key exchange from ordinary isogeny graphs” (joint work with Luca De Feo and Benjamin Smith)

    The talk presented an implementation of Couveignes’ hard homogeneous spaces concept with ordinary elliptic curves.

  • Lorenz Panny “CSIDH: An efficient post-quantum commutative group action” (joint work with Wouter Castryck, Tanja Lange, Chloe Martindale and Joost Renes)

    Building on work in the previous talk, the talk explained an implementation of Couveignes’ hard homogeneous spaces concept with supersingular elliptic curves. Using supersingular curves gives a massive performance improvement over the previous talk. Group actions like these have some advantages over SIDH, but are still slower.

  • Craig Costello “Computing supersingular isogenies on Kummer surfaces”

    The talk explained how to compute (chains of) 2-isogenies on an elliptic curve efficiently by converting them to (chains of) (2,2)-isogenies on the Kummer surface of the Weil restriction of the the elliptic curve.

There were also a number of accepted papers that used pairing-based crypto. To mention two of them: “Compact Multi-Signatures for Smaller Blockchains” by Dan Boneh, Manu Drijvers and Gregory Neven; “Unbounded Inner Product Functional Encryption from Bilinear Maps” by Junichi Tomida and Katsuyuki Takashima.

The Rump Session was superbly and irreverently chaired by Craig Costello, Leo Ducas and Pierre Karpman. One of the interventions perpetrated on the unsuspecting speakers was the introduction of humourous comments on their slides. But the major highlight of the rump session was the launch of the game “Cards against Cryptography”. It is a version of the famous card game “Cards against Humanity”, and has been designed by three anonymous cryptographers (not the rump session chairs). You can find out more by following @CrdsAgnstCrypto on twitter. A copy of this highly collectible and desirable game was awarded to each of the five best rump session talks. To buy extra time, speakers were invited to eat a spoonful of vegemite, or drink a beer. Another highlight of the rump session included the song “Gotta Break Em All” (about the NIST PQ Crypto competition) written by Leo Ducas and his partner Jessica, and performed by Peter Schwabe (on guitar), Chloe Martindale, Lejla Batina, Marcel Keller, Leo and Jessica.

Serious rump session talks included: Bart Preneel on how to steal a Tesla car; Suhri Kim on curve equations for isogenies; Daniel Bernstein on quantum circuits for class group actions (relevant for the analysis of Kuperberg’s algorithm as an attack on CSIDH); Chloe Martindale on choosing appropriate pairings for current security levels; Lorenz Panny on speeding up SeaSign isogeny signatures.

A small group of Asiacrypt attendees then flew to Adelaide for Kangacrypt. The workshop was mostly about cryptanalysis, especially fault attacks and side-channel attacks. But I did give (naturally enough) a talk about Kangaroos (ie., the Pollard kangaroo method for discrete logs and why it doesn’t work for isogenies).

— Steven Galbraith

Posted in Uncategorized | Leave a comment

ECC 2018, Osaka, Japan

As announced earlier on this blog, the 22nd Workshop on Elliptic Curve Cryptography took place at Osaka University, Japan, from November 19 to 21. This edition featured invited talks across a broad range of topics, from quantum information theory to homomorphic encryption to blockchains. As for elliptic curves specifically, the highlight was clearly isogeny-based crypto, explored in four different talks:

* David Jao discussed a number of techniques (from various authors) to achieve faster embedded implementations of SIDH, both in software using either vector instructions (like ARM NEON) or dedicated coprocessors, and on reconfigurable hardware. The talk was presented as a response to a recent paper by Koppermann et al. which had rather pessimistic conclusions regarding the usability of SIDH on smaller devices, mentioning 18 seconds as its headline timing for key exchange on 32-bit microcontrollers. David Jao argued that suitably optimized implementations could in fact do much better.

* Travis Morrison discussed some of his recent results (joint work with Eisenträger, Hallgren, Lauter and Petit) regarding the relationship between two computational problems connected to supersingular elliptic curves, namely pathfinding in the \ell-isogeny graph of supersingular elliptic curves over some \mathbb{F}_{p^2} (with \ell = O(\log p)) and the problem of computing the endomorphism ring of a supersingular elliptic curve. The main takeaway is that, assuming some heuristics, the two problems are polynomial-time equivalent.

* Chloe Martindale gave an excellent introduction to CSIDH (joint work with Wouter Castryck, Tanja Lange, Lorenz Panny and Joost Renes), which is a new instantiation of Couveignes-style hard homogeneous spaces using isogenies of supersingular elliptic curves over \mathbb{F}_p (as opposed to \mathbb{F}_{p^2}), which satisfy that the ring of rational endomorphisms is commutative. This provides a nice group action similar to the case of ordinary curves, but makes it possible to choose parameters in such a way that \ell-isogenies for many small primes \ell can be computed efficiently. This leads to a variant of the Couveignes-Rostovtsev-Stolbunov key exchange protocol that outperforms the original one by many orders of magnitude, achieving performance on the order of a few dozen milliseconds per key exchange.

* Finally, Katsuyuki Takashima discussed new isogeny-based authenticated key exchange protocols (joint work with Atsushi Fujioka and Kazuki Yoneyama). He showed how to obtain a one-round authenticated key exchange protocol using commutative group actions on isogeny graph. Assuming the existence of n-way cryptographic invariant maps, as suggested by Boneh et al., the protocol can be instantiated for an arbitrary number of parties. Unfortunately, it is not yet known how to construct such invariant maps (and as one of the culprits, I have to admit that the prospects of constructing them look rather remote). However, the two-party case only relies on Couveignes’s hard homogeneous spaces, and can thus be obtained from CRS or CSIDH.

There were many other excellent talks at the workshop, but some of them were not closely related to elliptic curves and so we don’t discuss them on this blog. Of particular notice besides isogenies was Pierrick Gaudry’s presentation on point counting in higher genus (joint work with Simon Abelard and Pierre-Jean Spaenlehauer). He showed how to compute the zeta function of a hyperelliptic curve of genus g over \mathbb{F}_q in time O_g((\log q)^{O(g)}), greatly improving upon the previous complexity, with an exponent quasi-quadratic in g. He also discussed concrete results for g=3, establishing that the correct complexity was (\log q)^{14} for general hyperelliptic curves, and (\log q)^{6} for Jacobians with real mutiplication. In the latter case, the complexity becomes tractable even for cryptographic sizes, and Pierrick was able to show us the whole zeta function for a curve over \mathbb{F}_p with p=2^{64} - 59.

— Mehdi Tibouchi

Posted in Uncategorized | Leave a comment

Mathematics of Public Key Cryptography textbook free

I have made available for free a corrected version of my book “Mathematics of Public Key Cryptography”. You can access it here. I have fixed all the typos and errors that I was aware of (most of them documented in the errata list), plus I have added two or three new examples and exercises. I thank everyone who found errors or gave feedback on the original version.

Sadly, the book is not updated to discuss new research since 2011. I don’t have time to do that.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

ECC 2018 Conference, Osaka, Japan

Registration is open for this years Elliptic Curve Cryptography conference. For details, including the full list of speakers, visit the conference website.

There will be a “autumn school” on November 17-18, followed by the main conference on November 19-21.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

MathCrypt 2018

The MathCrypt 2018 event (affiliated with Crypto 2018) took place in Santa Barbara CA on the 19th of August. Five out of fifteen talks were devoted to Elliptic Curve Cryptography. The slides of talks are available on the conference website.

An improvement to the quaternion analogue of the L-isogeny path problem, by Spike Smith

This talk focused on the analogue of the l-isogeny path problem, important for the security of the Charles-Goren-Lauter hash function, under the Deuring correspondence between supersingular elliptic curves and left ideals of quaternion orders. While an algorithm by Kohel-Lauter-Petit-Tignol is known that solves the problem in probabilistic polynomial time, this work improves on the run time of the algorithm, and the size of the solution that is found. This improvement allows for smaller signatures in the Galbraith-Petit-Silva identification protocol. Two more significant improvements to the KLPT are being developed and will be published in an extended version of the paper.

Multi-Party Non-interactive Key Exchange and more from Isogenies on Elliptic Curves, by Dan Boneh

The room was packed for the talk about “Multi-Party Non-interactive Key Exchange and more from Isogenies on Elliptic Curves”. Dan reminded the audience of cryptographic group actions such as CRS and CSIDH and how they give rise to elegant Post Quantum secure Diffe-Hellmann like protocols. Then he talked about the new paper which introduces a new generalization of cryptographic group actions that would result in NIKE, BLS signatures and more. The paper gives a candidate construction of this powerful new primitive apart from the fact that one crucial ingredient, namely an efficiently computable isomorphism invariant of a product of elliptic curves, is missing.

Extra Secrets from Automorphisms and SIDH-based NIKE, by David Urbanik

The basic observation underlying this talk is that when doing SIDH starting from a curve which has nontrivial automorphisms, it is possible to exploit these automorphisms to derive multiple secrets for the same pair of public keys. This can be used to protect against the GPST attack and obtain non-interactive key exchanges in ways that are more efficient than previous approaches.

A new Poly space attack on CRS and CSIDH, by Jason Legrow

This work gives a new implementation of Regev’s quantum algorithm for inverting the CM action which can be used to attack the CRS and CSIDH cryptosystems. Like earlier attacks, the time and space complexity of the attack is subexponential, however the advantage of the new attack is that it only requires polynomial quantum space. The problem with previous attacks was that evaluating the CM action (which happens in superposition) required subexponential time and space. This is solved with a purely classical precomputation that allows the CM action to be evaluated in subexponential time, but in polynomial space, eliminating the need for subexponential amounts of quantum memory.

Quasi-subfield polynomials and the Elliptic Curve Discrete Log Problem, by Michiel Kosters

This work investigates if it is possible to generalize index calculus attacks to break the ECDLP problem for curves over the field GF(p^n), where p is a small prime, and n is a prime. The main idea is to replace the subfield polynomial X^p - X, which is used in the usual Gaudry/Diem-type index calculus attack on curves over GF(p^n) with large p, and replace this polynomial by a polynomial of the form f(X) = X^{p^{n'}} - \lambda(X), where \lambda(X) has small degree such that f(X) splits completely over GF(q^n). To make the index calculus algorithm efficient the degree of \lambda is low. When the degree of \lambda is low enough, the polynomial f(X) is called a quasi-subfield polynomial. Quasi-subfield polynomials can be used to solve the ECDLP slightly faster than with exhaustive search, but to improve over the baby-step giant-step algorithm much better quasi-subfield polynomials would need to be found.

— Ward Beullens

Posted in Uncategorized | Leave a comment

ANTS 2018

The Thirteenth Algorithmic Number Theory Symposium took place at the University of Wisconsin, Madison on July 16-20, 2018.

The Invited speakers were:

  • Jennifer Balakrishnan “Effective aspects of quadratic Chabauty

    Jennifer explained Minhyong Kim’s non-abelian Chabauty framework to obtain an effective methods for determining the rational points on a curve using Coleman integrals. She explained how p-adic heights provide a bilinear function that enables Kim’s approach to be performed in the “quadratic” case. She surveyed new results, including resolving the problem of rational points on the “cursed curve” that parameterises split Galois representations of level 13.

  • Noam Elkies “Curves with many points over number fields

    Noam demonstrated constructions of infinite families of curves over Q of fixed genus with many rational points.

  • Steven Galbraith “Current trends and challenges in post-quantum cryptography

    The talk gave an overview of post-quantum crypto and the NIST standardisation process, then listed a number of open problem in isogeny crypto. Slides are here:

  • Melanie Matchett Wood “Effective Chebotarev density theorems for families of number fields without GRH

    Melanie surveyed her joint work with Lillian Pierce and Caroline Turnage-Butterbaugh on effective Chebotarev density theorems for certain families of number fields (the fields in each family all have the same Galois group).

  • Emmanuel Thomé “Computation of discrete logarithms in finite fields

    Emmanuel gave an overview of number field sieve algorithms for discrete logarithms in \mathbb{F}_{p^n}, including recent research on variants for different regions of interest in terms of (p,n). He also mentioned the LOGJAM attack on TLS (from 2015) and the “hidden-SNFS” 1024-bit discrete logarithm (2016).

The contributed papers included the following of interest to ECC researchers:

  • S. Abelard, P. Gaudry and P.-J. Spaenlehauer, Counting points on genus-3 hyperelliptic curves with explicit real multiplication. The paper is about Schoof-type algorithms for point counting on genus 3 hyperelliptic curves over finite fields.
  • T. Kleinjung and B. Wesolowski, A new perspective on the powers of two descent for discrete logarithms in finite fields. The paper is about the descent step in quasi-polynomial-time algorithms for the DLP in \mathbb{F}{p^n} for small p and large n.
  • A. V. Sutherland, Fast Jacobian arithmetic for hyperelliptic curves of genus 3. This paper gives formulas for fast computation of divisor class groups of genus 3 curves with two points at infinity.
  • B. Wesolowski, Generating subgroups of ray class groups with small prime ideals. The paper has results about isogeny graphs in higher dimensions.

The winners of the Selfridge Prize for best paper were Michael Musty, Sam Schiavone, Jeroen Sijsling and John Voight for their paper “A database of Belyĭ maps”.

The poster prize was awarded to Travis Scholl for his poster on “Isolated Abelian Varieties over Finite Fields”. Here is a list of all the posters.

The Rump session took place late on the Thursday afternoon. I put up an announcement for ECC 2018 at Osaka Japan on November 19-21 (preceded by a 2 day autumn school). The rump session also included by presentation by Benjamin Smith giving a general way to break tri-linear maps of the type proposed by Huang, by using the intersection pairing on the endomorphism ring.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Tri-linear maps from elliptic curves and abelian surfaces

I spent the last week in beautiful Banff at the BIRS workshop on An Algebraic Approach to Multilinear Maps for Cryptography. The workshop participant photo is notable, as the age gap between the oldest and youngest person in the photo is more than 100 years. Three of the talks can be viewed online. I spent most of the time working with Ming-Deh Huang and others on the ideas in his preprint Trilinear maps for cryptography. This preprint sketches some ideas that might lead to a tri-linear map. (In the photo: Huang is in the front row, wearing sunglasses and standing beside Hendrik Lenstra; I’m at the back, hiding behind Boneh and Sahai.)

I am going to describe a simple (but insecure) example that will allow to communicate the main ideas of the proposal.

Let E be an ordinary pairing-friendly elliptic curve over \mathbb{F}_p and let \ell \mid \#E( \mathbb{F}_p ). Let e_\ell be the Weil pairing on E[\ell], meaning that e_\ell : E[ \ell ] \times E[ \ell ] \to \mu_\ell \subseteq \mathbb{F}_{p^k}^* for some integer k (the “embedding degree”), where \mu_\ell is the cyclic multiplicative group of order \ell.

Write \pi for the p-power Frobenius map \pi(x,y) = (x^p, y^p) on E. Note that \mathbb{Z}[\pi] \subseteq End(E).

The construction is to choose a random Q \in E[\ell] and random integers A, B \in \{ 0,1,\dots, \ell-1\}. Huang defines \lambda = A + B \pi to be an endomorphism on E, and sets P = \lambda(Q) = [A]Q + [B]\pi(Q). With high probability e_\ell( P, Q ) \ne 1 (if not then repeat the construction for another point P).

The key idea is that one can now “encode” three integers a, b, c \in \{ 0,1,\dots, \ell-1\} as follows. Encode a as the group element [a]P \in E[ \ell ], encode b as the group element [b]Q, encode c as the endomorphism \phi_c = c  + u \lambda where u is chosen uniformly at random in \{ 0,1,\dots, \ell-1\}. More precisely, \phi_c is represented as x + y \pi where x = c + Au \pmod{\ell} and y = Bu \pmod{\ell}. One can compute \lambda(Q) efficiently as [x]Q + [y] \pi(Q). Since the Weil pairing is alternating we have e_\ell( P , \lambda( Q )) = e_\ell( P, P ) = 1.

So e_{\ell}( [a]P, \phi_c( [b]Q )) = e_{\ell}( [a]P, (c + u \lambda)( [b]Q )) = e_\ell( [a]P , [cb]Q + [cbu] \lambda(Q)) = e_\ell( P, Q)^{abc}.

In other words, we have a tri-linear map e : G_1 \times G_2 \times G_3 \to \mu_\ell where the three sets G_i are “encodings” of \mathbb{Z} / \ell \mathbb{Z}. Note that the integers a and b are “hidden” due to the hardness of the discrete log problem, and G_1, G_2 are groups. While the integer c is hidden by the “random blinding” by a random multiple of \lambda.

The bad news about this particular example is that it is not secure. Since \lambda = A + B \pi is public, an attacker who sees the encoding x + y \pi in G_3 can easily solve for c and u. In other words the “discrete log problem” in G_3 is easy to solve.

We now briefly mention why this tri-linear map concept avoids the negative results by Boneh and Silverberg in their paper Applications of Multilinear Forms to Cryptography. In short, the set G_3 is “weight zero” in the motivic language of Section 7.4 of Boneh-Silverberg. One topic of discussion at the BIRS meeting last week was whether or not weight zero objects always have weak discrete logarithms. As far as I can tell the outcome was inconclusive.

Huang’s actual proposal is to work on a 2-dimensional Abelian variety that is pairing friendly and has a non-commutative endomorphism ring. The idea is to publish a set of endomorphisms (extending the single endomorphism \lambda in the above example) that can be used to “hide” an integer c when encoding it in G_3. Instead of representing these endomorphisms with respect to some \mathbb{Z}-module basis (such as x_0 + x_1 \pi + x_2 \pi^2 + x_3 \pi^3), which would be insecure, the suggestion is to represent endomorphisms using low degree rational functions on the Abelian surface. This is a very interesting idea, but more work is needed to determine if such an system is secure and efficiently computable.

— Steven Galbraith

Posted in Uncategorized | 2 Comments