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

Advertisements
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

Cryptographic tri-linear maps

Ming-Deh Huang has posted on arxiv the paper Trilinear maps for cryptography that proposes a cryptographic tri-linear map based on etale cohomology of abelian surfaces. Achieving multilinear maps is a major open problem, and already going from bilinear maps (pairings) to trilinear maps would have major implications in cryptography. It is too early for me to give any opinion on the security or correctness of this scheme.

Readers may be interested to watch this video of a lecture by Dan Boneh (from a few years ago) which is mostly about pairings but contains a segment around the middle that discusses multilinear maps (and trilinear maps in particular). Boneh even publicly commits to a US$ 1000 prize for a trilinear map. It will be interesting to see if Ming-Deg will be awarded this prize!

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Various news, mostly about isogeny cryptography

1. The NIST Post-Quantum Cryptography standardisation process has begun.
The Round 1 Submissions are here. Of particular interest to this blog is the SIKE proposal Supersingular Isogeny Key Encapsulation. The submitters of this proposal are David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Amir Jalali, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Joost Renes, Vladimir Soukharev and David Urbanik.

The submission contains an IND-CCA KEM based on SIDH. We briefly sketch the idea.
Let E be the base curve and let E_B be Bob’s public key (I’m omitting the points for brevity). The key encapsulation algorithm samples a random string m and computes the hash value r = G(m, E_B ). Then r is used to generate the ephemeral isogeny \phi : E \to E_A as in standard SIDH. The ciphertext includes E_A and F( j( E_{AB} )) \oplus m where F is another hash function. Decapsulation uses the usual SIDH ideas to compute j( E_{AB} ) and hence get m. Bob then recomputes r and verifies the correctness of all the computations by Alice.

I highly recommend to view this submission if you are interested in isogeny crypto.

The First PQC Standardization Conference will take place in Florida on April 12-13, 2018.

2. The conference PQ Crypto 2018 takes place in Fort Lauderdale, Florida on April 11-13, 2018. There are two papers about supersingular isogeny crypto:

  • Gustavo H. M. Zanon, Marcos A. Simplicio Jr, Geovandro C. C. F. Pereira, Javad Doliskani, and Paulo S. L. M. Barreto. Faster isogeny-based compressed key agreement.
  • Joost Renes. Computing Isogenies between Montgomery Curves Using the Action of (0,0).

3. I have posted to eprint the paper Authenticated key exchange for SIDH. The paper is a survey of issues and challenges with authenticated key exchange based on supersingular isogenies. I submitted a much less complete version of this paper to PQ Crypto and I am very grateful that it was rejected and that the referees told me lots of things I did not know about.

Some of the things I explain in this paper are: that an authenticated key exchange (AKE) protocol due to Jeong, Katz and Lee (from 2004) can be adapted to work with isogeny crypto; that this approach is more efficient than generic conversions from IND-CCA KEMs (e.g., the transform due to Boyd, Cliff, González Nieto and Paterson from 2009); that post-quantum security for AKE does not require quantum-secure arguments like the quantum random oracle model.

4. The Eurocrypt 2018 accepted papers are available. There are two papers that may be of particular interest to readers of this blog.

  • Henry Corrigan-Gibbs and Dmitry Kogan. The Discrete-Logarithm Problem with Preprocessing.
  • Kirsten Eisentraeger, Sean Hallgren, Kristin Lauter, Travis Morrison and Christophe Petit. Supersingular isogeny graphs and endomorphism rings: reductions and solutions.

    This paper is a merge of the two papers 2017/986 and 2017/962.

5. The first volume of IACR Transactions on Cryptographic Hardware and Embedded Systems is available. It will be good to keep an eye on this journal, which is the new publication outlet for the CHES conference. The first issue contains a paper about Diffie-Hellman on Kummer surfaces.

6. The submission deadline for ASIACRYPT 2018 is May 11. Please submit your best papers and enjoy a December break in wonderful Brisbane!

— Steven Galbraith

Posted in Uncategorized | Leave a comment