Is SIKE broken yet?

Home About

Schemes

Name
Type
Classical Security
Quantum Security
References
Additional Information
Key Exchange
Õ(n3)
Õ(n3)
JDF11 DJP14 CLN16

Comment

[JDF11] explored using isogenies of degree $\ell^e$ for various choices of $\ell$. It is only with [DJP14] that the choice of $\ell=2,3$ became standard. The choice of having $p = 3 \bmod 4$ and of a specific starting curve did not become standard until [CLN16].

Key Exchange
Õ(n8)
Õ(n8)
Pet17 BB+22

Comment

Folklore version SIDH, starting from a random curve of unknown endomorphism ring. First published mention in [Pet17], however it is currently not known how to generate such a curve without a trusted setup (see [BB+22]).

Key Exchange
Õ(n8)
Õ(n8)
Pet17 BdQ+19 Cos21

Comment

Folklore version of SIDH where the initiator (Alice) selects a random starting curve before starting the key exchange, and transmits it along with its public key. First published mention in [BdQ+19], Section 11.1, as a possible countermeasure against torsion point attacks (see [Pet17]). Also mentioned in [Cos21] for the same reason.

KEM
Õ(n3)
Õ(n3)
SIKE

Comment

Candidate to the NIST Post-Quantum Standardization process until the 4th round.

Key Exchange
Õ(n3)
Õ(n3)
Cos19

Comment

More compact variant of SIDH exploiting torsion points both on the curve and its twist.

Key Exchange, Non Interactive Key Exchange
exp(n)1/2
L(1/2)
Cou06 RS06 DKS18

Comment

Ancestor of CSIDH based on the theory of complex multiplication on ordinary curves defined over finite fields. Initially discovered by Couveignes in '97 [Cou06], was left unpublished and was independently rediscovered by [RS06]. [DKS18] introduce tweaks to the parameters to improve performance.

Key Exchange, Non Interactive Key Exchange
exp(n)1/2
L(1/2)
CL+18 CD19

Comment

Variant of CRS based on the action of $\mathrm{Cl}(\sqrt{-p})$ on supersingular curves defined over $\mathbb{F}_p$. Original proposal with $p = 3 \bmod 8$ in [CL+18], minor variant wiht $p = 7 \bmod 8$ in [CD19].

Key Exchange, Non Interactive Key Exchange
exp(n)0.292
exp(n)0.292
CK20

Comment

Variant of CRS/CSIDH based on the action of a class group on a set of supersingular curves reached by "volcano descent".

Σ-protocol, Signature
exp(n)1/2
L(1/2)
DG18

Comment

Proof of knowledge and signature based on group actions. Usually instantiated from CSIDH. Not very efficient.

Σ-protocol, Signature
exp(n)1/2
L(1/2)
Sto10 BKV19

Comment

Proof of knowledge and signature based on the group action CSIDH-512, for which the class group structure was computed on purpose.

Σ-protocol, Signature
Õ(n3)
Õ(n3)
DJP14 YA+17 DD+21 GK+21

Comment

Proof of knowledge and signature based on the SIDH assumption. Initially proposed in [DJP14]. [YA+17] adapts it into a signature, [DD+21] and [GK+21] fix mistakes in the security proof, [DD+21] introduces a variant with stronger soundness guarantees.

Σ-protocol, Signature
exp(n)1/2
exp(n)1/4
DD+21

Comment

Proof of knowledge and signature based on the weakSIDH assumption, i.e., the SIDH assumption without torsion point information.

Assumptions

Name
Classical Security
Quantum Security
References
Additional Information
Õ(n8)
Õ(n8)
JDF11 Pet17 QK+20

Comment

The problem of computing an isogeny of degree A between two random supersingular curves, given its action on a torsion subgroup of order B ≈ A, coprime A. First introduced in [JDF11] to claim security of SIDH, where A and B are powers of small primes, and then generalized in several works to cover general A and B.

Õ(n3)
Õ(n3)
-

Comment

Variant of CSSI where one of the two curves is "special", in the sense that its endomorphism ring is known and contains endomorphisms of "small" norm.

Õ(n3)
Õ(n3)
JDF11

Comment

The analogue of CDH for SIDH.

Õ(n3)
Õ(n3)
JDF11

Comment

The analogue of DDH for SIDH.

Õ(n3)
Õ(n3)
Cos19

Comment

The analogue of the SIDH problem for B-SIDH.

exp(n)0.292
exp(n)0.292
CK20

Comment

A generalisation of CSIDH in which the orientation and class group action is hidden in intermediate data, protecting against Kuperberg's subexponential quantum attack

exp(n)1/2
exp(n)1/4
CGL06 Wes21

Comment

Given two random supersingular curves, the problem of finding an isogeny walk between them. In some versions of the problem, one of the two curves is fixed. First considered in [CGL06]. Proven equivalent to the Endomorphism ring problem in [Wes21].

exp(n)1/2
exp(n)1/4
GP+16

Comment

