Review of ECC 2020

One of the reasons I started this blog was to share information with people who were unable to attend conferences. So I’ve tried to maintain a tradition of conference reviews. I’ll continue, even though online conferences are more inclusive and there is no excuse not to attend.

ECC 2020 took place online last week. Recordings of the 4 panel discussions are available on youtube here.

There were technical problems with the first panel (the “Pacific rim” group), but the audio is ok and the quality gets better after the first few minutes. The discussion in the first panel covered various attacks on signatures (including Minerva and TPM-Fail), groups of unknown order, the development of isogeny-based crypto, polynomial commitments, and computational records for factoring, finite field DLP and ECDLP. Finally we answered the question “why work on fancy crypto when we don’t even seem to be able to safely encrypt and sign data?”. Watch the recording to find out more!

The following three panels ran more smoothly and are also highly recommended. I found it particularly interesting to listen to the speculations on future developments in quantum computing in the panel “How long can we safely use pre-quantum ECC?”, but I also recommend “Formal verification of ECC” and “Is SIKE ready for prime time?”

There is also a curated list of talks which is a sort-of “greatest hits” of conference and seminar talks from the last year.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

ECC 2020 Conference

The ECC 2020 conference will take the form of a curated collection of lecture recordings, and four panel discussions. Each panel will feature a number of experts in the area, and there will be an opportunity for audience members watching live to ask questions during the session using zulip. Each panel is followed by a 30 min social break on wonder.me. The conference is free, please come along.

To register, email Tanja Lange.

The four panels are:

  • Wednesday 28th October, 01:00 UTC: Conference opening, and panel on recent trends in ECC
    Moderator: Steven Galbraith.
    Panel: Dan Boneh, Nadia Heninger, Kristin Lauter, Mehdi Tibouchi, and Yuval Yarom.
  • Wednesday 28th October, 08:00 UTC: Formal verification of ECC protocols
    Moderator: Benjamin Smith.
    Panel: Karthik Bhargavan, Bas Spitters, and Bow-Yaw Wang.
  • Thursday 29 October, 12:00 UTC: How long can we safely use pre-quantum ECC?
    Moderator: Francisco Rodríguez Henríquez.
    Panel: Sam Jaques, Manfred Lochter, and Michele Mosca.
  • Thursday 29 October, 19:00 UTC: Is SIKE ready for prime time?
    Moderator: Alfred Menezes.
    Panel: David Jao, Christophe Petit, and Nick Sullivan.

See you there!

— Steven Galbraith

Posted in Uncategorized | Leave a comment

PQCrypto 2020 and other news

PQCrypto 2020 took place online on September 21-23. All sessions were recorded and can be viewed here. The conference had a varied programme across all of post-quantum crypto, including a number of isogeny papers. In this blog post I will discuss the Three Invited Talks. (I was not able to participate in the conference in real-time, as the sessions took place in the middle of the night for me.)

  • Benjamin Smith “Isogenies: what now, and what next?”
    Ben’s talk was an overview of isogenies, SIDH and CSIDH. In his words, isogenies are “absolutely weird” but they are gradually becoming “less weird”. He spent time talking about how isogenies are computed, including mentioning his recent result with Bernstein, De Feo and Leroux on computing \ell-isogenies in \tilde{O}( \sqrt{\ell} ) time. He mentioned some open problems, such as the “insanely hard problem” to generate a random supersingular elliptic curve E without knowing a trapdoor that would allow to compute (for example) the endomorphism ring of E. He also stated his view, in regard the \sqrt{\ell} time result, that “square-root time is not the end of this story and we can probably do better than this”.
    Regarding what’s next: Ben says we need to better understand the foundations and to speed up isogenies, and to do this we need to bring new brains to these problems.
  • Frank Wilhelm-Mauch “Quantum computers – state of play and roadmap”
    The talk gave an excellent overview of the current state of quantum computing, including some of the different models for building a quantum computer and some of the recent computational records for problems in various domains in science.
    One of the main themes of the talk was that algorithmic progress is limited by the problem of fault-tolerance and lowering errors. If the error rate is too high (meaning > 0.3 percent) then computation seems to be more or less useless. The current challenge is to get an error rate around 10^{-4}. Once that is achieved the community can consider “aggressively scaling” the number of qubits.
    Frank’s speculation is that quantum computers will stay at the 50-100 qubit range for the near future, while researchers focus on lowering the error. He mentioned that IBM has a roadmap to 1000 qubit hardware in 3 years and hopes to reach 10^6 qubits a little later, but they have not set themselves any error rate targets.
    The conclusions of the talk: despite continual progress in hardware, “cryptanalysis still can only be addressed with fault-tolerant algorithms” and there is still a “long way to go” to achieve that.
  • Dustin Moody/NIST “NIST PQC Standardization Update: Round 2 and beyond”
    Dustin was representing the National Institute of Standards and Technology (NIST) in this talk, by giving an overview of how NIST selected the round 2 and round 3 candidates. In the talk, and during the questions afterwards, he addressed the extent to which the NSA has influenced the decision-making process. He stated that “NIST alone makes the decisions” based on their own research and input from the community, and that the NSA feedback did not change any of their decisions.
    Regarding the “alternate” schemes in the third round (eg SIKE), Dustin stressed that these could be standardised in future if they continue to hold up to scrutiny.
    In terms of the ultimate “winners”, he mentioned that there will be at most one lattice-based KEM and at most one lattice-based signature to be standardised. So it looks like the final selection will contain relatively few schemes (perhaps only 4).

