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, computations and foward security protection similar to that of the widely supported Elliptic Curve Diffie–Hellman key exchange it is a natural candidate to replace Diffie-Hellman and Elliptic Curve Diffie-Hellman in the face of a growing quantum computer threat.
Developments in quantum computing threaten the security of the cryptography used to secure the internet. Researchers at IBM's Watson Research Laboratories announced in 2013 that functional quantum computers could be available in as little as 15 to 20 years. 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 Supersingular Isogeny Diffie-Hellman was created in 2011 by De Feo, Jao, and Plut and published as: "Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies." Because the Supersingular Isogeny method 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 Supersingular Isogeny Diffie-Hellman is not patented by any of the authors of this paper.
Unlike other post-quantum public key systems, such as the McEliece system or NTRU, the Supersingular Isogeny Diffie-Hellman 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 and to protect against memory leaks in systems as evidenced by the Heartbleed bug.
The Supersingular Isogeny Diffie-Hellman method works with the set of supersingular elliptic curves E over Fp2, where the number of points on any such curve will be (p ± 1)2. 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 = (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 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: y2 = x3 + ax + b the j-invariant of the curve E is:
De Feo, Jao and Plut suggest that the security of SIDH will be:
O(p1/4) for classical computers
O(p1/6) for quantum computers.
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. 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. A 2014 study of the difficulty of this problem is by Delfs and Galbraith and confirms the O(p1/4) for classical computers.
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 log2p bits. Each elliptic curve point can be transmitted in log2p+1 bits. Hence the transmission is 4log2p + 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(wiei) (i = A or B). Because of this, the value for wi is often chosen as 2 or 3. With that choice the value of ei is chosen to provide the desired security level. The mathematics of composing isogenies use a set of formula's by Velu. For these formulas and a discussion of isogeny computation see, "Isogenies of Elliptic Curves: A Computational Approach" by Shumow. Further aspects of isogeny computation are found in the work of Moody and Shumow.
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.
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.
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
2. A supersingular elliptic curve E over .
3. Fixed elliptic points
4. The order of and is The order of and is .
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 , and , respectively. The different pairs of points used ensure that parties A and B create different, non-communting, isogenies. A random point (, or ) in the kernel of the isogenies is created as a random linear combination of the points , and , .
Using , or , parties A and B then use Velu's formulas for creating isogenies and respectively. From this they compute the image of the pairs of points , or , under the and isogenies respectively.
As a result A and B will now have two pairs of points , and , 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 and 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 mA, nA < (wA)eA
2A. A generates
3A. A uses the point to create an isogeny mapping and curve isogenous to
4A. A applies to and to form two points on and
5A. A sends to B , and
1B - 4B: Same as A1 through A4, but with A and B subscripts swapped.
5B. B sends to A , and
7A. A has , and and forms
8A. A uses to create an isogeny mapping .
9A. A uses to create an elliptic curve which is isogenous to E.
10A. A computes of the curve .
7B. Similarly, B has , and and forms .
8B. B uses to create an isogeny mapping .
9B. B uses to create an elliptic curve which is isogenous to E.
10B. B computes K = j-invariant ( of the curve .
The curves and will be guaranteed to both will have the same j-invariant. A function of K is used as the shared key.
The following parameters are suggested by Defeo et. al as providing 128 bits of security:
p = 768-bit prime for the key exchange with wA = 2, wB = 3, eA = 63, eB = 41, and f = 11. Thus p = (263·341·11) + 1.
E0 = the base (starting) curve for the key exchange = y2 = x3 + x
Luca Defeo, one of the authors of the paper defining the key exchange has posted software that implements the key exchange for these and other parameters.
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.
- Utsler, Jim (2013). "Quantum Computing Might Be Closer Than Previously Thought". IBM. Retrieved 27 May 2013.
- 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.
- Shumow, Daniel (2009-10-27). "Isogenies of Elliptic Curves: A Computational Approach". arXiv:0910.5370 [cs].
- Moody, Dustin; Shumow, Daniel (2011). "Analogues of Velu's Formulas for Isogenies on Alternate Models of Elliptic Curves".
- 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.
- "defeo/ss-isogeny-software". GitHub. Retrieved 2015-05-29.
- 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.