Verifiable Delay Functions and More from Isogenies and Pairings
Luca De Feo
based on joint work with J. Burdges, S. Masson, C. Petit, A. Sanso
IBM Research Zürich
December 4, 2019, ECC, Bochum
Slides online at https://defeo.lu/docet

Distributed lottery
Participants A, B, ..., Z want to agree on a random winning ticket.

Flawed protocol
Each participant x broadcasts a random string sx ;()

Winning ticket is H sA ; : : : ; sZ .

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

2 / 28

Distributed lottery
Participants A, B, ..., Z want to agree on a random winning ticket.

Flawed protocol
Each participant x broadcasts a random string sx ;()

Winning ticket is H sA ; : : : ; sZ .

Cheating participant Z waits to see all other strings, then brute-forces sZ to win lottery.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

2 / 28

Distributed lottery
Participants A, B, ..., Z want to agree on a random winning ticket.

Flawed protocol
Each participant x broadcasts a random string sx ;()

Winning ticket is H sA ; : : : ; sZ .

Cheating participant Z waits to see all other strings, then brute-forces sZ to win lottery.

Fixes
Make the hash function sloooooooooooooooooooooooooooow;
I e.g., participants have 10 minutes to submit sx ,I outcome will be known after 20 minutes.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

2 / 28

Distributed lottery
Participants A, B, ..., Z want to agree on a random winning ticket.

Flawed protocol
Each participant x broadcasts a random string sx ;()

Winning ticket is H sA ; : : : ; sZ .

Cheating participant Z waits to see all other strings, then brute-forces sZ to win lottery.

Fixes
Make the hash function sloooooooooooooooooooooooooooow;
I e.g., participants have 10 minutes to submit sx ,I outcome will be known after 20 minutes.
Make it possible to verify w

Luca De Feo (IBM Research Zürich)= H (sA; : : : ; sZ ) fast.

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

2 / 28

Verifiable Delay Functions (Boneh, Bonneau, Bünz, Fisch 2018)
Wanted:()Function (family) f X ! Y s.t.:
Evaluating f x takes long time:
I uniformly long time,
I on almost all random inputs x ,I even after having seen many values of f (x 0 ),I even given massive number of processors;= ()Verifying y f x is efficient:
I ideally, exponential separation between evaluation and verification.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

3 / 28

Verifiable Delay Functions (Boneh, Bonneau, Bünz, Fisch 2018)
Wanted:()Function (family) f X ! Y s.t.:
Evaluating f x takes long time:
I uniformly long time,
I on almost all random inputs x ,I even after having seen many values of f (x 0 ),I even given massive number of processors;= ()Verifying y f x is efficient:
I ideally, exponential separation between evaluation and verification.
Exercise

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

3 / 28

Verifiable Delay Functions (Boneh, Bonneau, Bünz, Fisch 2018)
Wanted:()Function (family) f X ! Y s.t.:
Evaluating f x takes long time:
I uniformly long time,
I on almost all random inputs x ,I even after having seen many values of f (x 0 ),I even given massive number of processors;= ()Verifying y f x is efficient:
I ideally, exponential separation between evaluation and verification.
ExerciseThink of a function you like with these properties

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

3 / 28

Verifiable Delay Functions (Boneh, Bonneau, Bünz, Fisch 2018)
Wanted:()Function (family) f X ! Y s.t.:
Evaluating f x takes long time:
I uniformly long time,
I on almost all random inputs x ,I even after having seen many values of f (x 0 ),I even given massive number of processors;= ()Verifying y f x is efficient:
I ideally, exponential separation between evaluation and verification.
ExerciseThink of a function you like with these properties
Got it?

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

3 / 28

Verifiable Delay Functions (Boneh, Bonneau, Bünz, Fisch 2018)
Wanted:()Function (family) f X ! Y s.t.:
Evaluating f x takes long time:
I uniformly long time,
I on almost all random inputs x ,I even after having seen many values of f (x 0 ),I even given massive number of processors;= ()Verifying y f x is efficient:
I ideally, exponential separation between evaluation and verification.
ExerciseThink of a function you like with these properties
Got it?
You’re probably wrong!
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

