SIAM Conference on Applied Algebraic Geometry 2019

So here we are in the nice city of Bern, in the Teutonic Switzerland, for the SIAM Conference on Applied Algebraic Geometry 2019that this year counts more than 750 attendees. The weather is warm enough but the isogenies topic has never been so hot! So for this occurrence of the conference Tanja Lange, Chloe Martindale and Lorenz Panny managed to organise a really great isogenies mini-symposium spread over 4 days.

Day #1

Day #1 started strong. After a quick overview of isogenies by Chloe Martindale and Lorenz Panny, including an introduction to SIDH and CSIDH, the invited speakers took the stage:

This concluded Day #1

Day #2

In Day #2 we had

  • David Jao discussing recent progress in implementing isogeny-based cryptosystems in constant time to resist side-channel attacks. In particular he presented results from his recent paper (joint work with Jalali, Azarderakhsh and Kermani). One of the interesting observation made was that isogeny computation over Edward curves is relatively simple to be implemented in constant time (as expected) but it is faster only for isogenies of degree 5 or more. He concluded his talk with some really great demos (as also reported by Thomas Decru in a second blog post).
  • Christophe Petit surveyed known results on the security of isogeny-based protocols including the celebrated active attack on SIDH.
  • Frederik Vercauteren gave the first of two sessions dedicated to CSI-FiSh (joint work with Beullens and Kleinjung). This part had as a focus the new record class group computation they achieved while computing the class group structure of CSIDH. It seems they reused some of the code previously written by Kleinjung, and for the final computation of the closest vector in the lattice Léo Ducas gave a hand. While the technique used for the computation was standard, it was still a remarkably big task involving several core years. He concluded the talk with a nice list of open problems.
  • David Kohel presented a joint work done with his student Leonardo Colò that was recently published at NutMiC 2019. This construction called OSIDH (that stands for oriented supersingular isogeny Diffie-Hellman) is built on top of O-oriented supersingular elliptic curves (as define in the paper).

Day #3

Day #3 of isogenies opened with the plenary session delivered by Kristin Lauter. Her talk, as usual, was really inspiring and was about the history of Supersingular Isogeny Graphs in Cryptography. She basically covered the Charles-Goren-Lauter (CGL) hashing construction and the panorama of post quantum cryptography. After a quick break and a commuting to the other building we were back to the isogenies mini-symposium:

  • Thomas Decru presented a new CGL type genus-two hash function (joint work with Wouter Castryck and Benjamin Smith). The reformulated a previous construction by Takashima (broken by Yan Bo Ti and Victor Flynn) by using genus-two superspecial subgraphs.
  • Jean-François Biasse talk was about algorithms for finding isogenies between supersingular elliptic curves. He showed that under some circumstances the generic Grover algorithm might beat the more isogeny specific Tani algorithm. This talk was also covered by a Thomas Decru’s blog post.
  • Benjamin Wesolowski talked about his systematic approach to analyse horizontal isogeny graphs for abelian varieties. He covered some neat theorems he proved (in a joint paper with Brooks and Jetchev) and concluded saying that his results would not be enough to say anything about the CSIDH case but as we will see in the next talk they are extremely useful in the higher genus cases.
  • Dimitar Jetche‘s talk was a natural following of the previous talk. He was focusing on vertical isogenies instead and announced a possible solution to the DLP on genus 3 hyperelliptic curves.

Day #4

And here we arrived already to the last day:

  • Ward Beullens delivered the second part of the CSI-FiSh paper (here there is also a blog post about it). In this part he focused on the identification scheme/signature part including the Zero Knowledge and the optimization part.
  • Florian Hess tried to give an answer to an open problem posed in a recent paper about multiparty non-interactive key exchange. Namely his talk was about the possibility of building an invariant maps from isogenies. His conclusions were not really positive at least so far.
  • Luca De Feo brought a new topic to the isogeny World: #blockchain! He presented a new Verifiable Delay Function construction based on Supersingular Isogenies and Pairings (joint work with Simon Masson, Christophe Petit and Antonio Sanso). Despite using isogenies, the construction is not quantum resistant due the usage of pairings. A blog post about this construction can be found here.

  • Jeff Burdges talked about some real word application of isogenies, including an hybrid scheme that might be used in mix networks, consensus algorithms in blockchain and encrypt to the future to be employed in auctions.

