SIDH

An Introduction to SIDH
David Jao
Department of Combinatorics & Optimization
Centre for Applied Cryptographic Research

Supersingular Isogeny Diffie-Hellman (Jao and De Feo, 2011):◮ A key-exchange protocol, similar to Diffie-Hellman, usingisogenies between supersingular elliptic curves
Why isogenies?
◮ Because they seem to be quantum-resistant

Why supersingular curves?
◮ We found a subexponential attack against ordinary (i.e.
November 18, 2018

Supersingular elliptic curves in cryptography

non-supersingular) curves (Childs, Jao, and Soukharev 2014)

History of isogeny-based public-key cryptography
Couveignes (1997), Rostovstev & Stolbunov (2006):

Previous applications of supersingular elliptic curves incryptography include:◮ Discrete logarithm attacks (Menezes, Okamoto, Vanstone)◮ Pairing-based cryptography (Joux)◮ Hash functions from expander graphs (Charles, Goren, Lauter)

The CGL hash function was the first published isogeny-basedcryptosystem.
◮ However, a hash function is “only” a one-way function, andcannot be used to achieve public-key encryption.
◮ Public-key encryption requires a trapdoor one-way function.

◮ Proposed a public-key cryptosystem using ordinary curves◮ Optimized by De Feo, Kieffer & Smith (2018)◮ Very slow
◮ Has subexponential security

Jao & De Feo, SIDH (2011):◮ Uses supersingular curves◮ (Relatively) fast
◮ Exponential security

Castryck et al., CSIDH (2018):◮ Based on the CRS concept, but uses supersingular curves andSIDH-like optimizations◮ Almost as fast as SIDH
◮ Subexponential security

SIDH vs. CSIDH

Isogenies

SIDH:◮ Faster (so far).

Definition◮ Superior (exponential) asymptotic security.

An isogeny is a morphism φ of algebraic varieties between twoelliptic curves, such that φ is a group homomorphism.

◮ Direct key validation is not possible.
◮ Admits active attacks — Galbraith, Petit, Shani, Ti (2016).

