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

Advertisements
Posted in Uncategorized | Leave a 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

ASIACRYPT 2017

ASIACRYPT 2017 took place in Hong Kong and had a large number of talks with elliptic curve and/or number-theoretical content.

The three invited talks were:

  • Dustin Moody The ship has sailed: the NIST Post-Quantum Cryptography “competition”. This talk gave a summary of the NIST post-quantum crypto standardisation process. The deadline for submissions was only 3 days before the conference so there had not been enough time yet for NIST to determine which submissions were “complete and proper” according to their criteria. Hence the talk did not list the actual submissions or give any details of particular submissions. However, it is known that there is one supersingular isogeny (SIDH) submission to the process.

    Mostly Dustin discussed the process up to this point, and the expectations of NIST for the coming stages of the process. Proposals were invited for either signature schemes or else public key encryption/key encapsulation schemes. Dustine emphasised that there is no single technology that provides all the desired features (“no silver bullet”) and that post-quantum crypto is a complex area that is still actively being researched. As a result, NIST is expecting to standardise several different schemes in each category.

    The slides of Dustin’s talk are here.

  • Huaxiong Wang Combinatorics in Information-Theoretic Cryptography surveyed how various areas of combinatorics have been used in various ways in crypto.
  • Pascal Paillier White-box Cryptomania explained the concept of white-box crypto and urged theoretical researchers to get involved in this area. He reported on the recent WhibOx challenge, all submissions to which were broken. It is fair to say that Pascal received vigorous questioning after his talk, and that several individuals in the audience were not convinced by his arguments.

    Two elliptic curve papers were highlighted in the “best paper” and “invited to Journal of Cryptology” category, and even the SNARKs paper (see below) uses pairings:

    • Steven D. Galbraith, Christophe Petit and Javier Silva Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems. I have a conflict of interest, so I won’t say too much about this paper. It is about post-quantum signatures from isogenies. The main contribution is to give a scheme based on the general endomorphism/isogeny problem, rather than the “special” isogeny problem used in SIDH key exchange. I should mention that the signature is not very efficient and is not recommended for practical use. The talk was presented by Javier.
    • Sabyasachi Karati and Palash Sarkar Kummer for Genus One over Prime Order Fields. This paper is about efficient “x-coordinate only” type arithmetic on elliptic curves. The performance results are excellent. The natural question is how this relates to Montogomery curves.
    • Behzad Abdolmaleki, Karim Baghery, Helger Lipmaa and Michal Zajac A Subversion-Resistant SNARK.

    Finally, there were many other contributed talks of interest to a mathematical audience.

    • Dominique Unruh Post-Quantum Security of Fiat-Shamir discussed the Fiat-Shamir transform in the quantum random oracle model. Previous work has given more complex transforms that turn an interactive sigma protocol (identification scheme) into a non-interactive signature scheme. Unruh’s result is that if the public key is “lossy” (he calls it “dual-mode hard instance generator”) then the basic Fiat-Shamir transform can be applied. For a similar result see Kiltz, Lyubashevsky and Schaffner eprint 2017/916.
    • There was a session on lattices, with several papers about algorithmic results and/or hardness. It comprised: Martin R. Albrecht and Amit Deo Large Modulus Ring-LWE >= Module-LWE; Martin R. Albrecht, Florian Göpfert, Fernando Virdia and Thomas Wunderer Revisiting the Expected Cost of Solving uSVP and Applications to LWE; Qian Guo, Thomas Johansson, Erik Mårtensson and Paul Stankovski
      Coded-BKW with Sieving; Thomas Prest Sharper Bounds in Lattice-Based Cryptography using the Rényi Divergence.

    • There was a whole session on Homomorphic Encryption and a whole session on Pairings. In particular, Jens Groth gave a lecture presenting two “uber assumptions” for pairing-based crypto which provide the “best” targets for cryptanalysis.
    • Martin Roetteler, Michael Naehrig, Krysta M. Svore and Kristin Lauter Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. This papers counts the number of Toffoli gates to perform elliptic curve arithmetic over a finite field of real-world size on a quantum computer. This therefore gives an estimate of the number of gates required to run Shor’s algorithm for ECDLP.

    • Joost Renes and Benjamin Smith qDSA: Small and Secure Digital Signatures with Curve-based Diffie-Hellman Key Pairs gives a signature scheme suitable for x-coordinate-only arithmetic. Signature verification in ECDSA requires computing [s]P + [c]Q and checking if this is equal to R. The new scheme computes x( [s]P ) and x( [c]Q ) using ladder algorithms and then cleverly checks if x(R) can be equal to either x( [s]P + [c]Q ) or x( [s]P - [c]Q ). The scheme can be used for elliptic curves or Kummer varieties of hyperelliptic curves. They note that FourQ is faster, but FourQ uses special curves.
    • Craig Costello and Hüseyin Hisil A simple and compact algorithm for SIDH with arbitrary degree isogenies discussed doing SIDH with isogenies of degree \ell > 3. Currently there is no application for this question, but the paper is nice anyway.
    • Christophe Petit Faster Algorithms for Isogeny Problems using Torsion Point Images introduces a very interesting and original idea to cryptanalyse the SIDH problem. In particular, his result uses the auxiliary points that are one of the concerning elements of the SIDH problem. The method does not succeed in breaking the current schemes, but would break variants of SIDH with “unbalanced” parameters.
    • Rex Fernando, Peter M.R. Rasmussen and Amit Sahai Preventing CLT Attacks on Obfuscation with Linear Overhead gave an approach to prevent an attack on the Coron-Lepoint-Tibouchi multilinear map. This seems to be a very interesting result.

    — Steven Galbraith

