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

Advertisements
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: http://www.math.grinnell.edu/~paulhusj/ants2018/TalkSlides/Galbraith.pdf.

  • 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

Eurocrypt 2018

This week Eurocrypt 2018 took place in Tel Aviv, in a hotel next to the marvellous beach. Despite the splendid weather and the tempting conference gift (a bath towel — that’s letting the fox into the hen house), there were many reasons to stay inside, thanks to the nice line up of speakers and the flawless organization. To name one highlight, Matthew Green’s invited talk on “Thirty years of digital currency: from DigiCash to Bitcoin” was particularly enjoyable. And so was the hummus, by the way!

Elliptic curves were a bit underrepresented though, with only one session talk explicitly devoted to them. Christophe Petit spoke about “Supersingular isogeny graphs and endomorphism rings: reductions and solutions”, which arose as a merge of a paper by him and Kristin Lauter and a paper by Kirsten Eisenträger, Sean Hallgren and Travis Morrison. In his talk, Christophe mainly focused on the security of the Charles-Goren-Lauter (CGL) hash function, which is based on the hardness of finding a cycle in the ell-isogeny graph (typically ell = 2) of supersingular elliptic curves over a large quadratic finite field \mathbb{F}_{p^2}. He related the security of the CGL hash function to the problem of computing the endomorphism ring of a given supersingular elliptic curve (while removing some ambiguity on what is meant by this) and to the problem of making Deuring’s correspondence effective. The most interesting outcome is a polynomial-time collision algorithm in case the initial curve is “special”, i.e., if it has a well-known endormorphism ring. This is worrisome, because it is an open problem how to generate a genuinely random “non-special” supersingular elliptic curve over \mathbb{F}_{p^2}, so this potentially opens the door to backdoored versions of the CGL hash function.

Other talks of relevance to ECC included:

  • Henry Corrigan-Gibbs gave a nice talk on the discrete logarithm problem (DLP) in general, reporting on a paper that he wrote together with Dmitry Kogan, which won the best young research award. He recalled that a massive preprocessing phase can reduce the hardness of the DLP in a generic group G of order N from O(N^{1/2}) to O(N^{1/3}). Their contribution is a Shoup-type result stating that this is optimal in the generic group model. Interestingly, they also reveal a dichotomy with the decisional Diffie-Hellman problem, in that they provide an O(N^{1/5}) algorithm for distinguishing triples of the form (g, g^x, g^{(x^2)}) from random triples in G^3, again using a very large amount of preprocessing.
  • Another interesting talk was given by Yilei Chen on joint work with Ran Canetti, Leonid Reyzin and Ron Rothblum, on the Fiat-Shamir transformation of a three-round public-coin identification scheme into a one-round digital signature scheme. He saw an analogy with transforming an elaborate USA-style conversation into a brief no-nonsense Israeli one. Chen and his coauthors constructed two families of so-called “correlation-intractable” hash functions, one of which uses elliptic curves. If you want to obtain a provably secure digital signature scheme from a hash function through Fiat-Shamir, then correlation intractability is the property you want.
  • In the rump session I gave a short talk about CSIDH, a compact non-interactive key exchange protocol designed together with Tanja Lange, Chloe Martindale, Lorenz Panny and Joost Renes. It is obtained by applying the Couveignes-Rostovtsev-Stolbunov scheme to the set of supersingular elliptic curves over a large prime field \mathbb{F}_p, rather than to ordinary elliptic curves. This choice was motivated by recent work of Luca De Feo, Jean Kieffer and Ben Smith on speeding up the ordinary Couveignes-Rostovtsev-Stolbunov scheme: one of their proposed speed-ups works particularly well in the supersingular setting.

All slides can (or will) be found on the conference web page, see https://eurocrypt.iacr.org/2018/

— Wouter Castryck

Posted in Uncategorized | Leave a comment

114-bit ECDLP solved on a curve with automorphisms over a prime field

There was a new ECDLP record that I missed last year. There was a press release on August 23, 2017. Now there is more information.

The details are published in the paper Solving 114-bit ECDLP for a Barreto-Naehrig Curve by Takuya Kusaka, Sho Joichi, Ken Ikuta, Md Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai and Sylvain Duquesne (appeared in proceedings of ICISC 2017).

The curve is a pairing-friendly BN curve over a prime field F_p. The curve has j-invariant 0, and so has an automorphism group of size 6. Hence, it is possible to perform the Pollard rho algorithm using equivalence classes of size 6.

I got a few more details from the authors. They used n = 1024 partitions for the random walk, and the “hash function” \eta was chosen to be the least significant \log_2(n) bits of the x-coordinate of the current curve point.

