Summary. CSIDH is a (relatively) new proposal in isogeny-based cryptography that offers (conjecturally) post-quantum secure non-interactive key exchange with tiny public keys and practical performance.

Introduction

During the past five to ten years, elliptic-curve cryptography (ECC) has taken over public-key cryptography on the internet and in security applications. Many protocols such as Signal or TLS 1.3 rely on the small key sizes and efficient computations to achieve forward secrecy, often meaning that keys are used only once. However, it is also important to notice that security does not break down if keys are reused. Indeed, some implementations of TLS, such as Microsoft's SChannel, reuse keys for some fixed amount of time rather than for one connection. Google's QUIC relies on servers keeping their keys fixed for a while to achieve quick session resumption. Several more examples are given by Freire, Hofheinz, Kiltz, and Paterson in their paper formalizing non-interactive key exchange. Some applications require this functionality and for many it provides significant savings in terms of roundtrips or implementation complexity. Finding a post-quantum system that permits non-interactive key exchange while still offering decent performance is considered an open problem. Our paper presents a solution to this problem.

Isogeny-based cryptography is a relatively new kind of elliptic-curve cryptography, whose security relies on (various incarnations of) the problem of finding an explicit isogeny between two given isogenous elliptic curves over a finite field F_q. One of the main selling points is that quantum computers do not seem to make the isogeny-finding problem substantially easier. This contrasts with regular elliptic-curve cryptography, which is based on the discrete-logarithm problem in a group and therefore falls prey to a polynomial-time quantum algorithm designed by Shor in 1994.

The first proposal of an isogeny-based cryptosystem was made by Couveignes in 1997. It described a non-interactive key exchange protocol where the space of public keys equals the set of F_q-isomorphism classes of ordinary elliptic curves over F_q whose endomorphism ring is a given order O in an imaginary quadratic field and whose trace of Frobenius has a prescribed value. It is well-known that the ideal-class group cl(O) acts freely and transitively on this set through the application of isogenies. Couveignes' central observation was that the commutativity of cl(O) naturally allows for a key-exchange protocol in the style of Diffie and Hellman. His work was only circulated privately and thus not picked up by the community; the corresponding paper was never formally published and posted on ePrint only in 2006. The method was eventually independently rediscovered by Rostovtsev and Stolbunov in 2004 (in Stolbunov's master's thesis and published on ePrint in 2006). In 2010, Childs, Jao and Soukharev showed that breaking the Couveignes–Rostovtsev–Stolbunov scheme amounts to solving an instance of the abelian hidden-shift problem, for which quantum algorithms with a time complexity of L_q[1/2] are known to exist; see Kuperberg and Regev's papers. While this may be tolerable (e.g., classical subexponential factorization methods have not ended the widespread use of RSA), a much bigger concern is that the scheme is unacceptably slow: despite recent clever speed-ups due to De Feo, Kieffer, and Smith, several minutes are needed for a single key exchange at a presumed classical security level of 128 bits. Nevertheless, in view of its conceptual simplicity, compactness, and flexibility, it seems a shame to discard the Couveignes–Rostovtsev–Stolbunov scheme.

The attack due to Childs–Jao–Soukharev strongly relies on the fact that cl(O) is commutative, hence indirectly on the fact that O is commutative. This led Jao and De Feo to consider the use of supersingular elliptic curves, whose full ring of endomorphisms is an order in a quaternion algebra; in particular it is non-commutative. Their resulting (interactive) key-agreement scheme, which nowadays goes under the name "Supersingular Isogeny Diffie–Hellman" (SIDH), has attracted almost the entire focus of isogeny-based cryptography over the past six years. The current state-of-the-art implementation is SIKE, which was recently submitted to the NIST competition on post-quantum cryptography.

It should be stressed that SIDH is not the Couveignes–Rostovtsev–Stolbunov scheme in which one substitutes supersingular elliptic curves for ordinary elliptic curves; in fact SIDH is much more reminiscent of a cryptographic hash function from 2006 due to Charles, Goren, and Lauter. SIDH's public keys consist of the codomain of a secret isogeny and the image points of certain public points under that isogeny. Galbraith, Petit, Shani, and Ti showed that SIDH keys succumb to active attacks and thus should not be reused, unless combined with a CCA transform such as the Fujisaki–Okamoto transform.

In this paper we show that adapting the Couveignes–Rostovtsev–Stolbunov scheme to supersingular elliptic curves is possible, provided that one restricts to supersingular elliptic curves defined over a prime field F_p. Instead of the full ring of endomorphisms, which is non-commutative, one should consider the subring of F_p-rational endomorphisms, which is again an order O in an imaginary quadratic field. As before cl(O) acts via isogenies on the set of F_p-isomorphism classes of elliptic curves whose F_p-rational endomorphism ring is isomorphic to O and whose trace of Frobenius has a prescribed value; in fact if p ≥ 5 then there is only one option for this value, namely 0, in contrast with the ordinary case. See, e.g., Theorem 4.5 in Waterhouse, with further details to be found in papers by Bröker, Delfs–Galbraith and in Section 3 of this paper. Starting from these observations, the desired adaptation of the Couveignes–Rostovtsev–Stolbunov scheme almost unrolls itself; the details can be found in Section 4. We call the resulting scheme CSIDH, where the C stands for "commutative". (Since this work was started while being very close to a well-known large body of salt water, we pronounce CSIDH as ["si:­saId] rather than spelling out all the letters.)

While this fails to address Jao and De Feo's initial motivation for using supersingular elliptic curves, which was to avoid the L_q[1/2] quantum attack due to Childs–Jao–Soukharev, we show that CSIDH eliminates the main problem of the Couveignes–Rostovtsev–Stolbunov scheme, namely its inefficiency. Indeed, in Section 8 we will report on a proof-of-concept implementation which carries out a non-interactive key exchange at a presumed classical security level of 128 bits and a conjectured post-quantum security level of 64 bits in about 80 milliseconds, while using key sizes of only 64 bytes. This is over 2000 times faster than the current state-of-the-art instantiation of the Couveignes–Rostovtsev–Stolbunov scheme by De Feo, Kieffer and Smith, which itself presents many new ideas and speedups to even achieve that speed.

For comparison, we remark that SIDH, which is the NIST submission with the smallest combined key and ciphertext length, uses public keys and ciphertexts of over 300 bytes each. More precisely SIKE's version p503 uses uncompressed keys of 378 bytes long for achieving CCA security. The optimized SIKE implementation is about ten times faster than our proof-of-concept C implementation, but even at 80 ms CSIDH is practical.

Another major advantage of CSIDH is that we can efficiently validate public keys, making it possible to reuse a key without the need for transformations to confirm that the other party's key was honestly generated.

Finally we note that just like the original Couveignes–Rostovtsev–Stolbunov scheme, CSIDH relies purely on the isogeny-finding problem; no extra points are sent that could potentially harm security, as argued by Petit.

To summarize, CSIDH is a new cryptographic primitive that can serve as a drop-in replacement for the (EC)DH key-exchange protocol while maintaining security against quantum computers. It provides a non-interactive (static–static) key exchange with full public-key validation. The speed is practical while the public-key size is the smallest for key exchange or KEM in the portfolio of post-quantum cryptography. This makes CSIDH particularly attractive in the common scenario of prioritizing bandwidth over computational effort. In addition, CSIDH is compatible with 0-RTT protocols such as QUIC.

Papers

(PDF) Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes. "CSIDH: An Efficient Post-Quantum Commutative Group Action". Date: 2018.11.18. ASIACRYPT 2018, LNCS 11274, pages 395–427.