Posted in Uncategorized | Leave a comment

CRYPTO 2017

Last week, Crypto 2017 took place at UC Santa Barbara. There were more than 425 attendees for this year’s 4-day conference, with 72 papers being presented.

Eclipse peeking through the cloudsMonday morning was interrupted by a very special coffee break: the ecliptic curve cryptography coffee break, a.k.a. viewing the solar eclipse. General Chair Steve Myers had very conveniently ordered solar eclipse glasses for everyone (from a legitimate vendor!). The sky was cloudy during the coffee break, but the eclipse occasionally peeked through, and the skies cleared afterward for a clearer view of the eclipse.

Later that morning, John Martinis, a physicist from UCSB, gave an invited lecture on the prospects of a quantum factoring (and, presumably, discrete logarithm-ing) machine.

On Monday afternoon, Yehuda Lindell gave a talk on his paper Fast Secure Two-Party ECDSA Signing. Fast protocols exist for many factoring-, discrete logarithm-, and elliptic curve-based signature and public key encryption schemes. DSA and ECDSA are tricky because signing involves operations both additive and multiplicative operations using $k$ and $k^{-1}$, but in a threshold scheme this must be done without knowing $k$. Past work by MacKenzie and Reiter (Crypto 2001) and Gennaro, Goldfeder, and Narayanan (ACNS 2016) gives two-party protocols for computing ECDSA using multiplicative sharing of the signing key $x$ and ephemeral secret $k$ and then Paillier encryption to combine their equations. Proving honest behaviour ends up being quite expensive, unfortunately. Lindell showed how to improve performance by simplifying the shared tasks that one of the party participates in while still using Paillier homomorphic encryption. The key idea is that the second party, before releasing the signature, can check whether the first party behaved honestly simply by checking the final signature, which is publicly checkable efficient by definition of a digital signature scheme. The paper reports experimental results that show that two-party signing for ECDSA (with the NIST P-256 curve) can be run in approximately 37 milliseconds. The techniques also apply to DSA.

Tuesday featured the three award papers. Sam Kim and David J. Wu won the best student paper award for Watermarking Cryptographic Functionalities from Standard Lattice Assumptions. Best paper awards went to Nico Döttling and Sanjam Garg for Identity-Based Encryption from the Diffie-Hellman Assumption and Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov for The first collision for full SHA-1.

