The possibility of active attacks has been mentioned by Kirkwood, Lackey, McVey, Motley, Solinas and Tuller and Costello, Longa and Naehrig . To be precise, one could try to perform some kind of “small subgroup” or “invalid curve” attacks such as have been proposed for DLP cryptosystems in the past . These auxiliary points open the door to active attacks on the encryption scheme (or key exchange where one party uses a static key). One particular feature of Jao and De Feo’s protocols compared to other schemes based on isogeny problems is the publication of auxiliary points, which are used to get around the difficulties of non-commutativity. In contrast, the case of supersingular curves is non-commutative and seems to be a promising candidate for a post-quantum-secure system . However, there is a (subexponential) quantum algorithm to break the system in the ordinary case (in part since the ordinary case is based on commutative ring theory). The idea behind the supersingular isogeny key exchange protocol is largely based on the isogeny protocol for ordinary elliptic curves proposed in . As with classical Diffie–Hellman, the basic version of the key exchange protocol uses ephemeral elements, but the encryption scheme and some of the more sophisticated applications use static values for at least one element.
Similar problems had appeared in a previous hash function construction by Charles–Lauter–Goren , and were subsequently used to build other cryptographic functions such as public-key encryption, undeniable signatures and designated verifier signatures . The security of this scheme is based on so-called supersingular isogeny problems. In 2011, Jao and De Feo introduced the supersingular isogeny Diffie–Hellman key exchange protocol as a candidate for a post-quantum key exchange. However, it highlights that implementations of these schemes will need to take account of the risks associated with various active and side-channel attacks. We stress that our work does not imply that these systems are insecure, or that they should not be used.
Our paper therefore provides an improved understanding of the security of these cryptosystems. A corollary of this work is the first bit security result for the supersingular isogeny key exchange: Computing any component of the j-invariant is as hard as computing the whole j-invariant. This can be used to retrieve the secret key, given information leaked from a side-channel attack on the key exchange protocol. Our third contribution is to give a reduction that uses partial knowledge of shared keys to determine an entire shared key. This result gives significant insight into the difficulty of the isogeny problem that underlies the security of these schemes. Our second contribution is to show that the security of all schemes of this type depends on the difficulty of computing the endomorphism ring of a supersingular elliptic curve. This attack can only be prevented by using a (relatively expensive) countermeasure.
Our first contribution is to give a very powerful active attack on the supersingular isogeny encryption scheme. This is an active area of research in post-quantum cryptography. We study cryptosystems based on supersingular isogenies.
0 kommentar(er)