3 / 28Sequentiality

Ideal functionality:y= f (x ) = |H (H (  {z (H (x ))))}
T timesSequential assuming hash output “unpredictability”,
but how do you verify? (you’re not allowed to say “SNARKs”)

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

4 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup
A group of unknown order, e.g.:=

Z=N Z with N pq an RSA modulus, p ; q unknown(e.g., generated by some trusted authority),x

Class group of imaginary quadratic order.

Evaluation
With delay parameter T :
f

:G !G

x 7 ! x2

T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup
A group of unknown order, e.g.:=

Z=N Z with N pq an RSA modulus, p ; q unknown(e.g., generated by some trusted authority),x2
xClass group of imaginary quadratic order.

Evaluation
With delay parameter T :
f

:G !G

x 7 ! x2

T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup
A group of unknown order, e.g.:

Z=N Z with N = pq an RSA modulus, p ; q unknown

x4
x2
x

(e.g., generated by some trusted authority),
Class group of imaginary quadratic order.

Evaluation
With delay parameter T :
f

:G !G

x 7 ! x2

T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup
A group of unknown order, e.g.:

Z=N Z with N = pq an RSA modulus, p ; q unknown

x4
x2
x

(e.g., generated by some trusted authority),
Class group of imaginary quadratic order.

Evaluation
With delay parameter T :f:G !Gx 7 !xT

x2

2T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup
A group of unknown order, e.g.:

Z=N Z with N = pq an RSA modulus, p ; q unknown

x4
x2
x

(e.g., generated by some trusted authority),
Class group of imaginary quadratic order.

Evaluation
2T

With delay parameter T :f:G !Gx 7 !xmod '(N )

T

x2

2T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup

Verification

A group of unknown order, e.g.:

Interactive proofs that y f x ,(non interactivity via Fiat-Shamir):=

Z=N Z with N pq an RSA modulus, p ; q unknown(e.g., generated by some trusted authority),= ()Class group of imaginary quadratic order.

Evaluation
With delay parameter T :
f

:G !G

x 7 ! x2

T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup

Verification

A group of unknown order, e.g.:

Interactive proofs that y f x ,(non interactivity via Fiat-Shamir):=

Z=N Z with N pq an RSA modulus, p ; q unknown(e.g., generated by some trusted authority),
Class group of imaginary quadratic order.

Proof size O(log(T )),Hard to find (non-trivial)
w 2 G of known order) Proof is sound.

Evaluation
With delay parameter T :fPietrzak ’19:

= ()

:G !G

x 7 ! x2

T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

5 / 28VDFs from groups of unknown order (inspired by Rivest–Shamir–Wagner time-lock puzzle)
Setup

Verification

A group of unknown order, e.g.:

Interactive proofs that y f x ,(non interactivity via Fiat-Shamir):=

Z=N Z with N pq an RSA modulus, p ; q unknown(e.g., generated by some trusted authority),
Class group of imaginary quadratic order.

With delay parameter T ::G !GWesolowski ’19:

x 7 ! x2(log(T )),()Proof size O 1 ,T

Conjecturally, fastest algorithm is repeated squaring.
Luca De Feo (IBM Research Zürich)

Proof size O

Hard to find (non-trivial)
w 2 G of known order) Proof is sound.

EvaluationfPietrzak ’19:

= ()VDFs from Isogenies and Pairings

More emphad hoc security
assumption.
https://defeo.lu/docet

ECC 2019

5 / 28Where have I seen this before?
5

x

26

x2

4

x2

3

x2

2

x2

7
x2

x

28

x

29

1

x2

0

x2

16

x

x2

210
11
x2

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

x2
x2

12

15

14

13

x2

x2

https://defeo.lu/docet

ECC 2019