Döttling and Garg’s paper showed how to construct identity-based encryption from the computational Diffie–Hellman problem in any group, including elliptic curve groups. Previous results had shown it impossible to construct IBE in a black-box way from CDH, so this paper had to make non-black-box use of the underlying cryptographic primitives. While the scheme is polynomial-time, this non-black-box use ends up making the scheme quite inefficient. On Wednesday another paper expanded the set of assumptions from which one can construct identity-based encryption: Identity-based Encryption from Codes with Rank Metric.

R, S, and A on stage at the Crypto 2017 rump session Tuesday evening featured the annual rump session, including the program chair’s report, reminiscences, announcements, songs, joke talks, and, unfortunately, some serious talks too. Most poignant was the second talk, entitled “Forty years and still running”. Jean-Jacques Quisquater presented a list of cryptosystems still running after 40 years, including the DES/Triple-DES algorithm and the RSA cryptosystem. In fact, 2017 marks the 40th anniversary of the invention of RSA, and Quisquater had arranged a wonderful surprise: Ron Rivest, Adi Shamir, and Leonard Adleman were all present for the rump session, and they took the stage to commemorate this milestone.

Later in the rump session, Michael Naehrig, co-inventor of the Barreto–Naehrig (BN) family of elliptic curves, performed (via Youtube) his original song The Sound of Quantum.

On Wednesday, Cédric Fournet of Microsoft Research Cambridge gave the second invited talk on Project Everest, a massive multi-institution multi-year project to create a fully verified efficient implementation of the TLS protocol. One component of Everest is a verified implementation of Curve25519 in a language called HaCL*, which compiles down to verified C code. This invited lecture was a joint talk between Crypto 2017 and the 30th IEEE Computer Security Foundations Symposium (CSF), also taking place at UCSB last week.

The full proceedings of Crypto 2017 are available on SpringerLink:

Crypto 2018 will take place in August 2018 at—where else?—UC Santa Barbara.

— Douglas Stebila

Posted in Uncategorized | Leave a comment

Isogeny-based post-quantum crypto

I’ve been meaning to write about isogeny-based crypto for a long while. This area has steadily become more and more active and there are now many researchers working seriously on it. The main motivation is its potential to provide a key exchange primitive that is efficient enough for practical deployment, yet potentially secure against an adversary with a quantum computer.

The first suggestions to use isogenies in crypto were due to Couveignes (in a talk in 1997), Charles, Lauter and Goren (a hash function proposed in 2005) and Rostovtsev and Stolbunov (eprint, 2006). But the biggest impetus came from the paper by David Jao and Luca De Feo in PQCrypto 2011. This paper presents the supersingular isogeny Diffie-Hellman (SIDH) key exchange scheme that has potential to be post-quantum secure.

The first thing to note is that the Jao and De Feo scheme is based on supersingular elliptic curves. Readers might think: Supersingular curves are weak for classical crypto, and ECDLP is broken by Shor’s algorithm, so how can this be a good idea? The point is that we are no longer basing security on discrete logarithms, or any “algebraic” property of a specific elliptic curve. Instead, the basic structure is group homomorphisms between curves.

There are several reasons to be interested in supersingular isogeny crypto.

  • The pool of potential post-quantum assumptions is very small, and so all avenues need to be fully explored and tested.
  • There has been a huge body of knowledge and experience developed over the last 20 years in support of elliptic curve crypto, and so it is natural to try to continue using elliptic curves if possible.
  • Some of the underlying computational problems have already been considered by researchers in classical elliptic curve crypto and computational number theory, and so there is some good evidence that the assumptions are reasonable, at least against classical computers.
  • It is straightforward to choose parameters to achieve a given security level. In contrast, selecting parameters for lattice crypto that achieve a given security level is still problematic. For example, different models of how the BKZ algorithm performs lead to quite different results (although it is possible to make conservative choices that still lead to a practical scheme).

