Supersingular Isogeny Key Exchange

The Supersingular Isogeny Diffie–Hellman Key Exchange (SIDH) is a post-quantum public key cryptographic algorithm used to establish a secret key between two parties over an otherwise insecure communications channel. It was designed to resist cryptanalytic attack by an adversary in possession of a quantum computer. Because the SIDH has key sizes and computations similar to the widely supported Diffie–Hellman key exchange it is a natural candidate to replace Diffie-Hellman in the face of a growing quantum computer threat.

Introduction

Developments in quantum computing threaten the security of the cryptography used to secure the internet. Researchers at IBM's Watson Research Laboratories announced that functional quantum computers could be available in as little as 15 to 20 years.^[1] When sufficiently sized quantum computers exist, all of the commonly used public key algorithms, RSA, Diffie–Hellman, elliptic curve Diffie–Hellman and the Elliptic Curve DSA, will become insecure.

The SIDH was created in 2011 by De Feo, Jao, and Plut and published as: "Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies."^[2] Because the SIDH uses many of the same computational primitives (such as adding points on an elliptic curve) used in conventional elliptic curve cryptography, it may be easy to upgrade systems that use elliptic curve Diffie–Hellman to use the SIDH. A search of the World Intellectual Property Organization's Patent Database indicates that the SIDH is not patented by any of the authors of this paper.^[3]

Unlike other post-quantum public key systems, such as the McEliece system or NTRU, the SIDH method provides forward secrecy and thus avoids the risk associated with reliance on the security of long term secret keys. Forward secrecy is an important tool to prevent mass surveillance^[4] and to protect against memory leaks in systems as evidenced by the Heartbleed bug.^[5]

Background

The SIDH method works with the set of supersingular elliptic curves E over F_p², where the number of points on any such curve will be (p ± 1)². An isogeny of an elliptic curve E is a rational map from E to another elliptic curve E' such that the number of points on both curves is the same. For supersingular elliptic curves, isogenies are equivalently defined by points inside their kernel.

The SIDH method works with a prime of the form p = (w_A)^e_A(w_B)^e_B(f) ± 1 where w_A and w_B are small primes and an elliptic curve E defined by the equation: y² = x³ + ax + b. SIDH builds an isogeny maps from a single elliptic curve point which is taken as the generator for the isogeny's kernel. This point is chosen to be a random linear combination to two fixed points chosen to be in the kernel of the isogeny.

The j-Invariant of an elliptic curve E is a fixed function of a set of isomorphic curves. It is computed from the parameters that define the curve. For an elliptic curve E defined by the equation: y² = x³ + ax + b the j-invariant of the curve E is:

j(E) = 1728 \frac{4a^3}{4a^3+27b^2}.

Security

De Feo, Jao and Plut suggest that the security of SIDH will be:

O(p^1/4) for classical computers
O(p^1/6) for quantum computers.^[2]

This suggests that SIDH will be 128-bit secure for a prime (p) of 768 bits.

The set of isogenies of a supersingular elliptic curve together with operation of composition form a non-abelian group and the security of the SIDH is dependent on this non-abelian structure.^[2] The security of SIDH is closely related to the problem of finding the isogeny mapping between two supersingular elliptic curves with the same number of points. The most recent study of the difficulty of this problem is by Delfs and Galbraith and confirms the O(p^1/4) for classical computers.^[6]

Efficiency

During a Key exchange entities A and B will each transmit information 2 (mod p) coefficients defining an elliptic curve and 2 elliptic curve points. Each elliptic curve coefficient requires log₂p bits. Each elliptic curve point can be transmitted in log₂p+1 bits. Hence the transmission is 4log₂p + 2 bits. For a 768-bit modulus p for the elliptic curve this is 3074 bits; hence, the bandwidth for SIDH is equivalent to that of the non-quantum secure RSA or Diffie-Hellman public key systems at the 128-bit security level.

