Supersingular isogeny-based cryptography

Summary

A robust family of quantum-resistant cryptographic algorithms based on the assumed computational complexity of pathfinding in isogeny graphs for supersingular elliptic curves and other related problems. The Supersingular Isogeny Key Encapsulation (SIKE) algorithm, an alternate candidate from the 3rd round of the NIST post-quantum competition, currently up for standardization in Russia, are both based on the pathfinding problem. Cryptographic algorithms from this family are relatively slow and yet able to provide short public keys and ciphertexts.
More on the topic

The potential appearance of a quantum computer able to implement Shor's algorithm poses a threat to traditional Diffie-Hellman-type key-agreement protocols based on the discrete logarithm problem. So, it has been proposed to use supersingular isogeny-based cryptography as a countermeasure.

An isogeny is a homomorphous rational map between two elliptic curves. If this kind of map is present between two curves, they are considered isogenous. An isogeny graph is a graph having a vertex set that is a set of isomorphism classes of elliptic curves. Two vertices of this graph are connected by an edge if and only if the representatives of the corresponding isomorphism classes are isogenous. If we confine ourselves to isogenies of degree l, we will get a graph of l-isogenies.

Upon closer examination of the so-called supersingular elliptic curves (considered "weak" in classical cryptography), it turned out that the graph of their l-isogenies has several properties allowing one to construct robust cryptographic schemes based on the assumed computational complexity of pathfinding between two graph vertices. These properties were studied by Couveignes (1997), Charles – Goren –Lauter (2006), Rostovtsev – Stolbunov (2006) and, finally, De Feo – Jao –Plût (2011), who were first to develop a stable and efficient key-agreement protocol known as SIDH. The SIKE algorithm, an alternate candidate from the 3rd round of the NIST post-quantum competition that provided the shortest public keys and ciphertexts, was based on SIDH.

The task of creating efficient supersingular isogeny-based authenticated key agreement schemes and digital signature protocols remains unfinished. The task of accelerating cryptographic supersingular isogeny-based algorithms is relevant as well.

    How to decide whether supersingular isogeny-based cryptography is the right choice for you?

    1. Analyze the challenges to be solved in the area of providing access to sensitive information, determining the suitability of a supersingular isogeny-based cryptography access control model, including when the data is stored in an untrusted cloud;
    2. Select and implement cryptographic algorithms optimal for solving the challenges defined in Step 1, taking the quantum threat into account;
    3. Design, pilot and implement supersingular isogeny-based cryptography solutions together with the QApp team.