Some other news updates:

  • The Raccoon Attack is side-channel attack on Diffie-Hellman in prime fields in old versions of TLS. The idea of the attack is to reduce the problem to the hidden number problem (HNP), which can be solved using a lattice attack. To quote from the announcement “The vulnerability is really hard to exploit and relies on very precise timing measurements and on a specific server configuration to be exploitable”. What is interesting for this blog is that the attack works for finite field Diffie-Hellman but seems to be hard to mount on elliptic curve Diffie-Hellman, since the analogous hidden number problem does not have such a good solution.
    Maybe it is time to revisit elliptic curve hidden number problems? I believe the current state-of-the-art to be the paper “On the Bit Security of Elliptic Curve Diffie-Hellman” by my previous PhD student Barak Shani (published at PKC 2017). Barak’s PhD thesis contains a detailed discussion of hidden number problems in different “access models”.
  • NIST is running a Virtual Workshop on Considerations in Migrating to Post-Quantum Cryptographic Algorithms, on October 7th. Registration is free. The workshop will be recorded and the content will be made available after the event.
  • The Accepted papers at Asiacrypt 2020 are online. The conference will take place online on Dec 7-11. There are lots of isogeny papers and it looks like it will be an interesting programme. Congratulations to Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit and Benjamin Wesolowski for their paper “SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies”, which is one of the three papers to be awarded the title of Best Paper. I will report from the conference at the time.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

CRYPTO 2020

CRYPTO ran as an online conference this year due to COVID. Most of the sessions were while I was sleeping, but I was able to catch up on some of the sessions I missed by looking at recordings. The conference programme with links to papers and YouTube recordings is here.

The highlight was the powerful and important invited talk Crypto for the People by Seny Kamara. It covered several themes. One theme was to ask the question “Who benefits from the crypto research that we are doing?” Seny argued that mostly our work benefits companies and governments, rather than citizens. This echoed some sentiments of Phil Rogaway’s talk “The Moral Character of Cryptographic Work” from ASIACRYPT 2015. It was fascinating to hear about the low-tech system used by the ANC in the 1980s for secure communication between operatives in South Africa and the leadership in exile in the UK. (Being old enough to remember saving Basic programs from my home computer onto cassette tape using an audio format, it all made sense to me.) The need for secure communication for freedom fighters served to illustrate his argument that at least some of us should work on systems that help the marginalised and disempowered, rather than companies and governments. Another theme of his talk was diversity, both of people and research topics. Seny gave some insight into his experiences as a black immigrant minority in the crypto research community.

The Best Papers were:

  • Joseph Jaeger and Nirvan Tyagi, “Handling Adaptive Compromise for Practical Encryption Schemes”. Best Paper by Early Career Researchers Award.
  • Susan Hohenberger, Venkata Koppula and Brent Waters, “Chosen Ciphertext Security from Injective Trapdoor Functions”.
  • Wouter Castryck, Jana Sotáková and Frederik Vercauteren, “Breaking the decisional Diffie-Hellman problem for class group actions using genus theory”.

    This is the paper of most interest to this blog. It is a wonderful paper, and I have already discussed it in this blog post. A well-deserved best paper award.

  • Christof Beierle, Gregor Leander and Yosuke Todo, “Improved Differential-Linear Attacks with Applications to ARX Ciphers”.

The Rump Session did not contain any talks directly related to ECC. Yvo Desmedt gave a talk “40 years Advances in Cryptology: How Will History Judge Us?” which was a plea to the community to publish more research on cryptanalysis (he also said that “side channels are not real cryptanalysis” and that everyone should read Kahn’s book). There was also a version of the game show “Jeopardy!” but I’d rather not talk about it.

Some papers related to discrete logarithms were:

  • Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann, “Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment”.

    The paper reports some recent large-scale factoring and finite field DLP experiments using the number field sieve. The results suggest that solving DLP in \mathbb{F}_p^* is only about 3 times slower than factoring for the same bit sizes (previous estimates would be suggested a bigger gap).

  • Gabrielle De Micheli, Pierrick Gaudry and Cecile Pierrot, “Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields”.

    The paper is about the complexity of index calculus algorithms for the DLP in “medium prime” finite field settings, as arise in pairing-based crypto.

  • Alex Lombardi and Vinod Vaikuntanathan, “Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs”.

    The paper is about zero-knowledge proofs, but it features a sort of index calculus algorithm. Worth a look if you are curious.

There were plenty of papers on lattices. A common theme was algorithms for algebraic structured lattices. Two papers I want to mention are:

  • Qian Guo, Thomas Johansson and Alexander Nilsson, “A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM”.

    The paper shows that the equality check in the Fujisaki-Okamoto transformation should be implemented in constant time for lattice schemes. If not, then a timing attack can be used to mount an active attack based on deducing when the errors start to overflow (and hence learning the error terms in LWE instances).

    Not mentioned in their paper, but discussed in the chat thread, is that a similar idea can be used to mount the GPST attack on SIDH if the FO transform is not constant time.

  • Koen de Boer, Léo Ducas, Alice Pellet-Mary and Benjamin Wesolowski, “Random Self-reducibility of Ideal-SVP via Arakelov Random Walks”.

    The paper shows how to transform an ideal lattice to a random ideal lattice (and hence transform ideal-SVP to the average case) by a combination of continuous (Arakelov class group) and discrete (sparsification) processes. I recommend the pre-conference video by Koen, as it has some really awesome animations. I also like the fact that the approach is analogous to the use of random walks on isogeny graphs to get uniform mixing, as done by Jao, Miller and Venkatesan in their reduction for the ECDLP.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