6 / 28Where have I seen this before?
Isogeny cycles

E5
E6

Vertices are elliptic curves:
I Ordinary,
I Supersingular =Fp .

E4

E3
E2

E7

E1
E8

Edges are horizontal isogenies.

E0
E9
E16
E10
E11

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

E15
E12 E13 E14https://defeo.lu/docet

ECC 2019

6 / 28Where have I seen this before?
Isogeny cycles

E5
E6

Vertices are elliptic curves:
I Ordinary,
I Supersingular =Fp .

Luca De Feo (IBM Research Zürich)

E2
E1

End(E ) acts upon the cycle:
$
$
$
$
$

E3

E7

Edges are horizontal isogenies.
The class group of
isogeny
endomorphism
degreedual
cycle size

E4

ideal
principal ideal
norm
complex conjugate
order of the ideal

VDFs from Isogenies and Pairings

E8
E0
E9
E16
E10
E11

E15
E12 E13 E14https://defeo.lu/docet

ECC 2019

6 / 28Where have I seen this before?
Isogeny cycles

E5

Vertices are elliptic curves:
I Ordinary,
Couveignes–Rostovtsev–Stolbunov
I Supersingular =Fp .
CSIDH
Edges are horizontal isogenies.
The class group of
isogeny
endomorphism
degreedual
cycle size

End(E ) acts upon the cycle:

Luca De Feo (IBM Research Zürich)

$
$
$
$
$

ideal
principal ideal
norm
complex conjugate
order of the ideal

VDFs from Isogenies and Pairings

E6

E4

E3
E2

E7

E1
E8
E0
E9
E16
E10
E11

E15
E12 E13 E14https://defeo.lu/docet

ECC 2019

6 / 28

Slooooooooooooooooooooooooooooooooooooooooooow isogenies
Setup
With delay parameter T :A laaaaaaaaaaaaaaaaaaaaaaaarge isogeny cycle,
E2
E1
E0

ET

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

7 / 28

Slooooooooooooooooooooooooooooooooooooooooooow isogenies
Setup
With delay parameter T :A laaaaaaaaaaaaaaaaaaaaaaaarge isogeny cycle,
E2
E1
E0

A starting curve E0 ,:An isogeny  E0 ! ET of degree 2T .

ET

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

7 / 28

Slooooooooooooooooooooooooooooooooooooooooooow isogenies
Setup
With delay parameter T :A laaaaaaaaaaaaaaaaaaaaaaaarge isogeny cycle,
E2
E1
E0

A starting curve E0 ,:An isogeny  E0 ! ET of degree 2T .

Evaluation

 is the VDF:
 : E0 (Fp ) ! ET (Fp )P 7 ! (P )ET

Conjecturally, no faster way than composing degree 2
isogenies.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

7 / 28

Slooooooooooooooooooooooooooooooooooooooooooow isogenies
Setup
With delay parameter T :A laaaaaaaaaaaaaaaaaaaaaaaarge isogeny cycle,
E2
E1
E0

A starting curve E0 ,:An isogeny  E0 ! ET of degree 2T .

How to verify?

Evaluation

 is the VDF:
 : E0 (Fp ) ! ET (Fp )P 7 ! (P )ET

Conjecturally, no faster way than composing degree 2
isogenies.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

7 / 28

Isogeny <3 Pairing

Theorem^::

Let  E ! E 0 be an isogeny and  E 0 ! E its dual. Let eN be the Weil pairing of E and eN0
that of E 0 . TheneN P ;  Q
eN0  P ; Q ;

[ ]

[ ]

for any P 2 E N and Q 2 E 0 N .

( ^( )) = ( ( ) )Corollary( ( ) ( )) = eN (P ; Q )deg :

eN0  P ;  Q

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

8 / 28

Refresher: Boneh–Lynn–Shacham (BLS) signatures
Setup:# ( ): [ ] [ ][ ]=:Elliptic curve E =Fp , s.t N j E Fp for a large prime N ,(Weil) pairing eN E N  E N ! Fp k for some small embedding degree k ,A decomposition E N
X1  X2 , with X1 hP i.
A hash function H f0; 1g ! X2 .

