**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.

**Version:**This is version 2018.11.23 of the "Intro" web page.