That’s all from SIAM AG. See you in 2 years.

— Antonio Sanso

Advertisements
Posted in Uncategorized | Leave a comment

ECC 2019, Bochum, December 2-4

It has just been announced that ECC 2019 will be held in Bochum, Germany, on December 2-4, 2019. More details will eventually be available at https://eccworkshop.org/.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

PQCrypto 2019

PQCrypto 2019 was held at Ronghui Spa Hotel in Chongqing, China on May 8-10, 2019. Prior to the conference, two other PQC events (the PQC 2019 summer school on May 6th and the 4th Asia PQC Forum on May 7th) were held at the same place.

The session on isogeny-based cryptography was held in the afternoon of May 9. It included three talks by young researchers:

  • Thomas Decru “Faster SeaSign signatures through improved rejection sampling” (joint work with Lorenz Panny and Frederik Vercauteren)

    This talk presented a faster variant of the SeaSign signature scheme by improving rejection sampling, which is a key technical ingredient of SeaSign. To obtain a practical isogeny-based (post-quantum) signature scheme is an important research direction in this field. This work advances a nice step towards the goal, however, it does not yet succeed.

  • Yan Bo Ti “Genus Two Isogeny Cryptography” (joint work with Victor Flynn)

    First, this talk presented a systematic method for finding collisions of the Charles-Goren-Lauter type genus-two hash function (which was suggested in a previous paper of mine). The collision finding was accomplished based on a closer look of the structure of isogeny graphs in genus two. A little surprisingly, it is now fixed by a very recent paper by Castryck, Decru, and Smith (eprint arxiv 2019/296), which reformulates it by using genus-two “superspecial” subgraphs. The talk also proposed a SIDH-type key exchange in genus two, in which (2,2)- and (3,3)-isogenies are used instead of 2- and 3-isogenies in the genus one case, respectively.

  • Michael Meyer “On Lions and Elligators: An efficient constant-time implementation of CSIDH” (joint work with Fabio Campos and Steffen Reith)

    This presentation proposed an efficient constant-time implementation of CSIDH. In the authors’ previous paper (INDOCRYPT 2018), they initiated an improvement of CSIDH implementation, which resulted in a faster algorithm than the original. However, this previous one leaks various information about the private key. Therefore, for obtaining side-channel leakage resistance, this talk modified how to sample key elements and used dummy isogenies, and then obtained a constant-time implementation (with several efficiency improvements furthermore).

Moreover, there were two invited talks which are relevant to this blog. One was by Tsuyoshi Takagi (Univ. of Tokyo), and the title was “Computational Challenge Problems in Post-Quantum Cryptography”, in which he first briefly reviewed the NIST PQC standardization, and then introduced PQC challenge problems with focus on the Fukuoka MQ Challenge and the Darmstadt Lattice Challenge. The other was given by Dustin Moody (NIST) on “Round 2 of NIST PQC Competition”. He carefully summarized the history of the competition and, for all the round 2 submissions, he made brief comments on advantages and/or unique features of the schemes. He also very briefly mentioned the future schedule of the competition.

— Katsuyuki Takashima

Posted in Uncategorized | Leave a comment

Recent work on pairing inversion

A few days ago (April 10, 2019) Takakazu Satoh posted on eprint the paper Miller Inversion is Easy for the Reduced Tate Pairing on Trace Zero Supersingular Curves on eprint. I was delighted to hear from Takakazu Satoh, as I know him well but I had not heard from him for several years. Satoh’s papers have a distinctive look, since he uses his own typesetting package that he wrote in the 1980s before TeX was widely available.