Private key: s 2 Z=N Z.

=

Public key: sP .

( )Verifiy: eN (P ; sH (m )) = eN (sP ; H (m )).
Sign: m 7! sH m .

X1  X2[s ]1

X1  X2

1  [s ]eN

X1  X2
Luca De Feo (IBM Research Zürich)eN

VDFs from Isogenies and Pairings

Fp khttps://defeo.lu/docet

ECC 2019

9 / 28

US patent 8,250,367 (Broker, Charles and Lauter 2012)
Signatures from isogenies + pairings[ ] : E ! E with an isogeny  : E ! E 0;

Replace the secret s

Define decompositions[ ] = X1  X2;
s.t. (X1 ) = Y1 and (X2 ) = Y2 ;Define a hash function H : f0; 1g ! Y2 .

[ ] = Y1  Y2;

E0 N

EN

X1  Y21

Y1  Y2
eN0

1  ^

X1  X2
Luca De Feo (IBM Research Zürich)

eN

Fp k

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

10 / 28

Isogeny VDF (principle)
Setup
Pairing friendly curve E ,:Isogeny  E ! E 0 of degree `T ,( ) 2 Y1.

Point P 2 X1 , image  P

Evaluation

Input: random Q 2 Y2 ,^( ) 2 X2.

Output:  Q

VerificationeN (P ; ^(Q ))Luca De Feo (IBM Research Zürich)?

=eN0 ((P ); Q ):VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

11 / 28

Instantiation over Fp
The curves)

Need a large enough isogeny class;
Need pairing friendliness;) supersingular curves.

Technicalities

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

12 / 28

Instantiation over Fp
The curves)

Need a large enough isogeny class;
Need pairing friendliness;) supersingular curves.

Technicalities+ =Choose p 1 N  f ,I for degree ` = 2 also need 8jf ;Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

12 / 28

Instantiation over Fp
The curves)

Need a large enough isogeny class;
Need pairing friendliness;) supersingular curves.

Technicalities+ =Choose p 1 N  f ,I for degree ` = 2 also need 8jf ;Choose E =Fp on an `-isogeny cycle
I If ` = 2 ) choose
 E with maximal endomorphism ring;
I Otherwise `p = 1.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

12 / 28

Instantiation over Fp
The curves)

Need a large enough isogeny class;
Need pairing friendliness;) supersingular curves.

Technicalities+ =Choose p 1 N  f ,I for degree ` = 2 also need 8jf ;Choose E =Fp on an `-isogeny cycle
I If ` = 2 ) choose
 E with maximal endomorphism ring;
I Otherwise `p = 1.
There are only two `T -isogenies from E , choose any.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

12 / 28

Instantiation over Fp
The curves)

Need a large enough isogeny class;
Need pairing friendliness;) supersingular curves.

Technicalities+ =Choose p 1 N  f ,I for degree ` = 2 also need 8jf ;Choose E =Fp on an `-isogeny cycle
I If ` = 2 ) choose
 E with maximal endomorphism ring;
I Otherwise `p = 1.

There are only two `T -isogenies from E , choose any.
Set X2 E N \ E Fp and X1 as the other eigenspace of Frobenius:
I Short notation:
X1 = E [(N ;  + 1)];X2 = E [(N ;  1)]:
I Similarly:
Y1 = E 0 [(N ;  + 1)];Y2 = E 0 [(N ;  1)]:

= [ ]Luca De Feo (IBM Research Zürich)( )VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

12 / 28

Instantiation over Fp 2
There’s nothing special with isogeny cycles
May as well use isogeny walks in the full supersingular graph(like Charles–Goren–Lauter, SIDH, . . . )[ ] = X1  X2

But we still need a canonical decomposition E N) start from E =Fp .

Technicalities

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

13 / 28

