Supersingular isogeny key exchange

Supersingular isogeny Diffie–Hellman key exchange (SIDH) is a cryptographic algorithm used to establish a secret key between two parties over an otherwise insecure communications channel. It is a form of the , but is designed to resist by an adversary in possession of a . SIDH uses the smallest key sizes among all post-quantum cryptosystems; with compression, SIDH uses 2688-bit public keys at a 128-bit quantum . SIDH also distinguishes itself from similar systems such as and by supporting , a property that prevents compromised long-term keys from compromising the confidentiality of old communication sessions. These properties make SIDH a natural candidate to replace (DHE) and (ECDHE), which are widely used in Internet communication.

Contents

Introduction

For certain classes of problems, algorithms running on are naturally capable of achieving lower than on classical computers. That is, can solve certain problems faster than the most efficient algorithm running on a traditional computer. For example, can factor an integer N in , while the best-known factoring classic algorithm, the , operates in . This is significant to because the security of is dependent on the infeasibility of factoring integers, the . Shor’s algorithm can also efficiently solve the , which is the basis for the security of , , , , , and . Although quantum computers are currently in their infancy, the ongoing development of quantum computers and their theoretical ability to compromise modern cryptographic protocols (such as ) has prompted the development of post-quantum cryptography.

SIDH was created in 2011 by De Feo, Jao, and Plut. It uses conventional operations and is not patented. SIDH provides and thus does not rely on the security of long-term private keys. Forward secrecy improves the long-term security of encrypted communications, helps defend against , and reduces the impact of vulnerabilities like .

Background

The supersingular isogeny Diffie-Hellman method works with the set of E over Fp2, where the number of points on any such curve will be (p ± 1)2. An of an elliptic curve E is a 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 .

The SIDH method works with a prime of the form p = (wA)eA(wB)eB(f) ± 1 where wA and wB are small primes and an elliptic curve E defined by the equation: y2 = x3 + ax + b. SIDH builds an isogeny map 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 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: y2 = x3 + ax + b the j-invariant of the curve E is:

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


Security

The set of isogenies of a supersingular elliptic curve together with operation of composition form a and the security of the SIDH is dependent on this non-abelian structure. The classical security, O(p1/4), of the SIDH was confirmed in the work of Biasse, Jao and Sankar as well as Galbraith, Petit, Shani and Bo Ti.

Efficiency

During a key exchange entities A and B will each transmit information 2 (mod p2) coefficients defining an elliptic curve and 2 elliptic curve points. Each elliptic curve coefficient requires log2p2 bits. Each elliptic curve point can be transmitted in log2p2+1 bits, hence the transmission is 8log2p + 2 bits. This is 6144 bits for a 768-bit modulus p (128-bit security). However, this can be reduced by over half to 2640 bits (330 bytes) using key-compression techniques, the latest of which appears in recent work by authors Costello, Jao, Longa, Naehrig, Renes and Urbanik. With these compression techniques, SIDH has a similar bandwidth requirement to traditional 3072-bit RSA signatures or Diffie-Hellman key exchanges. This small space requirement makes SIDH applicable to context that have a strict space requirement, such as Bitcoin or Tor. Tor’s data cells must be less than 517 bytes in length, so they can hold 330-byte SIDH keys. By contrast, NTRUEncrypt must exchange approximately 600 bytes to achieve a 128-bit security and cannot be used within Tor without increasing the cell size.

In 2014, researchers at the University of Waterloo developed a software implementation of SIDH. They ran their partially optimized code on an 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.

In 2016, researchers from Microsoft posted software for the SIDH which runs in constant time (thus protecting against timing attacks) and is the most efficient implementation to date. They write: “The size of public keys is only 564 bytes, which is significantly smaller than most of the popular post-quantum key exchange alternatives. Ultimately, the size and speed of our software illustrates the strong potential of SIDH as a post-quantum key exchange candidate and we hope that these results encourage a wider cryptanalytic effort.” Their software is posted on here.

In 2016, researchers from Florida Atlantic University developed efficient ARM implementations of SIDH and provided a comparison of affine and projective coordinates. In 2017, researchers from Florida Atlantic University developed the first FPGA implementations of SIDH.

The supersingular isogeny Diffie-Hellman 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 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-commuting, 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)^{e_A}.

2A. A generates R_A := m_A cdot (P_A)+ n_Acdot (Q_A).

3A. A uses the point R_A to create an isogeny mapping phi_A: Erightarrow 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).

6A. 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)).

7A. A uses S_{BA} to create an isogeny mapping psi_{BA}.

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

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

6B. 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)).

7B. B uses S_{AB} to create an isogeny mapping psi_{AB}.

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

9B. B computes K := text{ j-invariant } (j_{AB}) of the curve E_{AB}.

The curves E_{AB} and E_{BA} are guaranteed to have the same j-invariant. A function of K is used as the shared key.

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 and was found to have a subexponential quantum attack.

In March 2014, researchers at the Chinese State Key Lab for Integrated Service Networks and Xidian University extended the security of the SIDH to a form of digital signature with strong designated verifier. 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 designated verifier using elliptic curve isogenies.

Source

http://wikipedia.org/

See Also on BitcoinWiki