Takakazu Satoh has been interested in pairing inversion for quite a while, and has published several papers on the topic, including “On Degrees of Polynomial Interpolations Related to Elliptic Curve Cryptography” (WCC 2005), “On Pairing Inversion Problems” (Pairing 2007), and “Closed formulae for the Weil pairing inversion” (Finite Fields and Their Applications 2008).

To recall basic definitions: Let E be an ellptic curve over a field \mathbb{F}_q. Let \ell be a large prime such that \ell \mid \#E( \mathbb{F}_q ). The embedding degree is the smallest integer k such that \ell \mid (q^k  - 1). A pairing-friendly elliptic curve is one whose embedding degree is small, e.g., 2 \le k \le 30.

The (reduced) Tate-Lichtenbaum pairing takes two points P, Q \in E[ \ell ] and gives a value e_\ell( P, Q ) \in \mathbb{F}_{q^k}. A lot of researchers, including me and many of my friends, worked between 2000 and 2010 trying to compute pairings faster. The computation of the reduced Tate-Lichtenbaum pairing has two stages. First one computes a Miller function f_{\ell, P}(Q). The function f_{\ell, P} has divisor
\ell(P) - (\ell P ) - (\ell -1)(\infty).
Then one computes the final exponentiation, which is an exponentiation to the power (q^k - 1)/\ell.

It was discovered that, for many pairing-friendly curves, there was a more efficient way to compute the Miller function. Essentially instead of computing f_{\ell, P} one can compute values like f_{q, P}(Q), which is a simpler computation when \ell > q, which is usually the case. This observation was first made in a special case in a paper of Duursma and Lee from ASIACRYPT 2003. Further special cases were noted by Kwon (ACISP 2005) and Barreto, Galbraith, O hEigeartaigh and Scott (Designs, Codes and Cryptography, 2007). The situation was finally clarified by Granger, Hess, Oyono, Thériault and Vercauteren (“Ate Pairing on Hyperelliptic Curves”, EUROCRYPT 2007). The key idea is to work with Frobenius eigenspaces and change the pairing to f_{q,Q}(P). I call this paper GHOTV below. Subsequently, Hess (“Pairing Lattices”, Pairing 2008) and Vercauteren (“Optimal pairings”, IEEE Trans. Information Theory 2010) showed how to use this idea most effectively in general pairing implementations.

One particular feature of the ate pairing introduced in GHOTV, is that the pairing computation only needs the first stage (Miller’s algorithm) and does not require a final exponentiation. This makes it a lot faster to compute. The ate pairing is not the exact same function as the reduced Tate-Lichtenbaum pairing, so one cannot use them interchangeably. But they are both bilinear maps and so a system can be implemented using the ate pairing and it all works fine.

In those days, we thought pairings would be useful for identity-based crypto and short signatures, and we were mostly trying to work with large embedding degrees like k = 12. So the case k = 2 was considered of relatively minor interest and was not studied much.

The computational assumptions underlying pairing-based crypto all required pairing inversion to be hard. Typically pairing inversion means: Given z \in \mathbb{F}_{q^k} and a point P \in E[\ell] to find Q \in E[ \ell ] such that e_\ell(P, Q) = z.

It was quickly realised that there are two obstacles to pairing inversion: First it is necessary to invert the final exponentiation. Second one needs to invert the Miller function. It turned out that sometimes one or the other of these problems could be easy, but I know no situation for prime order groups where both are easy at the same time. For example, since the ate pairing does not require a final exponentiation, pairing inversion for the ate pairing is equivalent to Miller inversion (which seems to be hard in this case). In short, pairing inversion remains a hard computational problem, which is good news for pairing-based crypto. A good reference for these ideas is Galbraith, Hess, Vercauteren (“Aspects of Pairing Inversion”, IEEE Trans. Information Theory 2008).