There are several different ways to compute isogenies given a point in the kernel of the isogeny. However, the optimal strategy for a prime p, as described above has work less than O(w_i^e_i) (i = A or B). Because of this, the value for w_i is often chosen as 2 or 3. With that choice the value of e_i is chosen to provide the desired security level.

In 2014, researchers at the University of Waterloo developed a software implementation of SIDH. They ran their partially optimized code on a X86-64 processor running at 2.4 GHz. For a 768-bit modulus they were able to complete the key exchange computations in 200 milliseconds thus demonstrating that the SIDH is computationally practical.^[7]

The SIDH Method

While several steps of SIDH involve complex isogeny calculations, the overall flow of SIDH for parties A and B is straightforward for those familiar with a Diffie-Hellman Key Exchange or its elliptic curve variant.

Setup

These are public parameters that can be shared by everyone in the network, or they can be negotiated by parties A and B at the beginning of a session.

1. A prime of the form $p = w_A^{e_A}\cdot w_B^{e_B}\cdot f \pm 1.$

2. A supersingular elliptic curve E over $\mathbb{F}_{p^2}$ .

3. Fixed elliptic points $P_A, Q_A, P_B, Q_B \text{ on } E.$

4. The order of $P_A$ and $Q_A$ is $(w_A)^{e_A}.$ The order of $P_B$ and $Q_B$ is $(w_B)^{e_B}$ .

Key exchange

In the key exchange, parties A and B will each create an isogeny from a common elliptic curve E. They each will do this by creating a random point in what will be the kernel of their isogeny. The kernel of their isogeny will be spanned by the pairs of points $P_A$ , $Q_A$ and $P_B$ , $Q_B$ respectively. The different pairs of points used ensure that parties A and B create different, non-communting, isogenies. A random point ( $R_A$ , or $R_B$ ) in the kernel of the isogenies is created as a random linear combination of the points $P_A$ , $Q_A$ and $P_B$ , $Q_B$ .

Using $R_A$ , or $R_B$ , parties A and B then use Velu's formulas for creating isogenies $\phi_A$ and $\phi_B$ respectively. From this they compute the image of the pairs of points $P_A$ , $Q_A$ or $P_B$ , $Q_B$ under the $\phi_A$ and $\phi_B$ isogenies respectively.

As a result A and B will now have two pairs of points $\phi_B(P_A)$ , $\phi_B(Q_A)$ and $\phi_A(P_B)$ , $\phi_A(Q_B)$ respectively. A and B now exchange these pairs of points over a communications channel.

A and B now use the pair of points they receive as the basis for the kernel of a new isogeny. They use the same linear coefficients they used above with the points they received to form a point in the kernel of an isogeny that they will create. They each compute points $S_{BA}$ and $S_{AB}$ and use Velu's formulas to construct new isogenies.

To complete the key exchange, A and B compute the coefficients of two new elliptic curves under these two new isogenies. They then compute the j-invariant of these curves. Unless there were errors in transmission, the j-invariant of the curve created by A will equal to the j-invariant of the curve created by B.

Notationally, the SIDH key exchange between parties A and B works as follows:

1A. A generates two random integers m_A, n_A < (w_A)^eA

2A. A generates $R_A := m_A \cdot (P_A)+ n_A\cdot (Q_A).$

3A. A uses the point $R_A$ to create an isogeny mapping $\phi_A: E\rightarrow E_A$ and curve $E_A$ isogenous to $E.$

4A. A applies $\phi_A$ to $P_B$ and $Q_B$ to form two points on $E_A: \phi_A(P_B)$ and $\phi_A(Q_B).$

5A. A sends to B $E_A, \phi_A(P_B)$ , and $\phi_A(Q_B).$

1B - 4B: Same as A1 through A4, but with A and B subscripts swapped.

5B. B sends to A $E_B,\phi_B(P_A)$ , and $\phi_B(Q_A).$