Instantiation over Fp 2
There’s nothing special with isogeny cycles
May as well use isogeny walks in the full supersingular graph(like Charles–Goren–Lauter, SIDH, . . . )[ ] = X1  X2

But we still need a canonical decomposition E N) start from E =Fp .

Technicalitiesp+ 1 = N  f , no conditions on (p ; `);Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

13 / 28

Instantiation over Fp 2
There’s nothing special with isogeny cycles
May as well use isogeny walks in the full supersingular graph(like Charles–Goren–Lauter, SIDH, . . . )[ ] = X1  X2

But we still need a canonical decomposition E N) start from E =Fp .

Technicalitiesp+ 1 = N  f , no conditions on (p ; `);There are exponentially many `T -isogenies, choose any (pseudorandomly);

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

13 / 28

Instantiation over Fp 2
There’s nothing special with isogeny cycles
May as well use isogeny walks in the full supersingular graph(like Charles–Goren–Lauter, SIDH, . . . )[ ] = X1  X2

But we still need a canonical decomposition E N) start from E =Fp .

Technicalitiesp+ 1 = N  f , no conditions on (p ; `);There are exponentially many `T -isogenies, choose any (pseudorandomly);
Impossible to hash into Y2  X2 :I Domain of VDF is all of E 0 [N ];I To make the protocol sound we compose ^ with the trace of E =Fp 2 .

= ( )Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

13 / 28

Comparison

proof size
aggregatablewatermarkable
perfect soundness
long setup
trusted setup
best attack
quantum annoying

Wesolowski
RSA
class group
O 1
O 1
yes
yes
yes
yes
no
no
no
no
yes
no
LN 1=3
LN 1=2no(yes)

Luca De Feo (IBM Research Zürich)

()

()

( )

( )

Pietrzak
RSA
class group
O
T
O
T
yes
yes
yes
yes
no
no
no
no
yes
no
LN 1=3
LN 1= 2no(yes)(log( ))

(log( ))( )( )VDFs from Isogenies and Pairings

Fp

Ours

—
—
(yes)
yes
yes
yes
Lp 1=3no( )https://defeo.lu/docet

Fp 2

—
—
(yes)
yes
yes
yes
Lp 1=3yes( )ECC 2019

14 / 28

Implementation
PoC implementation in SageMath (re-implemented Montgomery isogenies);p+ 1 = N  21244  63, enables time/memory compromise in evaluation.
Protocol

Fp graph
Fp 2 graph

Step
Setup
Evaluation
Verification
Setup
Evaluation
Verification

Parameters size (T  216 )238 kb——491 kb
—
—

Time
—
—
0:3 s
—
—
4s

Throughput
0.75 isog/ms
0.75 isog/ms—
0.35 isog/ms
0.23 isog/ms—

Table: Benchmarks (Intel Core i7-8700 @3.20GHz) at 128 bits of security (aggressively optimizing for size).

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

15 / 28

Security

Attacks
Security goal:

Given the isogeny  E ! E , the adversary is allowedpoly(T ) precomputation.

Later, it is given a random Q 2 Y2 :its probability of computing  Q in less than “T steps” must be negligible.

^( )Attack avenues:
1

Speed-up/parallelize isogeny computation;

2

Solve the pairing equation;

3

Find isogeny shortcuts.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

17 / 28

Attacking the computation?
x 7 ! x2

RSA:

x 7 !xIsogenies:( 1; : : : ;e.g.,

T depend on the chosen isogeny)

log2 N 2048;log2 p

x i
x

1

mod N

mod p

i

 1500.

No speedup? Even with unlimited parallelism? Really?
See Bernstein, Sorenson. Modular exponentiation via the explicit Chinese remainder
theorem.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

18 / 28

Attacking the pairing

A pairing inversion problem:e (P ; ???) = e ((P ); Q )Quantum: Broken by Shor’s algorithm;
Classical: Subexponential Lp (1=3) attack.
Note: Solving the equation gives the true value of ^(Q ) (perfect soundness)

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

19 / 28

Computing shortcuts

E=

Isogeny degree `T $ walk length
I e.g., for delay  1 hour, T  220 ;Luca De Feo (IBM Research Zürich)= T;

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