The paper writes that “The parallel implementation of the rho method by adopting a client-server model, using 2000 CPU cores took about 6 months”. They seem to have been lucky to get a collision earlier than expected: “the result of the authors attack is little bit better than the average number of rational points where a simple collision attack stops.”

The previous ECDLP record (due to Bos, Kaihara, Kleinjung, Lenstra and Montgomery) in the F_p case was a 112-bits group size, published in 2012.

— Steven Galbraith

PS. It has been pointed out in the comments that there are other recent ECDLP records, such as the 118 bit record computation by Bernstein, Engels, Lange, Niederhagen, Paar, Schwabe and Zimmermann. This is a characteristic 2 computation, whereas I was focussed in this blog post on the F_p case. But still it is a notable computation and should be celebrated.

Posted in Uncategorized | 1 Comment

Isogeny crypto at PQCrypto 2018

The PQ Crypto conference took place in sunny Fort Lauderdale, Florida in April 2018. It was extremely well attended (around 350 participants).

The three plenary lectures were:

  • Jean-Pierre Tillich, Attacks in code based cryptography: a survey, new results and open problems.

    The talk surveyed code-based crypto (both within the NIST submissions, and over its entire history) and various types of attacks.

  • Dave Wecker, Achieving practical quantum computing.

    The talk gave a wide-ranging overview of the potential applications of quantum computing (especially in modelling for quantum chemistry), the engineering challenges of building a quantum computer (with focus on practical concerns such as cooling and the interface between classical computing control systems and the quantum system), and the work being done globally by Microsoft research. Dave predicts that Microsoft will have a quantum computer suitable for chemistry applications within 5 years and “something of interest to this crowd” in 10 years.

  • Dustin Moody, Let’s Get Ready to Rumble: The NIST PQC `Competition’.

    This was an overview of the NIST post-quantum standardisation process, including a discussion of the goals and evaluation criteria. The talk also presented a few graphs that give a rough comparison of submissions according to features like key size, computation time, etc.

The session on isogeny crypto had two papers:

  • Joost Renes talked about a method to derive very nice formulae for writing isogenies as explicit rational functions.
  • Geovandro Pereira presented his joint paper with Zanon, Simplicio, Doliskani and Barreto. This work is about efficient methods for compressed supersingular isogeny Diffie-Hellman (SIDH). The goal is to minimise the bandwidth in the SIDH protocol by compressing the protocol messages, and to minimise the cost of de-compressing these values to complete the protocol. The paper makes excellent use of a lot of really nice tricks, including techniques for efficient computation of pairings and Shoup’s optimised variant of the Pohlig-Hellman algorithm.

The contributed talks included sessions on code-based crypto, lattices, hash-based crypto, multivariate crypto. There were also papers on cryptanalysis of post-quantum cryptosystems and quantum algorithms.

The recent results session contained three talks on isogeny crypto:

  • Sam Jaques explained that Tani’s claw finding quantum attack on SIDH might be slower than estimated in the SIKE NIST submission. He suggests that the security level of the NIST submission attains higher security levels than claimed.
    Ray Perlner has also posted a comment on the NIST PQCrypto mailing list suggesting this. Ray references independent works by Dan Bernstein, Scott Fluhrer, and himself on hash collisions, that argue that storage costs cannot be neglected in the complexity estimates. He writes “the quantum algorithm for collision search is no better than the best classical algorithms in any physically plausible model of computation”.

  • Lorenz Panny sketched a variant of SIDH based on the curves with j-invariant in {\mathbb F}_p. The idea is to implement the group action key exchange protocol due to Couveignes, and so to avoid having to send points. A preprint will be made public soon.
  • Aaron Hutchinson discussed joint work on efficient implementation of SIDH by exploiting parallelism. They consider the de Feo, Jao, Plut optimised method to compute \ell^e-isogenies in a multi-core setting.

Not presented at this conference, but also relevant: Gora Adj, Daniel Cervantes-Vázquez, Jesús-Javier Chi-Domínguez, Alfred Menezes and Francisco Rodríguez-Henríquez have posted on eprint the paper On the cost of computing isogenies between supersingular elliptic curves. The paper is about classical algorithms and they show how the low-storage algorithm due to van Oorschot and Wiener can be applied to isogeny problems. Again, they argue that storage costs should not be neglected and suggest that the stated security levels have been under-estimated. They suggest using somewhat smaller primes for SIDH. This reinforces the claims made by Jaques/Perlner/et al.

— Steven Galbraith

Posted in Uncategorized | Leave a comment