Isogeny-based post-quantum crypto

I’ve been meaning to write about isogeny-based crypto for a long while. This area has steadily become more and more active and there are now many researchers working seriously on it. The main motivation is its potential to provide a key exchange primitive that is efficient enough for practical deployment, yet potentially secure against an adversary with a quantum computer.

The first suggestions to use isogenies in crypto were due to Couveignes (in a talk in 1997), Charles, Lauter and Goren (a hash function proposed in 2005) and Rostovtsev and Stolbunov (eprint, 2006). But the biggest impetus came from the paper by David Jao and Luca De Feo in PQCrypto 2011. This paper presents the supersingular isogeny Diffie-Hellman (SIDH) key exchange scheme that has potential to be post-quantum secure.

The first thing to note is that the Jao and De Feo scheme is based on supersingular elliptic curves. Readers might think: Supersingular curves are weak for classical crypto, and ECDLP is broken by Shor’s algorithm, so how can this be a good idea? The point is that we are no longer basing security on discrete logarithms, or any “algebraic” property of a specific elliptic curve. Instead, the basic structure is group homomorphisms between curves.

There are several reasons to be interested in supersingular isogeny crypto.

  • The pool of potential post-quantum assumptions is very small, and so all avenues need to be fully explored and tested.
  • There has been a huge body of knowledge and experience developed over the last 20 years in support of elliptic curve crypto, and so it is natural to try to continue using elliptic curves if possible.
  • Some of the underlying computational problems have already been considered by researchers in classical elliptic curve crypto and computational number theory, and so there is some good evidence that the assumptions are reasonable, at least against classical computers.
  • It is straightforward to choose parameters to achieve a given security level. In contrast, selecting parameters for lattice crypto that achieve a given security level is still problematic. For example, different models of how the BKZ algorithm performs lead to quite different results (although it is possible to make conservative choices that still lead to a practical scheme).

However, there are also several serious concerns about supersingular isogeny crypto.

  • One of the most serious concerns is that the systems have not been sufficiently scrutinised by researchers in quantum algorithms. A contributing factor is that there are significant mathematical preliminaries needed to fully understand isogeny crypto, and so it is not an easy field for non-experts to work in.
  • Another concern, especially in contrast to lattices, is that isogenies are not a very “expressive” tool. Lattice crypto has provided a rich suite of cryptographic functionalities including encryption, signatures, id-based crypto, homomorphic encryption, and more. On the other hand, the only practical isogeny crypto primitive known is key exchange. We do not even have a practical digital signature scheme based on isogenies (see Yoo et al in FC2017 and this paper, which is to appear at Asiacrypt 2017), and signatures are a relatively basic primitive.

The main conceptual idea of isogeny key exchange is the following: In the original Diffie-Hellman protocol Alice sends to Bob g^a and Bob sends to Alice g^b. One can interpret this in terms of group homomorphisms: Alice has a private group homomorphism \phi : G \to G defined by \phi(x) = x^a and Bob has a private group homomorphism \psi : G \to G defined by \psi(x) = x^b. Alice publishes \phi(g) and Bob publishes \psi(g). Alice completes the protocol by computing \phi( \psi(g )) and Bob computes \psi( \phi( g )). The homomorphisms commute so Alice and Bob compute the same key.

An isogeny is a group homomorphism from an elliptic curve E. An isogeny has a finite kernel G. So one can think of an isogeny as a homomorphism E \to E/G. The crucial fact is that there is a way to represent the image E/G in a form that does not reveal the group G. In other words, it is not represented using cosets, but as another elliptic curve.

The key exchange protocol is then seen to be analogous to the Diffie-Hellman protocol. Fix an elliptic curve E. Alice has a private subgroup G_A and a private isogeny (group homomorphism) \phi : E \to E/G_A. Bob has a private subgroup G_B and a private isogeny \psi : E \to E/G_B. Alice publishes \phi(P) for some points P \in E that enable Bob to compute \phi(G_B). Bob computes \psi( Q ) for some other points Q \in E that enable Alice to compute \psi( G_A ). Then Alice computes (E/G_B)/\psi(G_A) and Bob computes (E/G_A)/\phi(G_B) and in both cases they get the same elliptic curve (up to isomorphism) E/(G_A,G_B). For details see the paper by Jao and De Feo, or any of the other subsequent papers in the field.

One reason to choose supersingular elliptic curves is that it makes key generation and some computational and theoretical aspects of the protocol much more simple and efficient than if using other elliptic curves.

The fundamental computational problem underlying isogeny crypto is the problem: Given two elliptic curves E, E' to find an isogeny \phi : E \to E'. This has been studied by researchers since David Kohel’s thesis in the mid-1990s and is a well-established problem in computational number theory. Only exponential-time classical algorithms are known for this problem. Moving to quantum algorithms: Childs, Jao and Soukharev gave in 2014 a subexponential-time quantum algorithm for the ordinary curve case. However, for supersingular curves the only quantum algorithm known is by Biasse, Jao and Sankar and it requires exponential time and subexponential space. This gives further motivation to only consider the case of supersingular curves.

However, it is important to note that the Jao-De-Feo key exchange scheme relies on a weaker variant of this problem. In the scheme one gets two elliptic curves E, E' plus two pairs of points (P, \phi(P)) where \phi : E \to E' is an isogeny of known degree. Using these points one can generate exponentially many points (R, \phi(R)) on the graph of \phi. Is it possible to compute \phi using some kind of interpolation algorithm? Perhaps a quantum algorithm? A recent paper by Christophe Petit explores a novel classical approach to solving this variant of the isogeny problem, but currently these methods do not break practical versions of the SIDH scheme.

In conclusion, isogeny crypto is a very interesting and active area of research in crypto. However, more investigation is needed by researchers in quantum algorithms before we can be confident that it really is post-quantum secure. If you wish to learn more about the subject then I recommend this paper for a tutorial on the basic theory, and for a discussion of computational problems of interest.

— Steven Galbraith

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Isogeny-based post-quantum crypto

  1. JPF says:

    Hi Steven, what is the 97 Couveignes talk you have in mind? Best, JPF

    • ellipticnews says:

      This is documented in a paper called “Hard Homogeneous Spaces” by Couveignes. He writes “This note was written in 1997 after a talk I gave at the séminaire de complexité et cryptographie at the École Normale Supérieure”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s