The second half of ANTS 2020

This is a follow-up to my previous post on the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV).

First I want to announce that the Selfridge Prize for the best submitted paper as judged by the program committee was awarded to Jonathan Love and Dan Boneh for their paper Supersingular Curves With Small Non-integer Endomorphisms. The prize is funded by the Number Theory Foundation.

The prize for the best poster was awarded to Eric Bach and Jonathan Sorenson for Generating Smooth Numbers with Known Factorization Uniformly at Random.

David Jao’s invited talk introduced and surveyed the current state of isogeny-based crypto. In his opinion, signatures are the exciting new frontier in this area.

The other two invited talks for the second half of the conference were Rachel Pries and Andrew Booker. Rachel talked about determining the Shimura datum of families of Abelian varieties coming from cyclic covers of the projective line. Andrew talked about his recent computations on sums of three cubes (in particular the 33 and 42 problems). I highly recommend watching Andrew’s talk for his descriptions of how the result about 33 was announced and his interactions with the press (and a suggestion for the conference T-shirt).

Among the contributed papers, there were several papers that will be of interest to cryptographers.

  • Daniel J. Bernstein, Luca De Feo, Antonin Leroux and Benjamin Smith. Faster computation of isogenies of large prime degree

    The paper gives an improved method to compute isogenies of high-degree, by using ideas about fast computation of products that go back to Pollard and Strassen.

  • Novak Kaluderovic, Thorsten Kleinjung and Dusan Kostic. Cryptanalysis of the generalised Legendre pseudorandom function

    The paper gives new algorithms to compute f(x) \in \mathbb{F}_p[x] when given an oracle O(x) that computes the Legendre symbol (\tfrac{f(x)}{p}). This problem goes back a several decades in crypto, but recently gained new interest due to applications in multi-party computation.

  • Thomas Espitau and Paul Kirchner. The nearest-colattice algorithm: time-approximation tradeoff for approx-CVP

    The paper gives a “block” algorithm for solving the approximate closest vector problem in a lattice, that generalises the Babai nearest plane method.

  • Carl Bootland, Wouter Castryck and Frederik Vercauteren. On the Security of the Multivariate Ring Learning With Errors Problem

    The paper gives methods to solve the search m-RLWE problem and attack cryptosystems based on this problem.

  • Jean-Sébastien Coron, Luca Notarnicola and Gabor Wiese. Simultaneous diagonalization of incomplete matrices and applications

    The paper is about some computations that improve algorithms to solve the approximate common divisor problem and break CLT13 cryptographic multilinear maps.

  • Daniel E. Martin. Short Vector Problems and Simultaneous Approximation

    The paper gives a reduction from the approximate shortest vector problem to the problem of simultaneous Diophantine approximation (the reverse direction to the famous reduction by Lagarias form simultaneous Diophantine approximation to SVP).

As always, the pdfs of the preconference versions of the papers are here, and pre-recorded talks can be found at the ANTS conference YouTube channel. Even easier: Everything is in one place at researchseminars.org.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

The first half of ANTS 2020

The Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), that was intended to take place at the University of Auckland in New Zealand, is currently taking place online in what Noam Elkies has named “New Zoomland”. Here is a report on the first half of the conference.

Note that the pdfs of papers are all here and that there are short videos of all talks on the ANTS 2020 conference YouTube channel.

Day one of the conference opened with two papers on isogenies.

  • Supersingular Curves With Small Non-integer Endomorphisms, by Jonathan Love and Dan Boneh.

    The motivation for this paper is the problem of “hashing” to a random supersingular curve over \mathbb{F}_{p^2}. A natural solution would be to construct a CM curve with small discriminant, as done in Broker’s algorithm. The paper calls such curves M-small (curves whose endomorphism ring contains an isogeny of degree at most M). Equivalently the endomorphism ring contains an order of discriminant at most M. For each fundamental discriminant D such that M \le D < 0 let T_D be the set of all M-small curves such that the order lies in \mathbb{Q}(\sqrt{D}). The paper proves a number of new results (both mathematical and algorithmic) relating to the structure of the subgraphs T_D within the full isogeny graph, when M < \sqrt{p}/2.

    The conclusion is that, given any M-small curves E, E' one can efficiently compute an isogeny from E to E', which means this is not a useful way to hash to elliptic curves.

    Note that Castryck, Panny and Vercauteren (EUROCRYPT 2020) present a complementary result for hashing into the CSIDH set.

  • Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs, by Kirsten Eisenträger, Sean Hallgren, Chris Leonardi, Travis Morrison and Jennifer Park.

    This paper is about the problem of computing End(E) when E is a supersingular elliptic curve. There are two approaches to this problem in the literature:

    1. To compute cycles in the isogeny graph (and hence endomorphisms), giving a subring of End(E). Then to work out which of the maximal orders containing that ring is the right one. This idea first appears in Kohel’s thesis, but all the details were not worked out.
    2. To compute an isogeny from a nice curve E_0 with known endomorphism ring to E, and then to deduce the endomorphism ring of E. The key step to such approaches is the paper by Kohel, Lauter, Petit and Tignol (from ANTS 2014). Several subsequent papers discuss details of computing End(E), in particular the paper Supersingular isogeny graphs and endomorphism rings: reductions and solutions by Eisenträger, Hallgren, Lauter, Morrison and Petit.

    This ANTS paper is the first to give all the details of an algorithm of the first approach (finding cycles) and to work out the complexity carefully. The main focus of the paper is a study of Bass orders. The paper pays close attention to the size of the representation of the endomorphism ring.

    At a high level it is not obvious to me which of these two approaches is the better strategy, or whether they both should have basically the same complexity.