7A. A has $m_A, n_A, \phi_B(P_A)$ , and $\phi_B(Q_A)$ and forms $S_{BA} := m_A(\phi_B(P_A)) + n_A(\phi_B(Q_A)).$

8A. A uses $S_{BA}$ to create an isogeny mapping $\psi_{BA}$ .

9A. A uses $\psi_{BA}$ to create an elliptic curve $E_{BA}$ which is isogenous to E.

10A. A computes $K := \text{ j-invariant } (j_{BA})$ of the curve $E_{BA}$ .

7B. Similarly, B has $m_B, n_B, \phi_A(P_B)$ , and $\phi_A(Q_B)$ and forms $S_{AB} = m_B (\phi_A(P_B)) + n_B(\phi_A(Q_B))$ .

8B. B uses $S_{AB}$ to create an isogeny mapping $\psi_{AB}$ .

9B. B uses $\psi_{AB}$ to create an elliptic curve $E_{AB}$ which is isogenous to E.

10B. B computes K = j-invariant ( $j_{AB})$ of the curve $E_{AB}$ .

The curves $E_{AB}$ and $E_{BA}$ will be guaranteed to both will have the same j-invariant. A function of K is used as the shared key.^[2]

Similar Systems, Signatures, and Uses

A predecessor to the SIDH was published in 2006 by Rostovtsev and Stolbunov. They created the first Diffie-Hellman replacement based on elliptic curve isogenies. Unlike the method of De Feo, Jao, and Plut, the method of Rostovtsev and Stolbunov used ordinary elliptic curves^[8] and was found to have a subexponential quantum attack.^[9]

In March 2014, researchers at the Chinese State Key Lab for Integrated Service Networks and Xidian University, extend the security of the SIDH to a form of digital signature with strong designated verifier.^[10] In October 2014, well known elliptic curve researchers Jao and Soukharev from the University of Waterloo presented an alternative method of creating undeniable signatures with designatured verifier using elliptic curve isogenies.^[11]

References

↑ Utsler, Jim (2013). "Quantum Computing Might Be Closer Than Previously Thought". IBM. Retrieved 27 May 2013.
↑ 2.0 2.1 2.2 2.3 De Feo, Luca; Jao, Plut. "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" (PDF). PQCrypto 2011. Springer. Retrieved 4 May 2014.
↑ "PATENTSCOPE". www.wipo.int. World Intellectual Property Organization. Retrieved 14 June 2014.
↑ Higgins, Parker. "Long Term Privacy with Forward Secrecy". Electronic Frontier Foundation. Retrieved 4 May 2014.
↑ Zhu, Yan. "Why the Web Needs Perfect Forward Secrecy More Than Ever". Electronic Frontier Foundation. Retrieved 4 May 2014.
↑ Delfs, Christina; Galbraith (29 Oct 2013). "Computing isogenies between supersingular elliptic curves over F_p". arXiv.org. arXiv.org. Retrieved 20 June 2014.
↑ Fishbein, Dieter (30 April 2014). "Machine-Level Software Optimization of Cryptographic Protocols". University of Waterloo Library - Electronic Theses. University of Waterloo. Retrieved 21 June 2014.
↑ Rostovtsev, Alexander; Stolbunov (2006). "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES". Springer. Archived from the original (PDF) on 29 May 2006. Retrieved 10 May 2014.
↑ Childs, Andrew M; Jao, Soukharev. "Constructing elliptic curve isogenies in quantum subexponential time". Journal of Mathematical Cryptology. De Gruyter. Retrieved 4 May 2014.
↑ Sun, Xi; Tian (2 March 2014). "Toward quantum-resistant strong designated verifier signature". International Journal of Grid and Utility Computing. doi:10.1504/IJGUC.2014.060187. Retrieved 21 June 2014.
↑ Jao, David (October 2014). "Isogeny Based Quantum Resistant Undeniable Signatures" (PDF). David Jao Research. University of Waterloo. Retrieved 18 October 2014.