My name is Bruno Sterner and as of October 2019, I am a PhD student in the Secure Systems Research Group. My research looks into the security, efficiency and the underlying mathematics of post-quantum isogeny-based cryptosystems. These schemes, such as SIDH, SIKE, CSIDH etc, rely on the hardness of computing isogenies between supersingular elliptic curves.
I recently participated in the Eurocrypt 2020 conference. Not only was this my first attendance of the conference but it was the very first time that an IACR conference was hosted virtually. The organisers of the event did a great job of making sure that the conference went ahead and was run smoothly.
There was a wide range of topics that were presented at the conference including Broadcast Encryption, Attribute-Based Encryption, Symmetric Cryptology, Multi-Party Computation, Zero-Knowledge, Verifiable Delay Functions and more. There was definitely something there for everyone. The talks given at this conference as well as the live sessions have been uploaded to the IACR YouTube channel for your viewing pleasure.
In this blog entry I will focus on a few of the number-theoretic talks that were presented at the conference. I chose to write about these talks as they have some relevance to my research on isogenies.
“Mathematics & Cryptography: A Marriage of Convenience?”
Alice Silverberg
As an invited speaker, Alice talked about her life experiences in mathematics and cryptography. These experiences were presented as stories which served a purpose of conveying an important theme. The first theme was the idea of communication within the community as well as outreach speaking and avoiding jargon. One of the stories she told with this theme goes back to when the proof of Fermat’s Last Theorem was presented by Andrew Wiles. A reporter went to interview mathematicians regarding this result. Alice saw the reporter confused by the use of the term rationals and he wasn’t sure what that meant. As a result Alice leaned over and whispered to the reporter “when he says rationals, he means fractions”. Upon receiving this, the reporter thanked Alice. The moral of the story is to make sure you communicate in such a way that reflects the receivers background. Other themes mentioned included curiosity, listening, openness and doing the right thing. Alongside all this she briefly talked about her work on algebraic tori, multilinear maps, and the Gentry-Szydlo algorithm.
CSIDH Interlude
Before I continue to the other talks I will very briefly describe the CSIDH key exchange protocol. CSIDH (Commutative Supersingular Isogeny Diffie Hellman) is a post-quantum isogeny-based primitive serving as a potential drop-in replacement for the ECDH (Elliptic Curve Diffie Hellman) key exchange primitive. This scheme was introduced in a 2018 Asiacrypt paper by Castryck, Lange, Martindale, Panny and Renes, which was inspired by previous work from Couveignes, Rostovtsev and Stolbunov. This primitive works on the following group action: the class group of an ideal in an imaginary quadratic number field acting on the set of isomorphism classes of supersingular elliptic curves over a prime field.
“Rational isogenies from irrational endomorphisms”
Wouter Castryck, Lorenz Panny and Frederik Vercauteren
It is well documented in the isogeny literature that there is an algorithm for computing an isogeny between elliptic curves given their endomorphism rings. This is due to Kohel, Lauter, Petit, Tignol. However, this reduction does not necessarily give us the isogeny used in the CSIDH protocol as it may not be defined over the prime field. One of the main contributions of this paper coming up with an analogue of this algorithm but for curves over a prime field. Similar to the KLPT algorithm it computes an ideal in the prime endomorphism ring which then can be used to compute the isogeny. One caveat is that the whole process of computing the isogeny takes subexponential time and it could well be the case this one cannot do any better. This is because if you could then you might be able to compute faster discrete logarithms in the class group.
Another contribution of this paper discusses the potential of hashing into a supersingular isogeny graph without revealing a path to a known curve. This was first suggested by Charles, Goren and Lauter through a random walk in the graph. This approach is flawed from the outset as it leaks an isogeny from a base curve. It is possible to generate supersingular curves using the theory of complex multiplication and therefore it is natural to ask whether this method can be useful for hashing. The result they arrived at says that this idea of hashing is not possible as they manage to reveal path to a known base curve.
“He Gives C-Sieves on the CSIDH”
Chris Peikert
From the initial CSIDH paper, parameter sets were chosen based on the NIST post-quantum standardisation security levels. Since the underlying problem of attacking CSIDH can be reframed as instance of the HSP (Hidden Shift Problem), Kuperberg’s sieve of attacking the generic HSP can be applied to this scheme which has a quantum subexponential complexity. This paper analyses the security of CSIDH and these parameter sets from this sieve. The focus of this analysis is looking for a precise number of queries and amount of quantumly accessible classical memory which is used as part of the sieve.
The conclusions from this paper are that the proposed parameter sets for CSIDH provide very little quantum security beyond the cost of the quantum oracle. It turns out that another paper presented at the conference studied a very similar problem to that of Chris Peikert’s work and also came to the same conclusion. This is the paper “Quantum Security Analysis of CSIDH” by Bonnetain and Schrottenloher.