Next up was a superb invited lecture by David Harvey on Recent results on fast multiplication. A recording of the lecture is on the YouTube channel mentioned above.

The first day concluded with two more talks on superspecial curves.

  • Counting Richelot isogenies between superspecial abelian surfaces, by Toshiyuki Katsura and Katsuyuki Takashima.

    The paper has a careful analysis of the isogenies of superspecial dimension 2 abelian varieties. The goal is to distinguish the case of isogenies to a product of two elliptic curves versus isogenies to the Jacobain of a genus 2 curve.

  • Algorithms to enumerate superspecial Howe curves of genus four, by Momonari Kudo, Shushi Harashita and Everett Howe.

    The paper is about a method to construct superspecial curves genus 4 curves out of elliptic curves and genus 2 curves.

Day two had a number of nice papers, but probably less interesting to a cryptographic audience (also a bit early in the morning for me). Isabel Vogt gave an invited lecture on Arithmetic and geometry of Brill–Noether loci of curves. There was a poster session comprising three of the posters. One of the posters has a crypto context: Samuel Dobson, Steven D. Galbraith, and Benjamin Smith, Trustless Construction of Groups of Unknown Order with Hyperelliptic Curves.

Day three started with three number theory talks (again, too early in the morning for me — who organised this??). The invited talk by Felipe Voloch on Commitment Schemes and Diophantine Equations discussed some ideas for a post-quantum commitment scheme based on diophantine equations that are hard to solve but for which determining the number of solutions is easy.

Day three also featured a wonderful session by Joppe Bos and Michael Naehrig to remember Peter Montgomery. Peter had attended a number of ANTS conferences over the years, and died earlier this year. His name is legendary in computational number theory due to his contributions to factoring and fast arithmetic, such as Montgomery multiplication, the Montgomery model for elliptic curves, and the Montgomery ladder for elliptic curve point multiplication.

Finally on day three was the rump session, which was heavily biased towards isogenies.

  • Everett Howe gave a hilarious talk on isogenies of superspecial curves in characteristic 2 (joint work with Bradley Brock).
  • Enric Florit (reporting on joint work with Ben Smith) presented some results on the Ramanujan property (or not) of genus 2 isogeny graphs.
  • Christophe Petit advertised the Isogeny-based cryptography winter summer school in Bristol in December.
  • Péter Kutas talked on joint work with on quantum attacks on unbalanced SIDH.
  • Antonin Leroux sketched SQIsign (pronounced “ski sign”) post-quantum signature from quaternions and isogenies. It seems a nice idea and I am very curious to see the details.
  • Wouter Castryck (joint work with Thomas Decru and Fre Vercauteren) presented Radical isogenies which is a major breakthrough new idea to speed up CSIDH.

It has been a great 3 days. I will report back again on the rest of the conference, and also the workshop on post-quantum crypto that follows the conference.

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Eurocrypt 2020

Eurocrypt 2020 took place online, being the first major IACR cryptography conference to be run online over zoom. The chairs did an amazing job at short notice, assisted very ably by Kevin McCurley and Kay McKelly from the IACR as Virtual Conference Administrators.

I understand there were over 1000 registrations, making it by far the largest Eurocrypt of all time. It turns out that online events are more accessible. Certainly I had not planned to fly to Europe for it, but since it was online I was able to attend.

Short videos of the talks are on youtube and are linked from the conference webpage, and the full live sessions are on the IACR YouTube channel. Unfortunately I did not attend any of the live sessions due to time-zones, but I did at least catch most of the rump session.

For the purposes of this blog, the most important session was the opening session on “Number-Theoretic Cryptography”. There was an unexpected hidden theme between two of the papers, which is the algorithm by Becker, Coron and Joux for solving subset-sum (building on the beautiful idea of Howgrave-Graham and Joux to split vectors by weight rather than length).