20 / 28

Computing shortcuts

E=

Isogeny degree `T $ walk length
I e.g., for delay  1 hour, T  220 ;I Typically much larger than graph

= T;
E0

diameter (= O (log p )  210 ).
I (which isogeny graph is meant depends
on the variant)Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

20 / 28

Computing shortcuts

E=

Isogeny degree `T $ walk length
I e.g., for delay  1 hour, T  220 ;I Typically much larger than graph

= T;
E0

diameter (= O (log p )  210 ).
I (which isogeny graph is meant depends
on the variant)Goal: find a shortcut, i.e., a shorter walk.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

20 / 28

End(E ) gives shortcuts

Fp caseEndF (E )  Q(p p ):the class group Cl( 4p ) acts on the setpof supersingular curves =Fp ;Structure ofmCl( 4p )relations between ideal classesmshortcuts in the graph.
I see CSI-FiSh signatures(Beullens–Kleinjung–Vercauteren);I akin to attack on class group VDF.
Some additional work to findendomorphism ! such that! Q  Q .

^( ) = ^( )Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

21 / 28

End(E ) gives shortcuts

Fp caseEnd (E )  Q(p p ):Fp

Cl(General case (both Fp and Fp 2 ))the class group
4p acts on the setof supersingular curves =Fp ;Structure ofmCl( 4p )End(E ) isomorphic to anorder in a quaternion algebra;
Structure ofmEnd(E ) (or End(E 0))

shortcuts (through Fp 2 ).
I Related to attacks on therelations between ideal classesmCharles–Goren–Lauter hash function.

Additional work to find ! 2

shortcuts in the graph.
I see CSI-FiSh signatures

End(E ).

(Beullens–Kleinjung–Vercauteren);I akin to attack on class group VDF.
Some additional work to findendomorphism ! such that! Q  Q .

^( ) = ^( )Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

21 / 28

End(E ) gives shortcuts

Fp caseEnd (E )  Q(p p ):Fp

Cl(General case (both Fp and Fp 2 ))the class group
4p acts on the setof supersingular curves =Fp ;Structure ofmCl( 4p )End(E ) isomorphic to anorder in a quaternion algebra;
Structure ofmshortcuts (through Fp 2 ).
I Related to attacks on therelations between ideal classesmCharles–Goren–Lauter hash function.

Additional work to find ! 2

shortcuts in the graph.
I see CSI-FiSh signatures^( ) = ^( )Luca De Feo (IBM Research Zürich)End(E ).

WE HAVE A PROBLEM!

(Beullens–Kleinjung–Vercauteren);I akin to attack on class group VDF.
Some additional work to findendomorphism ! such that! Q  Q .

End(E ) (or End(E 0))

No known way to construct supersingularcurves without knowledge ofE .

End( )

Only known fix: Trusted setup.
VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

21 / 28

Trusted setupy2= x3 + x
Start from a well known supersingularcurve,

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

22 / 28

Trusted setupy2= x3 + x
Start from a well known supersingularcurve,
E

Luca De Feo (IBM Research Zürich)

Do a random walk,

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

22 / 28

Trusted setupy2= x3 + x
Start from a well known supersingularcurve,
E

Luca De Feo (IBM Research Zürich)

Do a random walk,
Forget it.

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

22 / 28

Trusted setupy2= x3 + x
Start from a well known supersingularcurve,Do a random walk,E

Forget it.
Classical

Fp graph Fp 2 graph
Computing shortcuts
Pairing inversion

( )
( )

Lp 1=2
Lp 1=3p
O ( p)

Quantum

Fp graph