Satoh’s recent paper explores the case k = 2. Work on discrete logs in finite fields (e.g., see these blog posts has caused some pairing researchers to become very conservative and reconsider choices such as k = 2. When k = 2 we essentially have \ell = q+1 and the final exponentiation is to the power (q^2-1)/(q+1) = q-1. The reduced Tate-Lichtenbaum pairing is
f_{q+1, Q}(P)^{q-1}.
Satoh uses Lemma 2 of GHOTV, that f_{q, Q}(P) \in \mathbb{F}_{q^2} already has order q+1. This is the fact that the ate pairing does not require a final exponentiation. Let v = f_{q+1, Q}(P) be the value computed by Miller’s algorithm, so that v^{q-1} is the pairing value. Suppose one has the value v (this is not normally the case, normally the attacker has v^{q-1}, from which there are q-1 possible values for v). Since f_{q+1, Q}(P) = (x(P) - x(Q)) f_{q,Q}(P) (I am using different notation to Satoh here) it means that an attacker can get their hands on P by raising v to the power q+1, remembering that exponentiation to the power q is linear, and hence solving a square-root to get x(P). Hence, Satoh has shown that Miller inversion is easy in this case, but pairing inversion is still hard.

In fact, when k = 2 it would be quite natural to instead use the ate pairing for any crypto application. Now there is no final exponentiation. However Satoh’s attack does not work since his approach is precisely to kill off the “ate pairing” contribution to the Tate-Lichtenbaum pairing.

In short, there are two pairings one can use in embedding degree 2 and both seem to be hard to invert: the ate pairing has trivial final exponentiation but the Miller function seems hard to invert; the Tate-Lichtenbaum pairing has easy Miller inversion (as Satoh has just shown) but it seems hard to invert the final exponentiation.

I end with a comment about applications of pairings. As I mentioned, 15 years ago we thought that the “killer applications” for pairings were identity-based crypto and short signatures. Nowadays it seems pairings are most useful for short zero knowledge proofs. For example, Jens Groth’s pairing-based zk-SNARK (zero-knowledge succinct non-interactive argument of knowledge) is a key component of Zcash. As far as I can tell, the implementation in Zcash uses curves with embedding degree k=12 and does use the ate pairing.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

AMS Sectional Meeting Special Session on The Mathematics of Cryptography

The American Mathematical Society Spring Central and Western Joint Sectional
Meeting was held at the University of Hawaii at Manoa, in Honolulu during March 22-24, 2019.

There was a Special Session on The Mathematics of Cryptography organised by Shahed Sharif and Alice Silverberg. Slides of (some of) the talks are available here.

Among the talks I attended, I mention these:

  • Isogeny cryptography: strengths, weaknesses and challenges, by Steven Galbraith.

    I talked about CSIDH and SeaSign, and then said a little bit about some work of my PhD student Yan Bo Ti on hash functions from dimension 2 supersingular abelian varieties. The slides online also cover some other topics that I did not mention (Kuperberg’s algorithm and quaternion algebras).

  • Identity-Based Encryption from the Diffie-Hellman Assumption by Sanjam Garg.

    This was a really nice talk that described a “hash encryption” scheme based on the (decisional) Diffie-Hellman problem and explained how this enables identity-based encryption from the Diffie-Hellman problem (no pairings needed). This is joint work with Nico Döttling. The schemes are not practical.

  • Ramanujan Graphs In Cryptography by Kristin Lauter.

    Kristin reported joint work with Anamaria Costache, Brooke Feigon, Maike Massierer and Anna Puskas about some computational problems in isogeny graphs. A paper on this work is eprint 2018/593.

  • Numerical Method for Comparison on Homomorphically Encrypted Numbers by Jung Hee Cheon.

    Jung Hee talked about some basic mathematical functions (such as max and min) that are useful for practical computations on encrypted data. He explained some iterated processes (in his words “nowadays I am working in numerical analysis”) that give low-depth circuits to compute approximations to these functions.

  • Multiparty Non-Interactive Key Exchange From Isogenies on Elliptic Curves by Shahed Sharif.

    Shahed talked (on the blackboard — there are no slides) about his paper eprint 2018/665 with Dan Boneh, Darren Glass, Daniel Krashen, Kristin Lauter, Alice Silverberg, Mehdi Tibouchi and Mark Zhandry. The scheme is still incomplete as no suitable efficiently computable isomorphism invariant of abelian varieties has been found. Shahed discussed attempts to find such invariant, and I learned some interesting facts about polarizations on abelian surfaces.

  • The Hidden Quadratic Form Problem by Joseph Silverman.

    Joe presented joint work with Jeff Hoffstein and others on a new candidate number-theoretical problem that might be interesting for new signature schemes. This is a work-in-progress and is not published yet.

  • Isolated Curves and Cryptography by Travis Scholl.

    Travis presented his papers eprint 2017/383, eprint 2018/307 and some newer work on “isolated curves”.

  • Fun with the hidden number problem by Nadia Heninger.

    Nadia surveyed her joint work with Breitner, published as “Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies”. Her talk also included an overview of lattice algorithms for the hidden number problem, and a very clear sketch of Bleichenbacher’s approach using Fourier analysis to the hidden number problem.

  • Short digital signatures via isomorphisms between modular lattices based on finite field isomorphisms by Jeffrey Hoffstein.

    Jeff presented very new joint work with Joe Silverman on yet another number-theoretical problem that might be interesting for new signature schemes. This is related to their previous work on isomorphisms of finite fields, but with new ideas and applications. I was not able to follow the details of the talk. There is no preprint yet on this work.

  • Computing isogenies and endomorphism rings of supersingular elliptic curves by Travis Morrison.

    Travis gave an overview of his EUROCRYPT 2018 paper with Eisentraeger, Hallgren, Lauter and Petit.

  • Lower bounds for Hilbert class polynomials by Reinier Broker.

    Much work on algorithms to compute Hilbert class polynomials requires proving good upper bounds on the size (e.g., bitlength) of these polynomials. Reinier spoke about his current work-in-progress trying to prove lower bounds on the size of these polynomials.

There was also a Special Session on Emerging Connections with Number Theory organised by Kate Stange and Renate Scheidler, plus a lot of other sessions, that included talks of some interest to readers of this blog. However, I stayed in the Mathematics of Cryptography room.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Accepted papers to Eurocrypt, PQ Crypto and PKC 2019

The Eurocrypt 2019 program features a lot of interesting papers. There are two papers relevant to isogeny crypto:

  • Daniel J. Bernstein, Tanja Lange, Chloe Martindale and Lorenz Panny. Quantum Circuits for the CSIDH: Optimizing Quantum Evaluation of Isogenies.
  • Luca De Feo and Steven Galbraith. SeaSign: Compact Isogeny Signatures from Class Group Actions.

The PQ Crypto 2019 program features three papers on isogeny crypto:

  • Thomas Decru, Lorenz Panny and Frederik Vercauteren. Faster SeaSign signatures through improved rejection sampling.
  • E.V. Flynn and Yan Bo Ti. Genus Two Isogeny Cryptography.
  • Michael Meyer, Fabio Campos and Steffen Reith. On Lions and Elligators: An efficient constant-time implementation of CSIDH.

The PKC 2019 program includes the paper:

  • Steven D. Galbraith, Jake Massimo and Kenneth G. Paterson. Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation.

    This paper shows how to construct elliptic curves whose group order is a composite that passes some primality tests with moderate probability. The paper explains why this has implications in some Diffie-Hellman settings.

(Apologies for the self-promotion.)

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Blog post on CSIDH and video of talk

Wouter Castryck has written a blog post to explain CSIDH: Post-quantum key exchange using isogeny-based group actions.

You can watch the Habilitation thesis talk by Luca de Feo on Exploring isogeny graphs.

— Steven Galbraith

Posted in Uncategorized | Leave a comment