I now discuss the papers in this session.

  • “He Gives C-Sieves on the CSIDH” by Chris Peikert, and “Quantum Security Analysis of CSIDH” by Xavier Bonnetain and André Schrottenloher.

    These two papers are about quantum algorithms to solve the group action problem (the computational assumption underlying the CSIDH isogeny-based post-quantum key exchange protocol). Both papers use Kuperberg’s second algorithm for the hidden shift problem. The papers advance our understanding of the security of CSIDH.

    As outlined very clearly in Peikert’s talk, there are three components of such an algorithm:

    1. A quantum circuit to compute the class group action [a]*E for “arbitrary” ideal classes. This is used to create certain “labelled” quantum states (consisting of an integer, called the “label”, stored classically as bits, and a quantum state).
    2. A sieve algorithm to combine “naughty” labelled states to form “nice” labelled quantum states.
    3. A measurement process that allows to compute some bits of the secret ideal class from a nice labelled state.

    The main challenges are to get a small quantum circuit to do step 1 and to minimise the number of states needed for the sieving in step 2.

    Peikert’s paper is mainly about items 2 and 3. The paper uses “quantumly accessible classical RAM”, which means there is a storage device that stores classical bits, and one can efficiently create quantum states that are superpositions of stored values. The paper then studies the sieving process (the “collimation sieve”, which is the “C-sieve” in the title of the paper). One aim is to minimimise the total number of labelled states that need to be computed in step 1, and hence reduce the total number of quantum gates required.

    Peikert claims that if the storage is (respectively) 2^{32}, 2^{40}, 2^{48} bits, then one can attack CSIDH-512 using (respectively) 2^{18.7}, 2^{15.7}, 2^{14.1} executions of step 1. He claims that in the case of 2^{40} bits of storage this gives a quantum algorithm to break CSIDH-512 that requires 2^{60} T-gates. Officially this is below NIST level 1, though it is still unclear to me that a quantum computer with 2^{60} gates is a realistic object in the forseeable future (as far as I know, we do not currently have classical computers with 2^{60} gates).

    Peikert discusses several optimisations and also reports on his simulations (his code is available).

    Bonnetain and Schrottenloher study a different range of parameters for Kuperberg’s second algorithm. Regarding step 2 they focus on the case of small storage and aim to reduce the quantum cost of the algorithm by doing a large classical computation involving the labels. In other words, they reduce the quantum cost by increasing the classical cost. Their innovations in the sieve stage include using subset-sum algorithms (such as the one by Becker-Coron-Joux that I mentioned above) and list-merging algorithms (such as Schroeppel-Shamir). They also make progress on step 1, with new ideas to shrink the quantum circuit for computing the class group action.

    For CSIDH-512, Bonnetain and Schrottenloher claim an attack that requires only about 40,000 logical qubits and a total circuit size of approximately 2^{71.6} T-gates, while also performing a 2^{86} classical computation. Again, this is technically below the required security for NIST level 1.

    In the discussion it was noted that these papers do not “break” CSIDH, but both authors suggest the parameters should be increased. It was also mentioned that the attacks apply to CSURF. If I had been awake in the discussions I would have asked what is the security level if the Bonnetain-Schrottenloher quantum circuit is used with the Peikert sieve. Presumably this gives a further improvement of the attack.

  • “Double-Base Chains for Scalar Multiplications on Elliptic Curves” by Wei Yu, Saud Al Musa and Bao Li.

    There has been an ongoing literature on the task of computing low weight double-base chains, which are a tool to potentially speed up variable point scalar multiplication on elliptic curves. This paper, which is mostly theoretical, gives some improvements in this area.

  • “Rational Isogenies from Irrational Endomorphisms” by Wouter Castryck, Lorenz Panny and Frederik Vercauteren.

    This lovely paper gives a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves.

    For simplicity I discuss the case p \equiv 3 \mod{4}. Let E_0 : y^2 = x^3 + x be the supersingular curve with j-invariant 1728. The quadratic twist E_0^t of E_0 is isomorphic over \mathbb{F}_p to E_0.

    The paper exploits the fact that if E = [a] * E_0 for some ideal class [a] then E^t = [a^{-1}] E_0. Now suppose \tau \in End(E) is an isogeny of degree \ell such that \tau \circ \pi = - \pi \circ \tau, where \pi is the p-power Frobenius (this is a typical case). Let \phi : E \to E^t be the isomorphism over \mathbb{F}_{p^2} from E to its quadratic twist. Then \phi \circ \tau : E \to E^t is an \ell-isogeny that is \mathbb{F}_p-rational. It follows that \phi \circ \tau corresponds to an ideal class [b] such that E^t = [ab] E_0. Hence [ab] = [a^{-1}] and we can solve for [a] by computing \sqrt{[b]}.

    In short, if we are given E and want to compute [a] such that E = [a] * E_0, then it suffices to find a suitable element \tau \in End(E). The paper explains how to do this.

  • “Low Weight Discrete Logarithms and Subset Sum in 2^{0.65n} with Polynomial Memory” by Andre Esser and Alexander May.

    This paper gives the first progress on the low Hamming weight DLP for about 20 years and it is a major result. The paper is a total mind-bender, with random walks built from random walks forming rhos of rhos. A key idea is splitting by weight, which again takes us back to the Becker-Coron-Joux algorithm.

    I am sorry, but I cannot begin to summarise this paper in a few lines. Read it. Then read it again when you are stoned. Then read it again when you are sober.

The invited talks were both excellent.

  • “Mathematics and Cryptography: A Marriage of Convenience?” by Alice Silverberg.

    I watched the 44-minute pre-recorded lecture. There is also a Live talk with 30 mins presentation followed by Q&A.

    Alice told various stories of her journey through mathematics and crypto, and some of the people she has worked with. She briefly talked about her work with Rubin on compression in finite fields (algebraic tori), her work with Boneh on multilinear maps, and her work with H.W. Lenstra Jr. on the Gentry-Szydlo algorithm. Most importantly she used these stories to illustrate the importance of community, curiosity, communication, kindness, listening, and doing the right thing.

  • “Fine-Grained Cryptography: A New Frontier?” by Alon Rosen.

    The talk gave an overview of recent work on fine-grained complexity and crypto. The basic idea is this: Suppose we have a computational problem that an honest user can set up in roughly linear time O(n) but an attacker requires time O(n^k) to solve. This is polynomial time, but if k is large enough then such work may be infeasible, or at least extremely time-consuming, and that could be enough for crypto applications.

    Alon explained the k-Orthogonal Vectors (k-OV) problem, which is: Given k lists L_i, each containing n vectors in \mathbb{F}_p^d (for small p and d = O( \log(n))) to find k vectors u_i \in L_i such that \sum_{j=1}^d \prod_{i=1}^k u_{i,j} = 0. In the case k=2 this becomes the problem of finding two vectors whose Eucliden inner product is zero (i.e., the vectors are orthogonal).

    The obvious way to solve the k-OV problem is to consider all n^k combinations of vectors. The k-OV assumption is that there is no algorithm that can do much better than this.

    Impagliazzo, Paturi and Zane introduced the Strong Exponential Time Hypothesis (SETH) which is that you can’t solve k-SAT much better than expected. The SETH supports the k-OV assumption, in the sense that if there was a faster algorithm for k-OV then there would be faster algorithms for k-SAT than currently known.

    Alon then described how to get proof-of-work and one-way functions from k-OV, and said many nice things about the CRYPTO 2019 paper “Public-Key Cryptography in the Fine-Grained Setting” by Rio LaVigne, Andrea Lincoln and Virginia Vassilevska Williams. The final part of the talk was a blur of philosophical musings (and some jokes).

