Cryptography Reference
In-Depth Information
Table 1. Comparative costs for the multiplication and isogeny based algorithms using
projective coordinates. The entries must be multiplied by 2 (log 2 p ) 2 to obtain the
full cost.
A
2
3
5
11
19
log A 2
1
0.63
0.43
0.29
0.23
Isogeny
2 M + S
4 . 0 M +0 . 8 S
1 . 7 M +0 . 5 S
2 . 0 M +0 . 2 S
2 . 4 M +0 . 2 S
Multiplication
3 M +2 S
4 . 4 M +2 . 5 S
3 . 0 M +1 . 7 S
2 . 0 M +1 . 1 S
1 . 6 M +0 . 9 S
values h ( x 0 ) ,h ( x 0 ) ,h ( x 0 ) in order to apply Eq. (3). We let s =( A
1) / 2be
the degree of h . In ane coordinates, since h is monic, Horner's rule requires
(3 s
p 1 + p 1 )
we need I +8 M +2 S .For A = 3 the total count drops to I +6 M +2 S ,andfor
A = 5 it is I +8 M +2 S .
In projective coordinates, we first compute Z,...,Z s at a cost of ( s
6) M , except when s =1 , 2. Then, to compute β ( g ( x 0 ) /h ( x 0 )
1) M .
Then, if h = i h i X s−i Z i , we compute the monomials h i Z i using sM . Finally
we compute h, h ,h using three applications of Horner's rule, costing again
(3 s
=1 , 2. The final computation requires 11 M +3 S .For A =3
the total count is 10 M +2 S ,andfor A = 5 it is 14 M +3 S .
The difference between the ane and the projective formulas is I
6) M when s
2( s
1) M
S , so the choice between the two must be done according to the ratio
I/M .
Finally for A = 2, assuming a point of order 8 on the domain curve is known
(which will always be the case, except in the last two iterations), evaluating
the x part of Eq. 4 in projective coordinates and bringing the result back to a
Montgomery curve costs 2 M + S .
There are e A ( e A
1) isogeny evaluations in the algorithm, so, assuming
that N is the cost of doing one evaluation, the total cost is about
1
2 e 2 A N =
2 N (log 2 p ) 2 (log A 2) 2 . We summarize the main costs of the two algorithms in
Table 1.
1
5S cu y
5.1 Complexity Assumptions and Security Proofs
As before, let p be a prime of the form e A e B
·
f
±
1, and fix a supersingular curve
of E 0 [ e A ]and E 0 [ e B ]
respectively. In analogy with the case of isogenies over ordinary elliptic curves,
we define the following computational problems, adapted for the supersingular
case:
E 0 over
F p 2
together with bases
{
P A ,Q A }
and
{
P B ,Q B }
Problem 5.1 (Supersingular Isogeny (SSI) problem). Let φ A : E 0
E A be an
isogeny whose kernel is
[ m A ] P A +[ n A ] Q A
,where m A and n A are chosen at
/ e A
random from
and not both divisible by A .Given E A and the values
φ A ( P B ), φ A ( Q B ), find a generator R A of
Z
Z
[ m A ] P A +[ n A ] Q A
.
 
Search WWH ::




Custom Search