A long time ago, when pairing-based cryptography was new, cryptographers who did not fully understand the mathematics of pairings would sometimes make mistakes. They would assume that everything that can be done with discrete logarithms could also be done with pairings. Unfortunately, this would sometimes result in protocols that were insecure, or else un-implementable.
Indeed, such cases apparently still happen:
This situation is natural whenever a crypto tool that is technically subtle (and crypto tools always have technical subtleties) moves from “niche” into the mainstream. However it can result in incorrect schemes being published, for example because there are not enough experts to review all the papers.
Back in 2006, in response to those issues in pairing-based crypto, Kenny Paterson, Nigel Smart and I wrote the paper Pairings for Cryptographers. The abstract read:
Many research papers in pairing based cryptography treat pairings as a “black box”. These papers build cryptographic schemes making use of various properties of pairings. If this approach is taken, then it is easy for authors to make invalid assumptions concerning the properties of pairings. The cryptographic schemes developed may not be realizable in practice, or may not be as efficient as the authors assume. The aim of this paper is to outline, in as simple a fashion as possible, the basic choices that are available when using pairings in cryptography. For each choice, the main properties and efficiency issues are summarized. The paper is intended to be of use to non-specialists who are interested in using pairings to design cryptographic schemes.
This abstract exhibits the particular style of understated writing that is cultivated by British people. What we really meant was: Please read this and stop screwing up.
Rolling forward 15 years, isogeny-based cryptography is another area with many technical subtleties, but is moving into the mainstream of cryptography. Once again, not everything that can be done with discrete logarithms can necessarily be done with isogenies. It is therefore not surprising to find papers that have issues with their security.
It is probably time for an Isogenies for Cryptographers paper, but I don’t have time to write it. Instead, in this blog post I will mention several recent examples of incorrect papers. My hope is that these examples are instructional and will help prevent future mistakes. My intention is not to bring shame upon the authors.
- In 2014, D. Jao and V. Soukharev proposed an isogeny-based undeniable signature scheme. The security analysis of their scheme required the introduction of some computational problems in isogenies. Recently, S.-P. Merz, R. Minko and C. Petit Another look at some isogeny hardness assumptions have broken the computational assumptions and formulated attacks on the scheme.
In this case, there is no reason for the original authors to be embarrassed. There has been considerable progress in isogeny crypto in the last 5 years, and it is natural that new cryptanalytic tools would become available that could break earlier schemes.
- Several papers, including this one, have argued that a certain decisional assumption related to the SIDH isogeny cryptosystem should be hard.
Without going into all the details, in SIDH there is a base curve
and four points
on it. An SIDH instance includes a triple
where
is an isogeny of degree
. One of the basic computational problems is to compute
when given this information.
The decisional assumption is to distinguish a valid triple
where
is a supersingular curve, and
are points satisfying various conditions.
At Provsec 2019, S. Terada and K. Yoneyama (“Password-based Authenticated Key Exchange from Standard Isogeny Assumptions”) proposed a password-based authenticated key exchange scheme for SIDH. The security against offline dictionary attacks was based on the hardness of a decision problem, but it was not the above decision problem. Instead, the security of the scheme under such an offline dictionary attack relies on the difficulty of distinguishing the triple
etc) which would not be satisfied by a uniformly chosen binary string. Hence the scheme in the paper is not secure against offline dictionary attacks.
It is actually a really interesting open question to fix this, related to compression of SIDH protocol messages. If one could compress SIDH protocol messages down to the minimum number of bits, then one might actually be able to argue that the protocol message is indistinguishable from a uniform binary string. I don’t know any way to solve this problem and I think it is probably impossible. For the state-of-the-art in compression of SIDH messages see G. H. M. Zanon, M. A. Simplicio Jr, G. C. C. F. Pereira, J. Doliskani and P. S. L. M. Barreto, “Faster key compression for isogeny-based cryptosystems”.
- A very natural and desirable feature is to be able to hash to an SIDH or CSIDH public key. Unfortunately this is hard. Really hard.
D. Boneh and J. Love Supersingular Curves With Small Non-integer Endomorphisms show, among other things, that it is hard to hash to SIDH public keys. W. Castryck, L. Panny and F. Vercauteren, Rational isogenies from irrational endomorphisms show it is hard to hash to CSIDH.
It would be great if someone can solve one of these problems, but I think they are both hard. In the meantime, cryptographers should not assume that it is possible to hash to public keys/protocol messages. This also limits the possibility to transport some protocols from the discrete-log world into the isogeny world.
- Due to the adaptive attacks on SIDH, one cannot get CCA1 or CCA2 secure encryption from SIDH without doing the Fujisaki-Okamoto transform (or something similar). Similarly, one cannot get non-interactive key exchange from SIDH. It is natural to try to get around this by some tweak to SIDH. R. Azarderakhsh, D. Jao and C. Leonardi gave a solution to this problem by running
instances in parallel (e.g. for
). S. Kayacan suggested two schemes that were hoped to be secure. However adaptive attacks have been shown in both schemes by my students and collaborators:
- S. Dobson, S. D. Galbraith, J. LeGrow, Y. B. Ti and L. Zobernig, An Adaptive Attack on 2-SIDH.
- S. Dobson, T. Li and L. Zobernig, A Note on a Static SIDH Protocol.
- A. Fujioka, K. Takashima, S. Terada and K. Yoneyama proposed an authenticated key exchange scheme similar to some previous discrete-log-based schemes that required gap assumptions in the security proof. Gap assumptions are of the form: Problem X is hard, even when given an oracle to solve the decisional variant of problem X.
For the isogeny context it is dangerous to use a gap assumption, as there are known arguments that one can reduce the computational isogeny problem to a decisional isogeny problem in certain cases. I already warned about this in the key exchange setting in this note. The solution of Fujioka et al was to introduce a “degree-insensitive” version of the problem, which is essentially to extend the protocol to
-isogeny chains of any length (rather than fixed length). It is an interesting idea.
However, my student S. Dobson and I have given evidence (see On the Degree-Insensitive SI-GDH problem and assumption) that the distribution of public keys in the degree insensitive case is close to uniform, and so it no longer makes sense to consider a gap problem. We do not have an attack on this protocol, but we conclude that the security proof is not correct. This shows again that one must be very careful to adapt ideas from discrete-log-based protocols into the isogeny setting.
- S. Furukawa, N. Kunihiro and K. Takashima (“Multi-party key exchange protocols from supersingular isogenies”) proposed an isogeny variant of the Burmester-Desmedt protocol for
-party key exchange in two rounds for any
Furukawa et al. [14] proposed an isogeny-based BD-type GKE protocol called SIBD. However, the security proof of SIBD (Theorem 4 in [14]) is imperfect, and several points remain unclear, for example, on how to simulate some public variables.
Once again, the scheme is not broken (as far as I know), but the security argument is not correct. Takashima gives a new security analysis in his paper (but I have not had time to check it).
What can authors do to avoid the dangers of isogeny crypto? There are some very good surveys of the basic ideas behind isogenies (for example see Mathematics of Isogeny Based Cryptography by Luca De Feo), but there is no good resource for cryptographers who want to use isogenies as a “black box”, and just want to know what is possible and what is not possible for building protocols. My best attempt so far is this note. In any case, I hope the present blog post can act as a cautionary tale: treating isogenies as a black box is risky!
— Steven Galbraith
ellipticnews 
I have been asked many times whether there is an “Isogenies for Dummies” paper. I believe it is a much harder paper to write than “Pairings for Dummies”.
The Hard Homogeneous Spaces (HHS) framework by Couveignes (https://ia.cr/2006/291) comes close to a simple abstraction for CSI-FiSh (https://eprint.iacr.org/2019/498), and to a lesser extent to CSIDH (https://eprint.iacr.org/2018/383). So, in a sense, the “Isogenies for Dummies” paper has been existing for as long as isogeny based crypto, although it wasn’t publicly available before 2006 (same year as Pairings for Dummies). But HHS has serious limits when it comes to abstracting the field: SeaSign (https://eprint.iacr.org/2018/824) would have had no reason to exist, if HHS had been an accurate abstraction.
Also, HHS does not cover a whole lot of isogeny based crypto: SIDH is much harder to abstract away as a black box. This is the only attempt I know of: https://ia.cr/2018/648. It was written with a very specific goal (Oblivious Transfer) in mind, and I have a feeling it is still quite unwieldy for the non-expert.
A pairing is an easy to define concept, and all crypto protocols use it through the same API. A pairing is one mathematical tool that enables many protocols; at the time, everyone understood how to use them, but there was a need to clarify what problems were easy and what were hard.
Isogenies are also easy to define, but knowing the definition won’t get you very far in terms of constructing new protocols. Instead of one mathematical tool, here you have 2-3 different algorithms, which happen to be related by the same mathematical theory. Isogeny graphs are already somehow a common abstraction, but they capture very little of SIDH.
To summarize my feelings, it is maybe the right time to revive HHS and write a pumped-up version of Couveignes’ paper; btw Jean-Marc should absolutely sign it, whoever ends up writing it! I am a bit concerned, though, that this may start a trend of papers that assume we’re going to break a new class group computation record every other month… maybe I already started the trend (https://eprint.iacr.org/2019/1288).
But for a broader treatment, also covering SIDH, I think it is a book, not a paper, that we need. I must say I would really like to see this book in print sooner than later!