As always, a highlight was the rump session. There was drinking. There were cigars. There were unusual zoom backgrounds. Contacts were traced. There was a challenging quiz.

In terms of this blog, there were no rump session talks of particular relevance to ECC. Two highlights were the songs “I will survive” by Women in Theory, and “Zoom zoom zoom zoom” by Chloe Martindale. Please click here for the
Youtube link for the IACR Fellows Award Ceremony and Rump Session.

For those who wanted to visit Zagreb, don’t worry! The conference general chairs are being rewarded for their competence by being asked to run the conference again in 2021.

In the meantime, as FakeIACR quipped on twitter, I look forward to not seeing you soon at PKC and CRYPTO.

— Steven Galbraith

Posted in Uncategorized | 1 Comment

May 2020, What’s new?

Things have been quiet on this blog lately. As with everyone else on the planet, I have been distracted by COVID-19 and its impact on academic and family life. But I have decided it is time to write something.

Hopefully the next post will not be too far behind: EUROCRYPT is coming up next week, as an online conference. I plan to report on some of the activities that take place (although it is mostly taking place in the middle of the night with respect to my time-zone).

In the meantime, I thought I would mention some recent isogeny papers that I like.

  • Craig Costello and Ben Smith, The Supersingular Isogeny Problem in Genus 2 and Beyond, PQCrypto 2020.

    Supersingular abelian varieties of dimension d > 1 are isogenous to a product of supersingular elliptic curves. Superspecial abelian varieties are isomorphic to a product of supersingular elliptic curves, though generally only as unpolarized abelian varieties.

    If one considers the isogeny graph of superspecial abelian varieties of dimension d then some vertices (isomorphism classes of polarized abelian varieties) are simple and some are products of abelian varieties of lower dimension with a product polarization. The idea of the paper is to use a set of “easily-identifiable distinguished vertices” in the isogeny graph, namely those corresponding to E \times A where E is a supersingular elliptic curve and A is an abelian variety of dimension d-1.

    This leads to an iterative approach to find an isogeny between two superspecial abelian varieties A_1 and A_2 of the same dimension d: Take random walks from each until hitting distinguished vertices of the form E_i \times A_i' for i \in \{1,2\}. If one can compute isogenies E_1 \to E_2 and A_1' \to A_2' then one can “lift” them to an isogeny A_1 \to A_2. Since we are reducing the dimension, the search problems to find the isogenies are in smaller spaces, and hence easier to find.

    This is a really nice application of the structure of products with the space of polarized abelian varieties.

  • Ali El Kaafarani, Shuichi Katsumata and Federico Pintore, Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512, PKC 2020.

    The paper is about digital signatures from isogeny problems. The SeaSign paper by De Feo and me contained a signature scheme in the random oracle model and also, in an appendix, a scheme based on lossy keys that would have tight security in the quantum random oracle model (based on a result by Kiltz, Lyubashevsky and Schaffner). The drawback is working with a massive class group and hence larger parameters.

    This paper introduced a new way to get lossy keys, that is simpler and does not require such a large increase in parameters. I like the idea. Here is an analogy of the idea in the DLP setting.
    Let the system parameters be (g_1, g_2) in some group.
    Suppose a user has private key a and public key (h_1,h_2) = (g_1^a,g_2^a).
    Here is an interactive way to prove knowledge of a:

    1. Prover chooses random r and sends commitment (t_1, t_2) = (g_1^r,g_2^r) to verifier.
    2. Verifier responds with a challenge bit c \in \{0,1\}.
    3. Prover replies with s = r (if c=0) or s = ar^{-1} (if c=1).
    4. Verifier checks that (g_1^s, g_2^s) = (t_1,t_2) if c=0, or (t_1^s,t_2^s) = (h_1,h_2) if c=1.
    5. Repeat.

    One can see that this makes sense as a proof of knowledge, and can be turned into a signature scheme using the Fiat-Shamir transform.

    The lossy key setting is to choose a random pair (h_1,h_2) as a “lossy public key”, in which case one can see that there is not a single s that works for each r. The indistinguishability of real and lossy keys is the computational assumption.

    Unlike the lossy keys scheme in the SeaSign paper, this approach does not need such large parameters.

  • Daniel J. Bernstein, Luca De Feo, Antonin Leroux and Ben Smith, Faster computation of isogenies of large prime degree, to appear at ANTS.

    Computing degree d isogenies essentially boils down to evaluating some polynomials of degree O(d) at some points. For example we have polynomials such as

    f(x) = \prod_{i=1}^{(d-1)/2} (x - x( [i]P ))

    and wish to evaluate them on the x-coordinate of some points. The classical Vélu formulae compute this in O(d) steps.

    The starting point of the paper is the observation (going back to Pollard and Strassen) that there are fast methods to evaluate polynomials with a certain “structure” in their roots. The paper explains how to make this idea work for isogenies, using biquadratic polynpomials to encode the addition operation on a Montgomery model.

    In short, the paper shows how to compute isogenies in \tilde{O}( \sqrt{d} ) operations. In practice, this approach becomes useful for d \approx 200, which means it could be useful for CSIDH, CSURF or BSIDH. The approach is not interesting for SIDH/SIKE.

  • Samuel Jaques and André Schrottenloher, Low-gate Quantum Golden Collision Finding, eprint 2020/424.

    This paper is about quantum algorithms for the claw-finding problem, which is a basic “meet-in-the-middle” approach to solving the computational problem behind SIDH/SIKE. More precisely, in a claw-finding problem we have functions f : X \to Z, g : Y \to Z and seek x \in X, y \in Y such that f(x) = g(y). In SIDH, X = Y corresponds to degree 2^{n/2} isogenies, and f is taking an isogeny from E while g is taking an isogeny from E_A.

    Two types of algorithm have previously been considered:

    1. Tani’s algorithm. This was already mentioned in the original paper on SIDH by Jao and De Feo. A recent paper by Jaques and Schanck argued that managing the quantum random access storage in Tani’s algorithm would likely mean it performs less well that originally expected.

    2. The van Oorschot and Wiener algorithm. This is a classical algorithm, whose relevance to SIDH was first noted by Adj, Cervantes-Vázquez, Chi-Domínguez, Menezes and Rodríguez-Henríquez. The main idea is to transform the problem of claw-finding into a collision-finding problem on the set X. The problem is that useless collisions arise, and so one needs to compute many collisions until finding a collision (the so-called “golden collision”) that solves the claw-finding problem.

    The new paper considers variants of these quantum random walk algorithms. I’m still digesting the details. However, the conclusion is that SIDH/SIKE is still holding up well against quantum attack. The paper states “SIKE parameters still meet the NIST security levels claimed in their NIST submission.”

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Breaking the decisional Diffie-Hellman problem for class group actions using genus theory

