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
.