https://ia.cr/2018/932

Implementing supersingular isogeny cryptography
David Jao
Department of Combinatorics & Optimization
Centre for Applied Cryptographic Research

November 19, 2018

SIDH overview

Vélu’s formulas for constructing isogenies (1971)

1. Public parameters: Supersingular elliptic curve E over Fp 2 .
2. Alice chooses a kernel A ⊂ E (Fp 2 ) and sends E /A to Bob.
3. Bob chooses a kernel B ⊂ E (Fp 2 ) and sends E /B to Alice.
4. The shared secret is
E /hA, Bi = (E /A)/φA (B) = (E /B)/φB (A).
EφAQ∈SQ = (xQ , yQ )E /A

gQx = 3xQ2 + a4

E /hA, Bi

gQy = −2yQ
(gQxtQ =2gQx

φBE /BSet S = (A \ {∞})/± (i.e. “A excluding identity, modulo ±”).
Then φA = (φx , φy ) whereX  tQuQ+
φx (x, y ) = x +x − xQ
(x − xQ )2Q∈S"#X
gQx gQy
2yy − yQφy (x, y ) = y −+ tQ−uQ(x − xQ )3(x − xQ )2 (x − xQ )2The core operation in SIDH is to compute φA : E → E /A given A.

uQ = (gQy )2

if Q = −Q
if Q 6= −Q

SIDH strategies

Optimization #0: Use smaller parameters

In SIDH, we use isogenies of degree ℓe , where ℓ is a small prime.
Evaluate
Isogeny

Point multbyIsogeny
computation using
Velu’s formulas

Basic constraints:
We can compute
point multiplication
freely, at will.
However, in orderto evaluate an
isogeny φi , we needto compute thepoint [ℓe−i ]Ri first.

Optimization #1: SIMD instructions

Adj et al., https://ia.cr/2018/313:
We conclude that using SIDH parameters with p ≈ 2448
offers CSSI security of at least 128 bits against knownclassical and quantum attacks, and thus meet thesecurity requirements in NIST’s Category 2. . .
SIDH operations are about 4.8 times faster when p434 isused instead of p751 .

NEON-SIMD multiplication example: 256 × 32 bit

Koziel et al., https://ia.cr/2016/669:

A7

Quad Register 1
A6A5A4A3

Quad Register 0A2A1A0◮ SIMD (Single Instruction Multiple Data) allows multiple

operations to be performed in a single cycle.
◮ The catch: one operand must be constant◮

Transpose

A4 x B0

We can parallelize a · b and a · c, but not a · b and c · d◮ Since our numbers are so large (512 bits and up), we can takeadvantage of SIMD to parallelize just a single multiplication.
Our approach (on 32-bit ARM):

A0 x B0

Carry Chains

Multiplication
and Carry×

Step 1:A5 x B0

A1 x B0

Step 2:A6 x B0

A2 x B0

Step 3:A7 x B0

A3 x B0◮ Use SIMD to multiply 256-bit blocks using parallel operations◮ Use Karatsuba multiplication to multiply larger numbers (e.g.

1024-bit numbers) using smaller 256-bit blocks
Step 4:A4 x B0

B0

B0

Optimization #2: parallelized isogeny evaluations

Optimization #3: FPGA implementations

Aaron Hutchinson and Koray Karabina, Constructing canonicalstrategies for parallel implementation of isogeny based
cryptography, Indocrypt 2018
◮ B. Koziel, R. Azarderakhsh, M. M. Kermani, Fast hardware

architectures for Supersingular Isogeny Diffie-Hellman key
exchange on FPGA, Indocrypt 2016.
◮ B. Koziel, R. Azarderakhsh, M. M. Kermani, D. Jao,

Post-quantum cryptography on FPGA based on isogenies onelliptic curves, IEEE TCAS (2017).
◮ B. Koziel, R. Azarderakhsh, M. M. Kermani, A

high-performance and scalable hardware architecture forisogeny-based cryptography, IEEE TC 67 (11), 2018.

Parallelism in FPGA implementations◮ Fp 2 multiplication → 3 Fp multiplications◮ Perform isogeny evaluations in parallel (as in Hutchinson andKarabina, Indocrypt 2018)

Results

Optimization #4: ECC hardware acceleration

J. D. Calhoun, “Optimization of supersingular isogeny
cryptography for deeply embedded systems,”
https://digitalrepository.unm.edu/ece_etds/420◮ 6.3-7.5x speed improvement using instruction set extensions◮ 4x more area, 10x less speed, 6x smaller keys (vs. NewHope)◮ Finite field exponentiation (needed for constant-time fieldinversion) remains a bottleneck, as it is difficult to parallelize

for finite field arithmetic◮ (Further) 6.0-6.1x speed improvement using an existing finite

field arithmetic coprocessor design with a 32-bit datapath◮ (Further) 2.6-2.9x speed improvement using a slightly

modified finite field coprocessor with a 64-bit datapath

Target platforms

Baseline platform: Targhetta et al., “The design space of ultra-low
energy asymmetric cryptography.”
http://ieeexplore.ieee.org/document/6844461/
1. “Pete” — 5-stage pipelined RISC (MIPS) processor, 256kB
program ROM, 16kB RAM
2. “PeteISE ” — Pete with instruction set extensions for prime
fields
3. “PM32” — Pete with “Monte” GF(p) arithmetic accelerator
4. “PM64” — Modified Monte accelerator with 64-bit word size
All (except PM64) were originally designed for ECC (not SIDH).

ResultsWork

Platform[1]

Cortex-M4
PetePeteISEPM32PM64x64
Virtex-7[2][3][4]Key gen.
Alice Bob1025 1148
4259 4814
617
679
99
113
33
3727
31
1.61
1.74

Secr. gen.
Alice Bob96711124012 4197
494556
85
10128
34
25
29
1.44
1.59

Table: Clock cycle count [×106 ] for SIDH on p751
1. Koppermann et al., https://ia.cr/2018/932
2. Calhoun, https://digitalrepository.unm.edu/ece_etds/420
3. Faz-Hernández et al., https://ia.cr/2017/1015
4. Koziel et al., IEEE TC 67 (11), 2018.

Size comparison
[1]
[2]
[3]

NewHope
PeteISE
PM32
PM64
SIDHConclusions
Artix-7

Bytes
2178

Zynq 7Z020

378

Virtex-7

378

FF
4452
2944
3426
3700
24908

LUT
5142
4658
5403
6074
18820

DSP
215
17192

BRAM
433.5
44.5
47.5
43.5

◮ SIDH with NewHope-like hardware acceleration resources isclock-for-clock comparable to SIDH on x64 in speed.
FF — flip flops
LUT — lookup tables
DSP — digital signal processing slices
BRAM — Block RAM
1. Oder and Güneysu, LatinCrypt 2017
2. Calhoun, https://digitalrepository.unm.edu/ece_etds/420
3. Koziel et al., IEEE TC 67 (11), 2018.
Note: The design in [2] is software-configurable for any field size.

◮ SIDH on IoT likely requires hardware acceleration.
◮ Taking into account cost of communication, SIDH may be ofinterest to IoT implementors.
◮ Future work: Authenticated key exchange, signatures, CSIDH.