This post is about the paper Breaking the decisional Diffie-Hellman problem for class group actions using genus theory by Wouter Castryck, Jana Sotáková and Frederik Vercauteren.

First let us recall the situation in the setting of \mathbb{Z}_p^* where p is prime. A Diffie-Hellman quadruple is (g, g^a, g^b, g^{ab} ) for g \in \mathbb{Z}_p^*. The Decision Diffie-Hellman problem (DDH) is to distinguish such a triple (for uniformly sampled g \in \mathbb{Z}_p^* and a,b \in \mathbb{Z}_{p-1}) from a quadruple (g, g^a, g^b, g^c) for uniformly sampled g \in \mathbb{Z}_p^* and a,b,c \in \mathbb{Z}_{p-1}.

The Legendre symbol is multiplicative, which implies that (\tfrac{g^a}{p} ) = ( \tfrac{g}{p} )^a. If (\tfrac{g}{p})= -1 (which may happen when g has even order) then one can learn the parity of a and b from g^a, g^b respectively, and hence test if the fourth value of the quadruple has Legendre symbol consistent with g^{ab}. This well-known fact allows to reject half of all uniformly sampled quadruples (g, g^a, g^b, g^c) when (\tfrac{g}{p})= -1, which is sufficient to say that DDH is not a hard problem in \mathbb{Z}_p^*.

One can increase the success rate beyond 1/2 by using a random-self-reduction of Diffie-Hellman quadruples, but one can never get a perfect DDH oracle (i.e., an oracle that only accepts (g, g^a, g^b, g^{ab} )) from this technique, as the Legendre symbol only “sees” the order 2 elements.

The Legendre symbol is just a group homomorphism \mathbb{Z}_p^* \to \{ 1, -1\}, and for any prime \ell \mid (p-1) one can get a homomorphism \mathbb{Z}_p^* \to H where H is a subgroup of order \ell. Hence, if (p-1) has a range of small factors then one can get an increasingly accurate algorithm to distinguish Diffie-Hellman quadruples from random quadruples (and hence solve DDH).

[As an aside: The amazing thing about the Legendre symbol, and the reason it is taught in all good number theory courses, is not the existence of a group homomorphism \mathbb{Z}_p^* \to \{ 1, -1\}. This is trivial. What is non-trivial is the quadratic reciprocity law, which gives a non-obvious and very efficient way to compute Legendre symbols.]

Similarly, for any finite group one can consider group homomorphisms to subgroups of small order. So one can also attack elliptic curve DDH in a similar way. This is one of the main reasons why the community works with groups of prime order, and in particular elliptic curves of prime order.

Now we turn to group actions. Let G be a finite group acting on a set X. Write the action of g \in G on x \in X as g*x. For example, let G = Cl( \mathcal{O} ) be an ideal class group acting on the set X of supersingular elliptic curves with j-invariant in \mathbb{F}_p. This is the setting of the CSIDH system in isogeny-based post-quantum crypto. The natural analogue of DLP is: Given E and a * E to compute a. The natural analogue of DDH is to distinguish (E, a*E, b*E, (ab)*E ) from (E, a*E, b*E, c*E ), where a, b, c are uniformly sampled from G.

Knowing about Legendre symbols, it is natural to speculate that one might be able to do something similar for group actions. We’d like a group homomorphism \phi : G \to H for some group H of small prime order, and to be able to compute \phi(a) from a*E. That is what the paper of Castryck, Sotáková and Vercauteren does.

