The Computational Supersingular Isogeny Problem

Alfred Menezes
NutMiC 2019–1

Goals of this talk
1. Highlight some of the complications with assessing the“cost” of known attacks on computational problems.
2. Highlight some of the difficulties in comparing the costsof classical and quantum attacks.
3. Justify key size recommendations for SIDH (and SIKE).

–2

Assessing hardness of comp. problems
1. Assess the cost of known attacks.
There are many factors to consider:! Running time (number of arithmetic operations)! Parallelizability! Space requirements! Communication costs! Possibility of custom-designed machines! Quantum resources
2. Assess the possibility of new attacks in the future.

–3

RSA vs. ECC key sizes
Running time of NFS for factoring n:O(exp(1.923+o(1))(log n)

1/3 (log log n)2/3).

Cost assessment is complicated:! Communication costs for sieving (best done in cache/RAM)! Linear algebra does not parallelize well
! Possibility of specialized hardware (TWINKLE, TWIRL)
In contrast, the cost of Pollard’s rho attack on the ECDLP in E(Fp )is straightforward to assess:√! Expected running time is πn/2 (n = #E(Fp ) ≈ p)
! Perfectly parallelizable (van Oorschot-Wiener (VW))! Negligible storage! Negligible communication costs–4

RSA vs. ECC key sizes
After much debate, NIST issued the following key sizerecommendations in 2005 (SP 800-57) based on the running timeof the fastest known (classical) attacks:
Bits ofsecurityBlockcipherHashfunction

RSA
log2 nECC
log2 p80

SKIPJACK(SHA-1)

1024

160

112

Triple-DES

SHA-224

2048

224

128

AES-128

SHA-256

3072

256

192

AES-192

SHA-384

7680

384

256

AES-256

SHA-512

15360

512

TLS 1.2: 2048-bit RSA or 256-bit ECC for key agreement.

–5

Grover’s search and AES
Let F : {0, 1}ℓ → {0, 1} be a function such that:(i) F is efficiently computable; and(ii) F (x) = 1 for exactly p inputs x ∈ {0, 1}ℓ .
Grover’s Search (1996) is a quantum algorithm that finds anx ∈ {0, 1}ℓ with F (x) = 1 in 2ℓ/2 /p1/2 evaluations of F .
Key recovery: Consider AES with an ℓ-bit key. Suppose that wehave r known plaintext-ciphertext pairs (mi , ci ), where r is such thatthe expected number of false keys is very close to 0.
Define F : {0, 1}ℓ → {0, 1} by F (k) = 1 if AESk (mi ) = ci for all
1 ≤ i ≤ r; and F (k) = 0 otherwise.

Then Grover’s search (with p = 1) can find the secret key k in 2ℓ/2
operations.
Grover’s search is often used to justify moving from AES-128 to
AES-256.
–6

Quantum resource estimates (AES-128)
Grassl-Langenberg-Roetteler-Steinwandt (PQCrypto 2016)! # circuits: 1! # qubits: 2,953! # gates: 287! depth: 281
NIST: Quantum attacks are restricted to a fixed circuit depth, called
MAXDEPTH. Plausible values for MAXDEPTH:! 240 gates (approx. # of gates that presently envisioned
quantum computing architectures are expected to seriallyperform in a year).
! 264 gates (approx. # of gates that current classical computing
architectures can perform serially in a decade).
! 296 gates (approx. # of gates that atomic scale qubits withspeed of light propagation times could perform in a millennium).
The attack needs to be parallelized.
–7

Grover’s search doesn’t parallelize well
Optimal strategy (Zalka 1999): Divide the search space into
M subsets, each of size 2ℓ /M . Each of the M processors
performs Grover’s search on one subset.
√ℓ/2
Running time (per processor): 2 / M .
depth:# circuits:# qubits/circuit:# gates/circuit:
Total # gates:

281
1
2,953
287
287

240
282
2,953
246
2128

248
266
2,953
254
2120

264
234
2,953
270
2104

–8

Quantum error correction
Self-correcting quantum memory may not exist.
Actively-controlled quantum memories:! To protect a circuit of depth D andwidth W , a surface code requires
Θ(log2 (DW )) physical qubits per
logical qubit.
! The active error correction is appliedwith a classical processor in a regularcycle (e.g. once every 200ns).

arxiv.org/abs/1208.0928! The overall cost of surface code computation is Ω(log2 (DW ))RAM operations per logical qubit per layer of logical circuit
depth.
! Quantum error correction has large overhead.
! This explains why DW -cost is a realistic cost measure for aquantum algorithm.
–9

AES-128 security, revisited
Quantum
depth:
circuits:
qubits/circuit:gates/circuit:
Total gates:

#
240
282
2,953
246
2128

Classical
depth:
processors:#
235 AES ops
293

gates/processor: 250
Total gates:2143! The 293 classical processors used for error correction could be
repurposed to perform exhaustive key search in time 235 AES
operations.
! It isn’t clear then that Grover’s search is more effective thanclassical exhaustive search in breaking AES-128.
! Nevertheless, since AES-256 is only marginally slower than
AES-128, it is reasonable to move from AES-128 to AES-256.

– 10

NIST Category 1! Any attack must require computational resources comparable
to or greater than those required for key search on AES-128.
! ...with respect to all metrics that NIST deems to be potentiallyrelevant to practical security.
! NIST intends to consider a variety of possible metrics,
reflecting different predictions about the future development of
quantum and classical computing technology.
! Fixed circuit depth (MAXDEPTH)! Cost metric: Number of gates• 2143 classical gates• 2170 /MAXDEPTH quantum gates(2130 quantum gates if MAXDEPTH = 240 )! Category 3 (AES-192):• 2207 classical gates,

2233 /MAXDEPTH quantum gates– 11

Hash function collisions: Grover
Let H : {0, 1}∗ → {0, 1}ℓ be an ℓ-bit hash function.
! A collision is a pair (x, y) with H(x) = H(y) and x ̸= y.
! Define F : {0, 1}ℓ+c × {0, 1}ℓ+c → {0, 1} by!
0, if H(x) ̸= H(y),F (x, y) =1, if H(x) = H(y) and x ̸= y.
The expected number of collisions is ≈ 2ℓ+2c .

! Grover’s
search with M processors can find a collision in time√
2ℓ/2 / M .
! If M = 2ℓ/3 , the time is 2ℓ/3 .
! So, collisions for SHA-256 can be found in time 285.3 .

– 12Collision finding: Classical (VW)! The fastest generic classic finding algorithm for finding acollision for f : S → S (where #S = N ) is due to van
Oorschot-Wiener (VW).
! Let θ be the distinguishing probability for elements in S.

! Expected time ≈"πN/2 + 2.5
θ ,Space ≈ θ

"

πN/2.
– 13

Hash function collisions: VW
The VW algorithm for finding a collision for H : {0, 1}ℓ → {0, 1}ℓ :! Has" expected running time
π2ℓ /2 ≈ 2ℓ/2

! Is perfectly parallelizable! Has negligible storage! Has negligible communication
costs
With M = 2ℓ/3 processors, a collision can be found in time 2ℓ/6 .
(Grover’s search takes time 2ℓ/3 .)– 14

Hash function collisions: BHT
Brassard-Høyer-Tapp (BHT) (1998)
Fix x1 , x2 , . . . , xN ∈ {0, 1}ℓ+c . Define F : {0, 1}ℓ+c → {0, 1} by!
1, if H(y) = H(xi ) and y ̸= xi for some i,
F (y) =
0, otherwise.
Grover’s search (one processor) finds a collision in timeN + 2ℓ/2 /N 1/2 .
If N = 2ℓ/3 , this time is 2ℓ/3 .
Bernstein (2009) argued that BHT is inferior to VW since:! Memory access is expensive (on the order of N 1/2 ).
! Quantum memory is expensive.
– 15

NIST Category 2! Any attack must require computational resources comparable
to or greater than those required for collision search on
SHA-256.
! Cost metric: Number of gates• 2146 classical gates! Category 1:• 2143 classical gates, 2170 /MAXDEPTH quantum gates.

! “...NIST will assume that the five security strengths arecorrectly ordered in terms of practical security.”! Category 4 (SHA-384):• 2210 classical gates– 16

SIDH parameters
Unauthenticated key agreement scheme (Jao & De Feo, 2011).
! Let p = 2eA 3eB − 1 be a prime with 2eA ≈ 3eB ≈ p1/2 .

! Let E be a (supersingular) elliptic curve defined over Fp2 with
#E(Fp2 ) = (p + 1)2 .
! Then E(Fp2 ) ∼= Zp+1 ⊕ Zp+1 , whence E[2eA ], E[3eB ] ⊆ E(Fp2 ).
Let {PA , QA }, {PB , QB } be bases for E[2eA ], E[3eB ].

! Write (ℓ, e) to mean either (2, eA ) or (3, eB ). Similarly for {P, Q}.

! For each order-ℓe subgroup S of E[ℓe ], there exists a degree-ℓe(separable) isogeny φS : E → E/S over Fp2 with kernel S.
The isogeny is unique up to isomorphism and can be efficiently
computed.
! Hence, the number of degree-ℓe isogenies φ : E → E ′ is(ℓ + 1)ℓe−1 ≈ p1/2 .
! SIDH parameters: eA , eB , p, E, PA , QA , PB , QB .

– 17

SIDH
1. Alice selects a random order-2eA point RA = mA PA + nA QA
and computes the isogeny φA : E → E/A, where A = ⟨RA ⟩.
Alice transmits E/A, φA (PB ), φA (QB ) to Bob.
2. Bob similarly transmits E/B, φB (PA ), φB (QA ) to Alice.
3. Alice computes φB (RA ) = mA φB (PA ) + nA φB (QA ) and(E/B)/⟨φB (RA )⟩.
4. Similarly, Bob computes(E/A)/⟨φA (RB )⟩.
5. The compositions of isogenies
E → E/A → (E/A)/⟨φA (RB )⟩ andE → E/B → (E/B)/⟨φB (RA )⟩have kernel ⟨RA , RB ⟩.
6. The shared secret is the j-invariantof these curves.

– 18

CSSI
! Hardness of the Computational SuperSingular Isogeny
problem (CSSI) is necessary for the security of SIDH:! Given the SIDH parameters eA , eB , p, E, PA , QA , PB , QB , andE/A, φA (PB ), φA (QB ), compute a degree-2eA isogeny
φA : E → E/A.

! We will study a simplification of the problem that omits theauxiliary points φA (PB ) and φA (QB ):CSSI: Given the SIDH parameters eA , eB , p, E, PA , QA , PB ,QB , and E/A, compute a degree-2eA isogeny φA : E → E/A.
! CSSI was first formulated by Charles, Goren and Lauter in
2005.

– 19

Supersingular isogeny graphs! Let R denote the set of all j-invariants of supersingular elliptic
curves over Fp2 ; then #R ≈ p/12 ≈ ℓ2e .

! The supersingular isogeny graph Gℓ (Fp2 ) has vertex set R, andedges (j1 , j2 ) with multiplicity equal to the multiplicity of j2 as aroot of the modular polynomial Φℓ (j1 , Z) over Fp2 .
! Gℓ is (ℓ + 1)-regular.

! Pizer showed that Gℓ (Fp2 ) is a Ramanujan graph:• Optimal expander graph.
• The endpoint of a random walk approximates the uniform
distribution after O(log v) steps, where v ≈ ℓ2e .

! Let E1 = E, j1 = j(E1 ),E2 = E/A, j2 = j(E2 ).

! The CSSI problem is to find a path of length e from j1 to j2 inGℓ (Fp2 ).
– 20

CSSI attacks
The fastest CSSI attacks that were first identified were:! Classical: Meet-in-the-middle O(p1/4 ).
! Quantum: Tani’s algorithm O(p1/6 ).
Consequently, primes p of bitlength ≈ 768 were recommended toattain the 128-bit security level.
However, both attacks have significant storage requirements:
p1/4 and p1/6 , respectively.
Thus, a concrete cost analysis might justify using smaller p whilestill attaining the 128-bit security level.

– 21

Meet-in-the-middle (MITM) attack! Denote the number of order-ℓe/2 subgroups of E[ℓe ] byN ≈ p1/4 .

! For i = 1, 2, let Ri denote that set of j-invariants of elliptic
curves over Fp2 that are ℓe/2 -isogenous to Ei .
! Then one expects that #R1 ≈ #R2 ≈ N ≪ #R.
It is also reasonable to assume that #(R1 ∩ R2 ) = 1.

MITM
Time: 2N
Space: N– 22

VW golden collision finding
van Oorschot &Wiener, 1996
Adj et al., 2018
! Let I = {1, 2, . . . . , N } and S = {1, 2} × I.

! For i = 1, 2, let: Ai = all order-ℓe/2 subgroups of Ei [ℓe ].
hi : I → Ai bijections.
fi : Ai → Ri , fi (Ai ) = j(Ei /Ai ).

! Let g : R → S be a random function! Define f : S → S by f : (i, y) 0→ g(fi (hi (y)))! The expected number of (unordered) collisions for f is ≈ N .

−1! Suppose j(E1 /A1 ) = j(E2 /A2 ), y1 = h−1
(A
),
y
=
h
1
2
1
2 (A2 ).

! We seek the golden collision (1, y1 ), (2, y2 ).
– 23

VW golden collision finding
Main idea: Find many collisions, until the gold. collision is obtained.

Problem: The golden collision might be hard to find.

Solution: Change f periodically (by changing g).
– 24

Finding the golden collision! Storage: Space for w triples (xi,a , a, xi,0 ).
"! Set θ = α w/(2N ).

! Use each version of f to produce βw distinguished points.

! Store a distinguished point in a memory cell determined byhashing it.
! For α = 2.25, β = 10:• One expects 1.3w collisions per function version.
• One expects 1.1w distinct collisions per function version.
• The expected time to find the golden collision isN
2N√ ≈ N 3/2 /w1/2≈· 10w ·
1.1w
2.25 w≈ p3/8 /w1/2 .

! The algorithm parallelizes well.
– 25

MITM vs. VW! MITM (time-memory tradeoff):
Time: N 2 /w
Space: w! VW golden collision search:
Time: N 3/2 /w1/2
Space: w! Conclusion: VW is superior to
MITM for w < N .

– 26

Quantum attacks
CSSI can be viewed as an instance of the claw finding problem:
Consider f : X → Z, g : Y → Z with |X| = |Y | = N ≪ |Z|. Given
black-box access to f and g, find (x, y) ∈ X × Y with f (x) = g(y).

In CSSI: X = degree-ℓe/2 isogenies originating at E1 ,Y = degree-ℓe/2 isogenies originating at E2 ,Z = set of j-invariants of all supersingular elliptic curves,f, g record the j-invariants of the image curves,and there is exactly one claw.
– 27

Grover’s search! Define F : X × Y → Z by F (x, y) = 1 if f (x) = g(y), andF (x, y) = 0 otherwise.
√! Grover’s search can be used to find a claw in time N 2 ≈ p1/4 .
√
3/2
1/2
! VW: N /(M w ), Grover: N/ M .
! Example: Consider ℓ = 2, e = 216, N ≈ 2108 , w = 280 ,MAXDEPTH=264 .
• Then VW total run time is 2125.7 degree-2108 isogeny
computations.
• An optimistic estimate for the depth of a quantum circuit fora degree-2108 isogeny computation is 214 .
• One quantum circuit can perform 250 isogeny computations,
so M = 2116 circuits are required for Grover.
• So, NIST’s Category 1 requirements are met.
– 28

Tani’s algorithm! The vertices of the Johnson graph J(X, T ) are the T -subsetsof X, with two subsets begin adjacent iff their intersection has
size T − 1.
! Tani: Perform a quantum random walk (with uniform
probabilities) in G = J(X, T ) × J(Y, T ).
! The walk on G is a Markov process with uniform probabilities
and spectral gap δ ≈ T1 .
! The proportion of vertices that contain a claw is# $N −1% &2
T2
T −1
ϵ=
= 2.
$N %
N
T

– 29

Quantum random walkClassical:
Construct a random vertex. (S)Repeat O( 1ϵ ) times:
Repeat O( 1δ ) times:
Take one random step in G. (U)Check if the current vertex contains a claw.
$
$
%%
1 1
Cost: O S + ϵ δ U + C .

(C)Quantum (Magniez-Nayak-Roland-Santha):
Create a superposition of random vertices. (S)Repeat O( √1ϵ ) times:

Repeat O( √1δ ) times:
Take one “quantum” random step in G.
“Quantum” check for a claw. (C)'(('Cost: O S + √1ϵ √1δ U + C .

(U)

– 30

Tani: query optimal
Cost: O'S + √1ϵ'√1 U + C
δ

((

,

T2
ϵ = N2 ,δ ≈ T1 .

Jaques & Schanck (CRYPTO 2019)! Cost = O(T + TN
1/2 ).
! The cost is optimized when T ≈ N 2/3 , yielding a running time
≈ N 2/3 = p1/6 degree-ℓe/2 isogeny computations.

! A vertex has size 2T , so p1/6 classical processors are neededin the active error control model.
! These p1/6 processors (and p1/6 classical memory) can beused with VW golden collision search with running time
p3/8
1/8
p
.
=
1/6
1/12
p ·p

– 31

Tani: Non-asymptotic cost estimates
Jaques & Schanck (CRYPTO 2019)! The optimal T is chosen based on memory access costs andoracle costs.
! Tani suffers from the same parallelization issues as Grover(however, the naive parallelization strategy may not be optimal).
! Note that Tani’s algorithm with T = 1 is essentially the same as
Grover’s algorithm.
! Conclusion: Tani is costlier than VW• with MAXDEPTH = 264• DW-cost• G-cost– 32

Concrete parameters for SIDH
! 128-bit security-level (also: NIST Categories 1 and 2)• p = p434 = 2216 3137 − 1.
• VW: w = 280 , θ ≈ 1/213.6 , Time = 2125.7 (isog.).
Protocol
phase
Key
Gen.
Key
Gen.

Alice
Bob
Alice
Bob

CLN + enhancements
p751
p434
26.9
5.3
30.5
6.0
24.9
5.0
28.6
5.8

(Times are in 106 clock cycles on an Intel Core i7-6700)! 192-bit security level (also: NIST Categories 3 and 4)• p = p610 = 2305 3192 − 1.
• VW: w = 280 , θ ≈ 1/235.9 , Time = 2192.6 (isog.).

! p434 and p610 have been included in the Round 2 SIKE
submission to the NIST PQC competition.
– 33

Questions! Can the analysis of VW golden collision finding be made more
rigorous?
! Can the CSSI problem be formulated as one of finding a single
collision (not a golden collision)?
! Are the assumptions on classical resources and quantum
resources reasonable for making long-term key-size
recommendations?
! Can Tani’s algorithm be parallelized in a cost-effective way?

– 34

References
1. G. Adj et al.
“On the cost of computing isogenies between supersingularelliptic curves”
SAC 2018.
2. S. Jaques and J. Schanck“Quantum cryptanalysis in the RAM model: Claw-finding
attacks on SIKE”
CRYPTO 2019.
3. S. Jaques“Quantum cost models for cryptanalysis of isogenies”
Master’s thesis, http://hdl.handle.net/10012/14612– 35