Last month I was lucky enough to attend Eurocrypt 2023, which took place in Lyon, France. It was my first chance to attend an academic cryptography conference and the experience sat somewhere in between the familiar cryptography of the Real World Crypto conference and the abstract world of black holes and supergravity conferences which I attended in my previous life as a theoretical physicist.
The Death of SIDH
My trip was motivated by the publication of the research paper A Direct Key Recovery Attack on SIDH, which I had worked on last summer with my coauthors Luciano Maino, Chloe Martindale, Lorenz Panny and Benjamin Wesolowski. The paper sits within the context of the attacks on the supersingular isogeny Diffie-Hellman (SIDH) protocol and thus the key-exchange mechanism SIKE, which is built on top of SIDH.
As a brief timeline, in July 2022 Wouter Castryck and Thomas Decru published a paper: An efficient key recovery attack on SIDH which gave a heuristic polynomial time algorithm to break all instances of SIKE within 24 hours using a theorem by Kani from 1997. Their attack used a higher dimensional isogeny between abelian surfaces as a passive oracle to determine Bob’s secret isogeny step-by-step in the isogeny graph. The efficiency of their attack exploited that SIKE had picked an elliptic curve with known endomorphism ring, which allowed them to efficiently compute auxiliary isogenies required for the attack.
One week later, Luciano Maino and Chloe Martindale published a paper: An attack on SIDH with arbitrary starting curve describing an independently derived attack on SIDH. Compared to the work of Castryck and Decru, they assumed no knowledge of the endomorphism ring of the curve, but the price to pay was that their attack had subexponential complexity. However, their work also contained a description of how you did not need to perform this chain of dimension-two isogenies to derive a secret, but rather only one successful oracle call was enough to completely derive the secret path. Following this paper, a third paper Breaking SIDH in polynomial time by Damien Robert showed that the attack of Maino and Martindale could be adapted to be provable polynomial time again by using dimension-eight isogenies between abelian varieties, where the auxiliary isogeny could always be computed.
For a high-level discussion of the Castryck-Decru attack on SIDH, Thomas Decru wrote a fantastic blog post and if you’re interested in how the attack is implemented, I wrote a fairly detailed blog post last year on the implementation of their attack using SageMath. My experience of this implementation is what led to the collaboration with Maino and Martindale, where together with Lorenz Panny we wrote a proof of concept implementation of their attack in SageMath.
The attacks on SIDH were not only beautiful pieces of cryptanalysis but were particularly important as only weeks before, SIKE had been chosen by NIST to continue to the fourth round of their post-quantum cryptography project. The huge impact of this work was acknowledged at this year’s Eurocrypt, where the Castryck-Decru attack won the best paper award and Robert’s and our work was given an honorable mention:
- An efficient key recovery attack on SIDH
★ Best Paper Award
Wouter Castryck and Thomas Decru - A Direct Key Recovery Attack on SIDH
★ Best Paper Honorable Mention
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope and Benjamin Wesolowski - Breaking SIDH in Polynomial Time
★ Best Paper Honorable Mention
Damien Robert
These three papers were collected into a single plenary session on the second day of the conference and in turn, Thomas, Luciano and Damien took their 20 minutes to discuss their variant of the attacks and what this means for isogeny-based cryptography in the future. You can watch the session via YouTube.
Although the polynomial time break of SIDH is dramatic, the attack relies on the protocol sharing auxiliary data which many isogeny schemes never need. This means that although SIDH is broken, schemes such as CSIDH (another key exchange protocol) and SQISign (a digital signature algorithm) are unaffected by these attacks. In fact, when asked in the questions following their talks, all three authors expressed excitement of the new possibilities that these attacks offered and suggested that constructive applications of these techniques will open up isogeny-based cryptography to new and exciting protocols.
To continue the theme, isogenies also took first place on Tuesday night, when the The Superspecial Isogeny Club Quartet won the best rump session award with their song Kani came in like a wrecking ball.
Selected Talks
There were more than 100 papers published this year, and with the conference running with parallel tracks it was impossible to see every talk, let alone talk about them all here. However, there is time to mention a few talks which stood out to me during the week and I’m afraid that my post-quantum-bias shows up here!
Just how hard are rotations of Zn? Algorithms and cryptography with the simplest lattice
Huck Bennett, Atul Ganju, Pura Peetathawatchai, Noah Stephens-Davidowitz [Presentation]
Imagine you draw the simplest lattice possible: the unit lattice. In two dimensions, this could be drawn by putting a dot on each corner of a square on a grid. In three dimensions it would mean drawing a dot for each vertex of a tiling of cubes. The intuitive basis to draw for these lattices is to take the unit vectors which take orthogonal steps in each direction. By taking these steps sequentially you can reach any dot in the lattice. This basis isn’t only nice, but it is the shortest basis we can draw.
Now, rather than being given this natural basis, imagine you’re given some ugly basis which has been found by first rotating the lattice and performing the same trick of finding vectors connecting dots by travelling directly upwards or sideways. The question is that when presented this long lattice basis, can you determine whether this is a lattice basis for the rotated simple lattice or just some random lattice? One way to answer this question is to determine if the basis describes the rotated unit lattice by finding the shortest basis and seeing if it is the orthogonal unit basis.
Surprisingly, this question seems to be difficult to answer. In fact, despite partial progress of finding efficient algorithms to solve this problem, this talk suggests that this is a cryptographically hard problem. From this, the authors build an encryption scheme based off the assumed hardness of this problem. I love cryptographic problems like this. The idea that you can take the simplest lattice we can construct and hide it almost completely with only a rotation is fascinating. I’m looking forward to seeing the progress / adoption on this problem. Either constructively from the hardness of this problem or cryptanalytically with a breakthrough on recovering the short orthogonal basis for this lattice problem.
Supersingular Curves You can Trust
Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis and Benjamin Wesolowski [Presentation]
In the isogeny world, a surprisingly hard problem to solve is how to find a way to “hash” to a supersingular elliptic curve. To understand this problem, let’s move over to the more familiar problem of hashing to points. For classical elliptic curve cryptography, there are times where a protocol requires the use of a point in a prime-order subgroup of the curve for which no one knows its relation to some fixed generator of the curve. This means we cannot compute the point as a scalar multiple of the generator but rather find a way to directly compute a point. This can de done efficiently and is discussed in the following IETF draft.
For isogeny-based cryptography, rather than ensuring no one knows a “scalar”, the important knowledge to hide is the endomorphism ring of the elliptic curve. At a high level, the endomorphism ring can be thought of as the collection of all of the isogenies which map from a curve to itself. Currently we have two methods of finding supersingular elliptic curves: compute a curve directly using the theory of complex multiplication or take a known supersingular curve and compute an isogeny to walk to some new curve.
The problem we have is that using complex multiplication to derive a curve necessarily also allows one to learn the endomorphism ring. For the isogeny walk, if you know the starting curve’s endomorphism ring and the isogeny connecting the curves, you also know the endomorphism ring of the final curve.
The authors of this work propose “SECUER: Supersingular Elliptic Curves with Unknown Endomorphism Ring”, a proposal of a trustless setup to “hash” to these curves. The idea is relatively simple. Although no one person can “hash” to a curve, if many people can work together, a curve with unknown endomorphism ring can be computed as long as one participant of the protocol is honest. The trick is to start with some curve and for the first user to randomly walk to a new curve. Although this user knows the endomorphism ring of their ending curve, if their isogeny is kept secret, then anyone given this curve cannot reasonably compute the endomorphism ring. By passing the end result of an isogeny to many users in a sequence, the final curve will have an endomorphism ring which could only be derived if every user has knowledge of every secret isogeny path taken.
Lattice Cryptography: What Happened and What’s Next
Vadim Lyubashevsky [Presentation]
The second invited speaker of Eurocrypt 2023 was Vadim Lyubashevsky of IBM, who gave a brilliant talk focusing on what has happened since Kyber and Dilithium were picked to be standardised by NIST after their selection in round three of the NIST post-quantum cryptography competition. For an overview of the selections, see NCC Group’s earlier blog post written by Thomas Pornin.
The talk discussed not only lattices and quantum-safe cryptography, but also served as a place to discuss the other complicated parts of the NIST competition and standardisation of protocols including patent issues, NIST/NSA conspiracy theories and the ongoing effort of migrating from our current cryptograph to something which is quantum-safe.
The latter half of the talk looked at future work and discussed progress on efficient zero-knowledge protocols using lattices. In particular, two projects which were mentioned were the new work on practical lattice-based zero knowledge proofs based on the hardness of Module-SIS and Module-LWE problems and new progress on practical anonymous credentials built from hard lattice problems.
Disorientation Faults in CSIDH
Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders, Jana Sotáková and Monika Trimoska [Presentation]
Although many of the talks at Eurocrypt were fantastically presented with engaging speakers and great cryptography, I think this talk is a principle example of how presentation slides can be used as a visual aide to demystify complex papers in such a way that an audience can really connect with a paper in the 20 minute slot the authors are given. I have included a link to the presentation for all these summarised talks, and really recommend watching this one.
The presentation described a fault attack on CSIDH, an isogeny-based key exchange protocol which is particularly interesting as it is both quantum-safe (although there are sub-exponential quantum attacks against the protocol) and is non-interactive. As with most isogeny-based protocols, the idea of CSIDH is that users Alice and Bob perform secret walks through an isogeny graph and send their end curves to each other. However, unlike SIDH which needed the deadly auxiliary data to allow the exchange to work, CSIDH is naturally commutative and Alice and Bob simply walk their path again from each other’s public curves to reach a shared secret curve.
When performing these walks, Alice and Bob both have a notion of “positive” and “negative” steps on their isogeny graphs. For the more mathematical, these directions are associated to walking from either a curve or its quadratic twist. Practically, random points are sampled and the code checks whether this will take the user in a positive or negative direction and keeps track of the remaining steps to take to finish the walk. The important part of this to understand is that for a single secret walk, the actual protocol requires taking many smaller walks in the isogeny graph in either these positive or negative directions.
By using a fault attack to trick the algorithm in taking positive steps when they should be negative (or vice-versa) the paper shows that information about the smaller sub-paths of the walk is leaked. By repeating fault attacks, an attacker can find information about each of these smaller walks making up the secret path. Given enough data, one can efficiently recover the secret walk by concatenating these smaller paths, breaking the protocol with an active side-channel.
An isogeny path to Zürich
Next year, Eurocrypt 2024 will be held in Zürich, Switzerland. With all the active research in isogeny-based cryptography, I’m excited to see where we are twelve months from now and with a little luck, hopefully I can enjoy Eurocrypt again next year with some new results of my own. For those who couldn’t attend this year, or just want to catch the sessions which collided with the ones they attended, IACR has uploaded all the talks to their YouTube channel.
Acknowledgements
Thanks to Paul Bottinelli of NCC Group for proof-reading an earlier draft of this post.