In some survey talks (such as at ANTS 2018 and at the Alice Silverberg birthday conference in 2018) I asked “Can subgroups of ideal class group be exploited?” While I thought this would be a good problem, I did not have any clue how to do this. I am surprised and delighted by the new results.

Without going into the details, what the paper shows is that one can get enough information about the degree of an isogeny from E to a*E (and hence the norm of the ideal a) from looking at pairings of points on the elliptic curve. It is a wonderful and surprising (at least, to me) result, and brings a new set of ideas and techniques into isogeny crypto. The paper is not too hard to follow (don’t be put off by the phrase “genus theory” — it is not as scary as it sounds).

I end with a few small comments. First, as with the case of \mathbb{Z}_p^*, this does not give a perfect algorithm to distinguish DDH quadruples from uniform ones. But it does allow to reject some quadruples as being definitely not DDH, and this is enough to break the DDH assumption. Second, breaking the DDH assumption does not, as far as I know, break any isogeny cryptosystem. This is because isogeny cryptosystems are rather unsophisticated compared with DLP-based protocols. Third, the results do not apply to SIDH and have no impact on the SIKE submission to the NIST standardization process.

To conclude, this paper is a great theoretical result that brings new ideas to the field. What will be next for isogeny crypto? Whatever it is, I look forward to it!

— Steven Galbraith

Posted in Uncategorized | Leave a comment

Algorithmic Number Theory (ANTS-XIV)

The Fourteenth Algorithmic Number Theory Symposium, ANTS-XIV, will take place at the University of Auckland, New Zealand on June 30 – July 4, 2020.

The deadline for submissions is February 25. To submit, please go to the call for papers on the conference website.

I decided to have a look at the history of the ANTS conferences, and in particular to identify the most highly cited papers (using google scholar). The ANTS conferences started in 1994, with the first conference held at Cornell.

First I want to mention that citation counts are not a good measure of research quality or difficulty or importance. Citations are biased towards subject areas that have a culture of writing lots of papers and citing widely. Citation counts are also biased to older papers, since they have had more time to accrue citations. Hence, we would expect the most highly cited papers at ANTS to be in cryptography, and from 16 or more years ago.

Nevertheless, citation counts do tell something about the interest in a paper, and are a reasonable proxy for impact on the field.

The most highly cited paper in the history of the ANTS conferences (with nearly 1700 citations according to google scholar) is:

  • J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, ANTS III, 1998.

There is no doubt that this is a massively influential paper on lattice cryptography. Several of the lattice-based submissions to the NIST Post-Quantum standardisaton process were very closely building on NTRU. The irony (if you can call it that) is that this paper was rejected from CRYPTO, and yet has had higher impact than most other papers published in CRYPTO around that time.

Here are the following 14 most cited ANTS papers:

  • A. Joux, A One Round Protocol for Tripartite Diffie-Hellman, ANTS IV, 2000. 1369 cites.
  • D. Boneh, The Decision Diffie-Hellman Problem, ANTS III, 1998. 1078 cites.
  • S. D. Galbraith, K. Harrison and D. Soldera, Implementing the Tate Pairing, ANTS V, 2002. 689 cites.
  • A. Joux, The Weil and Tate Pairings as Building Blocks for Public KeyC ryptosystems, ANTS V, 2002. 287 cites.
  • L. M. Adleman, J. DeMarrais and M.-D. A. Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields, ANTS I, 1994. 258 cites.
  • P. Gaudry and R. Harley, Counting Points on Hyperelliptic Curves over Finite Fields, ANTS VI, 2000. 199 cites.
  • P. Q. Nguyen and D. Stehlé, LLL on the Average, ANTS VII, 2006. 168 cites.
  • O. Schirokauer, D. Weber and T. F. Denny, Discrete Logarithms: The Effectiveness of the Index Calculus Method, ANTS II, 1996. 167 cites.
  • L. M. Adleman, The function field sieve, ANTS I, 1994. 165 cites.
  • G.-J. Lay and H. G. Zimmer, Constructing elliptic curves with given group order over large finite fields, ANTS I, 1994. 163 cites.
  • P. Q. Nguyen and J. Stern, Lattice Reduction in Cryptology: An Update, ANTS IV, 2000. 144 cites.
  • N. D. Elkies, Shimura Curve Computations, ANTS III, 1998. 106 cites.
  • M. Fouquet and F. Morain, Isogeny Volcanoes and the SEA Algorithm, ANTS V, 2002. 104 cites.
  • A. Shallue and C. E. van de Woestijne, Construction of Rational Points on Elliptic Curves over Finite Fields, ANTS VII, 2006. 100 cites.

Of course, these rankings will change over time. But that is what it looked like in early 2020.

Looking at this list I see many important and favourite papers: Antoine Joux’s paper on One Round Tripartite Diffie-Hellman kick-started pairing-based crypto; the Adleman-DeMarrais-Huang paper was the first to show high genus curves are weak for DLP crypto; the Lay-Zimmer paper was influential in the early days of ECC; Fouquet and Morain introduced the phrase “Isogeny Volcano”; etc. It is also notable that several of the papers listed (e.g., those by Boneh, Elkies, Nguyen-Stern, and the second paper by Joux) are invited papers, which shows that the community does value survey/overview papers.

Anyway, I look forward to strong submissions to ANTS XIV in Auckland, including on elliptic curves, lattices and isogenies. Hopefully in 15-20 years the impact of some of those papers will be apparent.

— Steven Galbraith

Posted in Uncategorized | Leave a comment