Concretely:◮ Requires extra steps, e.g. SIKE (https://sike.org/) for

φ: E → E′

CCA2 security or non-interactive key exchange (Urbanik &Jao, MathCrypt 2018).

φ(x, y ) = (φx (x, y ), φy (x, y ))f1 (x, y )φx (x, y ) =f2 (x, y )g1 (x, y )φy (x, y ) =g2 (x, y )CSIDH:◮ Slower (so far).
◮ Inferior (subexponential) asymptotic security.
◮ Supports direct key validation.
◮ No known active attacks.

(f1 , f2 , g1 , and g2 are all polynomials)◮ Naturally supports non-interactive key exchange.

Vélu’s formulas for constructing isogenies (1971)
Let G be any finite subgroup of an elliptic curve E . Let S be a setof representatives of (G \ {OE })/∼, where P ∼ Q ⇐⇒ P = ±Q.
Then there exists an isogeny φ : E → E ′ with ker φ = G , given byX  tQuQ+φx (x, y ) = x +x − xQ(x − xQ )2Q∈S"#X
gQx gQy
2yy − yQuQ
φy (x, y ) = y −+ tQ−(x − xQ )3(x − xQ )2 (x − xQ )2
Q∈S

Q = (xQ , yQ )gQx = 3xQ2 + a4

tQ =gQx
2gQx

uQ = (gQy )2Remarks:◮ The computational complexity of Vélu’s formulas is O(|G |).
◮This is exponentially slow when |G | is large.

◮ The isogeny φ and the codomain E ′ are unique up toisomorphism (a kernel determines an isogeny, up toisomorphism).
◮ Borrowing notation from group theory, we denote E ′ by E /G .

gQy = −2yQ
(Vélu’s formulaif Q = −Q
if Q 6= −Q

CRS (2006), CSIDH (2018)

SIDH (overview)

1. Public parameters: √Ordinary elliptic curve E withEnd(E ) = Od ⊂ Q( d), d < 0.

1. Public parameters: Supersingular elliptic curve E over Fp 2 .

2. Alice chooses an ideal a ⊂ Od and sends a ∗ E to Bob.

3. Bob chooses a kernel B ⊂ E (Fp 2 ) and sends E /B to Alice.

◮CSIDH: Supersingular E with EndFp (E ) = Od .

3. Bob chooses an ideal b ⊂ Od and sends b ∗ E to Alice.

4. The shared secret is (ab) ∗ E = a ∗ (b ∗ E ) = b ∗ (a ∗ E ).
Ea∗E

2. Alice chooses a kernel A ⊂ E (Fp 2 ) and sends E /A to Bob.
4. The shared secret is

E /hA, Bi = (E /A)/φA (B) = (E /B)/φB (A).
E

φAE /AφBb∗E(ab) ∗ E

The ∗ operator is the complex multiplication operator:a ∗ E = E / ker(a) = E /{P ∈ E : φ(P) = OE for all φ ∈ a}

Making it work

E /BE /hA, Bi

We will discuss security later: For ℓ-bit (quantum) security against
current attacks, use a prime of size 6ℓ bits (i.e. p ≈ 26ℓ ).

Computing isogenies with large kernels

EφAE /A◮ For simplicity, we use A ∼= Z/2e Z. Then the subgroup tower

φB

E /B

To control the cost of isogeny evaluation, we need to use kernels
ethat factor as abelian groups: A ∼= Z/p1e1 Z × · · · × Z/pgg Z, wherethe primes pi are small.

E /hA, Bi◮ In order to be secure, A and B must be of cryptographic size,

but Vélu’s formulas are impractical for such large kernels.
◮ In order to compute (E /A)/φA (B), Bob needs not only E /A

but also the image of B in E /A, i.e. φA (B). But B is known
only to Bob, and φA is known only to Alice.

0 ⊂ Z/2Z ⊂ Z/4Z ⊂ · · · ⊂ Z/2e Z
allows us to factor φA : E → E /A into the composition
E → E /(Z/2Z) → E /(Z/4Z) → · · · → E /(Z/2e Z)
Each isogeny in the composition is easy to compute.
◮ Similarly, Bob’s subgroup B is isomorphic to Z/3f Z.
(Bob cannot also use B ∼ Z/2e Z; if he did, then the shared=secret E /hA, Bi would be E /E [2e ] ∼= E .)

Computing E /hA, Bi

SIDH (detailed construction)

Alice knows φA and Bob knows B. How can Bob find φA (B)?
◮ Fix a generating set {P, Q} of (Z/3f Z)2 ⊂ E (Fp 2 ).

◮ Let mP + nQ be a generator of B. (Without loss ofPublic parameters:◮ Prime p = ℓeA ℓeB · f ± 1
A B◮ Supersingular elliptic curve E /Fp 2 of order (p ∓ 1)2◮ Z-basis {PA , QA } of E [ℓeA ] and {PB , QB } of E [ℓeB ]A
B

generality, we may take m = 1.)◮ Alice computes φA (P) and φA (Q) and sends them to Bob.
◮ Bob can now compute mφA (P) + nφA (Q) = φA (mP + nQ) toobtain φA (B).

Alice:◮ Choose RA = mA PA + nA QA of order ℓeAA
◮ Compute φA : E → E /hRA i◮ Send E /hRA i, φA (PB ), φA (QB ) to Bob

Therefore:◮ While Alice (for example) is computing φA , she also needs toBob:◮ Same as Alice, with A’s and B’s swapped

compute φA (P) and φA (Q).
◮ Alice needs to send φA (P) and φA (Q) to Bob as part of her

public key.

The shared secret is
E /hRA , RB i = (E /hRA i)/hmB φA (PB ) + nB φA (QB )i◮ We refer to φA (P) and φA (Q) as “auxiliary points.”= (E /hRB i)/hmA φB (PA ) + nA φB (QA )i

Security

Attack complexity

Hardness problem: Given E and E /A, find A.
Fastest known attack is meet-in-the-middle search (Galbraith,Hess, Smart 2002):
E11..
E1.
E12E

E2E3E21E22···

E31E32..

.

E /A

For a generic meet-in-the-middle attack, the values in the table
are provable lower bounds.

ClassicalQuantum

Alice√
2e
√
3 e
2Bob
√
3f
√
3 f
3

Quantum security level of SIDH is conjecturallymin(2e/3 , 3f /3 ) ≈ p 1/6

Key sizes
Public key size (bits):◮ 8 log2 p (naive)◮ 6 log2 p (Costello et al., Crypto 2016 — no key compression)◮ 7 log2 p (Costello et al., Eurocrypt 2017 — key compression)
2Example: For 128-bit quantum security, we have p ≈ 2768 and:◮ 8 log2 p bits = 6144 bits = 768 bytes◮ 6 log2 p bits = 4608 bits = 576 bytes (no key compression)◮ 7 log2 p bits = 2688 bits = 336 bytes (key compression)
2

Performance (Intel x86-64 Skylake):◮ Faz-Hernandez et al., https://ia.cr/2017/1015: 10ms
◮ Zanon et al., https://ia.cr/2017/1143: 20ms for keycompression
These numbers are likely improvable, since the p 1/6 estimate seems
to be too conservative (Adj et al., https://ia.cr/2018/313)

Summary
At first glance, the fact that [SIDH-based] SIKE is the only
isogeny-based KEM submitted to the NIST post-quantum process,competing with 58 others mostly based on codes, lattices, andpolynomial systems, might suggest that it is a strange outlier.
However, this uniqueness is not so much an indicator of lack ofsupport, so much as a sign of rare convergence and consensus in
the elliptic-curve cryptography community—convergence that didnot occur to the same extent in the communities working on otherpost-quantum paradigms. The fact that there was only one
isogeny-based submission reflects the general agreement that thiswas the right way to do isogeny-based key agreement at that point
in time. The more flexible CSIDH scheme was not developed until
later, when the NIST process was already underway, and so it was
not part of the conversation.
—Ben Smith, https://ia.cr/2018/882