Fp 2 graphpolylog(p ) O ( pp )Lp (1=3) polylog(p ) polylog(p )4Quantum annoyance:
Computing shortcuts in Fp 2 is quantumly hard;
Pairing inversion attacks must be run online, useless if Shor’s algorithm takes much longer
than target delay.
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

22 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),E1

Luca De Feo (IBM Research Zürich)y2= x3 + x

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

1
E1

Luca De Feo (IBM Research Zürich)y2= x3 + x

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

1
E1

y2

= x3 + x

Repeat.

E2

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

2

1
E1

y2

= x3 + x

Repeat.

E2

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

2

1
E1

y2

= x3 + x

Repeat.

E2

E3

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

2

1
E1

y2

= x3 + x

Repeat.

E2

3
E3

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Distributed trusted setups
Mitigate trusted setup woes by distributing trust:Participant i performs a random walk (in Fp ),Publishes a proof of isogeny knowledge,

2

1
E1

E2

y2

= x3 + x

Repeat.
Proof options:
Generic ZK proofs,
Isogeny ZK proofs (SeaSign),

3Pairing proofs (not ZK!):= H(Ei ; Ei +1);ei (P ; ^i (Q )) = ei +1 (i (P ); Q ):
P; Q

E3

Properties: asynchronous, robust against n 1
coalition, verification scales linearly, updatable, . . .
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

23 / 28

Beyond VDFs

Watermarking
Goal: reward evaluator for its effort.
Watermarking: issue proof of evaluation tied to evaluator identity

^1

^2
E

E0

Emid

^ = ^2  ^1Secret key: scalar s 2 Z=N Z,( ) 2 E 0 (+ proof of exponent knowledge),
Proof of work: s ^1 (Q ) 2 Emid ,Verification: emid (2 (P ); s ^1 (Q )) = e 0 (s (P ); Q ).
Public key: s  P

Properties: blind (can be checked before the computation is complete).
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

25 / 28

Encryption to the future (time-locks)
Goal: encrypt now, decryption only possible after delay.
Applications: auctions, voting, . . .
Idea: start from Boneh–Franklin IBE, just add isogeniesTM .
Biddersamples random s 2 Z=N Z
computes k e  P ; Q s
encrypts offer ok Enck osends ok ; sP

= (( ) )= ()()

Auctioneer
Publishes auction key Q H sid
starts evaluating  Q

= ( )
^( )

!

..
.

= (

^( ))

computes k e sP ;  Q
decrypts ok
Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

26 / 28

Open questions
Understand the impact of large memory requirements in evaluation; is a time/memory
trade-off reasonable?

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

27 / 28

Open questions
Understand the impact of large memory requirements in evaluation; is a time/memory
trade-off reasonable?
Remove trusted setup:
I Hash into the supersingular set, or
I Construct ordinary pairing friendly curves with large discriminant.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

27 / 28

Open questions
Understand the impact of large memory requirements in evaluation; is a time/memory
trade-off reasonable?
Remove trusted setup:
I Hash into the supersingular set, or
I Construct ordinary pairing friendly curves with large discriminant.
Explore more advanced pairing+delay constructions.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

27 / 28

Open questions
Understand the impact of large memory requirements in evaluation; is a time/memory
trade-off reasonable?
Remove trusted setup:
I Hash into the supersingular set, or
I Construct ordinary pairing friendly curves with large discriminant.
Explore more advanced pairing+delay constructions.
Spend millions on dedicated hardware for 2-isogenies.

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

27 / 28

Open questions
Understand the impact of large memory requirements in evaluation; is a time/memory
trade-off reasonable?
Remove trusted setup:
I Hash into the supersingular set, or
I Construct ordinary pairing friendly curves with large discriminant.
Explore more advanced pairing+delay constructions.
Spend millions on dedicated hardware for 2-isogenies.

Just Add IsogeniesTM !

Luca De Feo (IBM Research Zürich)

VDFs from Isogenies and Pairings

https://defeo.lu/docet

ECC 2019

27 / 28

Thank you
https://defeo.lu/@luca_defeo