The variant of the isogeny path problem where the distance between the two curves in some isogeny graph is bounded away from the average distance of two random curves. [GP+16] proves that this problem heuristically reduces to the problem of finding paths of generic length.

exp(n)1/2
exp(n)1/4
Koh96 Cer04 Wes21

Comment

Given a random supersingular curve, the problem of computing its endomorphism ring. First algorithms proposed in [Koh96]. Proven equivalent to the Isogeny path problem in [Wes21].

exp(n)1/2
L(1/2)
Wes21

Comment

Same as the supersingular endomorphism ring problem, but for random curves over a prime field $\mathbb{F}_p$.

exp(n)1/2
L(1/2)
BY01 Cou06 Sto10 GP+18

Comment

Given two random elements $x_0$, $x_1$ in a set acted upon transitively by a group $G$, find an element of G that maps $x_0$ to $x_1$. By random self-reducibility, this is equivalent to the problem where $x_0$ is fixed.

exp(n)1/2
L(1/2)
-

Comment

The variant where the set is a set of ordinary curves with endomorphism ring isomorphic to an order $\mathcal{O}$, and the set is the class group of $\mathcal{O}$.

exp(n)1/2
L(1/2)
CL+18 CPV19 Wes21

Comment

The variant where the set is a set of supersingular curves defined over a prime field $\mathbb{F}_p$, and the set is the class group ($\textrm{Cl}(\sqrt{-p})$. The reduction to the Endomorphism ring problem over $\mathbb{F}_p$ was done in steps in [CPV19] and [Wes21].

exp(n)0.292
L(1/2)
CK20 Wes21

Comment

The variant where the set is a set of supersingular curves with an orientation (an explicit embedding of a quadratic imaginary order into the endomorphism ring of the curve) and the group is the class group of the orientation. Shown to be equivalent to $\mathcal{O}$-EndRing in [Wes21].

exp(n)1/2
L(1/2)
Cou06 Sto10 GP+18

Comment

The anaologue of CDH for group actions.

exp(n)1/2
L(1/2)
-
-

Comment

exp(n)1/2
L(1/2)
CL+18
-

Comment

exp(n)0.292
L(1/2)
CK20 Wes21

Comment

Shown to be equivalent to $\mathcal{O}$-EndRing in [Wes21]

exp(n)1/2
L(1/2)
Sto10 AD+20 CSV20

Comment

The anaologue of DDH for group actions.

exp(n)1/2
L(1/2)
-
-

Comment

exp(n)1/2
L(1/2)
CL+18
-

Comment

exp(n)0.292
L(1/2)
CK20 CH+22
-

Comment

Comment

Given two supersingular isogenies $\phi: E_0 \to E_1$ and $\phi': E_2 \to E_3$ of the same degree $A$, and given an integer $B$ coprime to $A$, decide whether there exist isogenies $\psi: E_0 \to E_2$ and $\psi': E_1 \to E_3$ of degree $B$ such that $\phi,\phi',\psi,\psi'$ form a commutative diagram.

Attacks

Name
Complexity
Quantum?
References
Additional Information
MITM
exp(n)1/2
No
JDF11

Comment

Useful to find isogeny walks of unusually short length, such as in SIDH.

Tani
exp(n)1/3
Yes
Tan07

Comment

Claw finding quantum algorithm. Useful to find isogeny walks of unusually short length, such as in SIDH.

vOW
exp(n)3/4
No
vOW99 AC+18

Comment

Memory efficient version of MITM. For a fixed amount of memory the best time complexity is $\exp(n)^{3/4}$. If memory scales with input size, time can scale anywhere between $\exp(n)^{3/4}$ and $\exp(n)^{1/2}$.

Castryck-Decru
Õ(n3)
No
CD22

Comment

Solves the isogeny problem with torsion point information (CSSI), assuming the endomorphism ring of the starting curve is special.

CDMM
L(1/2)
No
CD22 MM22

Comment

$L(1/2)$ version of Castryck-Decru for arbitrary starting curve.

Robert
Õ(n8)
No
Rob22

Comment

Polynomial-time generalization of Castryck-Decru for arbitrary starting curve.

BJS
exp(n)1/4
Yes
BJS14

Comment

Quantum version of Delfs-Galbraith.

DG
exp(n)1/2
No
DG13

Comment

$\exp(1/4)$ reduction of the supersingular isogeny path problem to the vectorization problem for supsersingular curves over $\mathbb{F}_p$.

Kuperberg
L(1/2)
Yes
Kup04 CJS13

Comment

[Kup04] describes a generic quantum algorithm to solve the hidden shift problem (equivalently, the dihedral hidden subgroup problem). [CJS13] uses Kuperberg's algorithm as a subroutine to attack the vectorization problem.

Galbraith
exp(n)1/2
No
Gal99 GHS01

Comment

Random walk based algorithm to find an isogeny path between curves. [GHS01] is a more memory efficient version of [Gal99].

Dartois-De Feo
exp(n)0.292
No
DD21

Comment

Despite the exponential complexity, practically breaks proposed OSIDH parameters.