However, there are also several serious concerns about supersingular isogeny crypto.

  • One of the most serious concerns is that the systems have not been sufficiently scrutinised by researchers in quantum algorithms. A contributing factor is that there are significant mathematical preliminaries needed to fully understand isogeny crypto, and so it is not an easy field for non-experts to work in.
  • Another concern, especially in contrast to lattices, is that isogenies are not a very “expressive” tool. Lattice crypto has provided a rich suite of cryptographic functionalities including encryption, signatures, id-based crypto, homomorphic encryption, and more. On the other hand, the only practical isogeny crypto primitive known is key exchange. We do not even have a practical digital signature scheme based on isogenies (see Yoo et al in FC2017 and this paper, which is to appear at Asiacrypt 2017), and signatures are a relatively basic primitive.

The main conceptual idea of isogeny key exchange is the following: In the original Diffie-Hellman protocol Alice sends to Bob g^a and Bob sends to Alice g^b. One can interpret this in terms of group homomorphisms: Alice has a private group homomorphism \phi : G \to G defined by \phi(x) = x^a and Bob has a private group homomorphism \psi : G \to G defined by \psi(x) = x^b. Alice publishes \phi(g) and Bob publishes \psi(g). Alice completes the protocol by computing \phi( \psi(g )) and Bob computes \psi( \phi( g )). The homomorphisms commute so Alice and Bob compute the same key.

An isogeny is a group homomorphism from an elliptic curve E. An isogeny has a finite kernel G. So one can think of an isogeny as a homomorphism E \to E/G. The crucial fact is that there is a way to represent the image E/G in a form that does not reveal the group G. In other words, it is not represented using cosets, but as another elliptic curve.

The key exchange protocol is then seen to be analogous to the Diffie-Hellman protocol. Fix an elliptic curve E. Alice has a private subgroup G_A and a private isogeny (group homomorphism) \phi : E \to E/G_A. Bob has a private subgroup G_B and a private isogeny \psi : E \to E/G_B. Alice publishes \phi(P) for some points P \in E that enable Bob to compute \phi(G_B). Bob computes \psi( Q ) for some other points Q \in E that enable Alice to compute \psi( G_A ). Then Alice computes (E/G_B)/\psi(G_A) and Bob computes (E/G_A)/\phi(G_B) and in both cases they get the same elliptic curve (up to isomorphism) E/(G_A,G_B). For details see the paper by Jao and De Feo, or any of the other subsequent papers in the field.

One reason to choose supersingular elliptic curves is that it makes key generation and some computational and theoretical aspects of the protocol much more simple and efficient than if using other elliptic curves.

The fundamental computational problem underlying isogeny crypto is the problem: Given two elliptic curves E, E' to find an isogeny \phi : E \to E'. This has been studied by researchers since David Kohel’s thesis in the mid-1990s and is a well-established problem in computational number theory. Only exponential-time classical algorithms are known for this problem. Moving to quantum algorithms: Childs, Jao and Soukharev gave in 2014 a subexponential-time quantum algorithm for the ordinary curve case. However, for supersingular curves the only quantum algorithm known is by Biasse, Jao and Sankar and it requires exponential time and subexponential space. This gives further motivation to only consider the case of supersingular curves.

However, it is important to note that the Jao-De-Feo key exchange scheme relies on a weaker variant of this problem. In the scheme one gets two elliptic curves E, E' plus two pairs of points (P, \phi(P)) where \phi : E \to E' is an isogeny of known degree. Using these points one can generate exponentially many points (R, \phi(R)) on the graph of \phi. Is it possible to compute \phi using some kind of interpolation algorithm? Perhaps a quantum algorithm? A recent paper by Christophe Petit explores a novel classical approach to solving this variant of the isogeny problem, but currently these methods do not break practical versions of the SIDH scheme.

In conclusion, isogeny crypto is a very interesting and active area of research in crypto. However, more investigation is needed by researchers in quantum algorithms before we can be confident that it really is post-quantum secure. If you wish to learn more about the subject then I recommend this paper for a tutorial on the basic theory, and for a discussion of computational problems of interest.

— Steven Galbraith

Posted in Uncategorized | 2 Comments