It is analogous to the Diffie–Hellman key exchange, but is based on walks in a supersingular isogeny graph and was designed to resist cryptanalytic attack by an adversary in possession of a quantum computer.
SIDH also distinguishes itself[disputed – discuss] from similar systems such as NTRU and Ring-LWE [citation needed] by supporting perfect forward secrecy, a property that prevents compromised long-term keys from compromising the confidentiality of old communication sessions.
These properties seemed to make SIDH a natural candidate to replace Diffie–Hellman (DHE) and elliptic curve Diffie–Hellman (ECDHE), which are widely used in Internet communication.
However, SIDH is vulnerable to a devastating key-recovery attack published in July 2022 and is therefore insecure.
SIDH provides perfect forward secrecy 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 mass surveillance, and reduces the impact of vulnerabilities like Heartbleed.
Since the security of the scheme depends on the smaller torsion subgroup, it is recommended to choose
An excellent reference for this subject is De Feo's article "Mathematics of Isogeny Based Cryptography.
"[8] The most straightforward way to attack SIDH is to solve the problem of finding an isogeny between two supersingular elliptic curves with the same number of points.
At the time of the original publication due to De Feo, Jao and Plût, the best attack known against SIDH was based on solving the related claw finding problem, which led to a complexity of O(p1/4) for classical computers and O(p1/6) for quantum computers.
[5] A 2014 study of the isogeny problem by Delfs and Galbraith confirmed the O(p1/4) security analysis for classical computers.
[9] The classical security O(p1/4) remained unaffected by related cryptanalytic work of Biasse, Jao and Sankar as well as Galbraith, Petit, Shani and Yan.
[10][11] A more intricate attack strategy is based on exploiting the auxiliary elliptic-curve points present in SIDH public keys, which in principle reveal a lot of additional information about the secret isogenies, but this information did not seem computationally useful for attackers at first.
Petit in 2017 first demonstrated a technique making use of these points to attack some rather peculiar SIDH variants.
[12] Despite follow-up work extending the attack to much more realistic SIDH instantiations, the attack strategy still failed to break "standard" SIDH as employed by the NIST PQC submission SIKE.
In July 2022, Castryck and Decru published an efficient key-recovery attack on SIKE that exploits the auxiliary points.
[2][13] The attack relies on gluing together multiple of the elliptic curves appearing in the SIDH construction, giving an abelian surface (more generally, an abelian variety), and computing a specially crafted isogeny defined by the given auxiliary points on that higher-dimensional object.
It should be stressed that the attack crucially relies on the auxiliary points given in SIDH, and there is no known way to apply similar techniques to the general isogeny problem.
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.
[14] With these compression techniques, SIDH has a similar bandwidth requirement to traditional 3072-bit RSA signatures or Diffie-Hellman key exchanges.
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.
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.
In 2016, researchers from Florida Atlantic University developed efficient ARM implementations of SIDH and provided a comparison of affine and projective coordinates.
[18][19] In 2017, researchers from Florida Atlantic University developed the first FPGA implementations of SIDH.
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.
To complete the key exchange, A and B compute the coefficients of two new elliptic curves under these two new isogenies.
[5] The following parameters were taken as an example by De Feo et al.:[5] p = prime for the key exchange with wA = 2, wB = 3, eA = 63, eB = 41, and f = 11.
[23] 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.
[24] In October 2014, Jao and Soukharev from the University of Waterloo presented an alternative method of creating undeniable signatures with designated verifier using elliptic curve isogenies.[25][importance?]