Cryptography Reference
In-Depth Information
in its derivative to evaluate the isogeny, this only takes a constant number of
multiplications (plus one inversion in ane coordinates). Finally, the image of
(
x
0
,y
0
)isgivenby(
β
(
g
(
x
0
)
/h
(
x
0
)
p
−
1
+
p
1
)
,βy
0
(
g/h
)
(
x
0
)). Note that if the
y
-coordinate is not needed
1
, we can avoid computing
h
(
x
0
), thus saving
−
/
2
multiplications. Of course, for specific small
,suchas
=3
,
5, it is more conve-
nient to write down the isogeny explicitly in terms of the kernel points and find
optimized formulas.
When
= 2, things are more complex, but in our specific case we can easily
deal with it. The isogeny of
E
vanishing (0
,
0) is readily seen as being
∼
F
:
y
2
=
x
3
+
A
+6
B
x
2
+4
A
+2
B
2
x,
(4)
φ
:
E
→
F,
1
B
x
2
.
y
1)
2
(5)
(
x
−
1
B
y
(
x, y
)
→
,
−
x
If a point
P
8
satisfying [4]
P
8
=(0
,
0) is known, then
√
A
+ 2 can be computed
from the abscissa of
φ
(
P
8
), and
F
can be put in Montgomery form as before.
The isogeny vanishing on a generic point of order two
P
2
=(0
,
0) can be easily
computed when a point
P
4
satisfying [2]
P
4
=
P
2
is known: change coordinates
to bring
P
2
in (0
,
0), then use the abscissa of
P
4
to express the resulting curve
in Montgomery form (this is the same technique as above, taking
= 1); notice
that this step needs to be done at most once per key exchange. When points of
order 8 or 4 are not available, as in the last few steps of our setting, ordinary
Weierstrass forms yield formulas that require a few extra multiplications.
We conclude this section with operation counts for the key exchange al-
gorithms. We write
I,M,S
for the costs of one inversion, multiplication and
squaring in
M
;wecount
multiplication by constants as normal multiplications. For simplicity, we only
list quadratic terms in
e
A
.
F
p
2
respectively, and we make the assumption
S
≤
Multiplication-based.
If
P
is a point on the Kummer line, computing
P
times
an
n
-bit integer costs (7
M
+4
S
)log
2
n
(see [12]). Thus the cumulative cost of
Step 2 is
e
A
−
1
1
2
(7
M
+4
S
)(log
2
√
p
)
2
log
A
2
.
(7
M
+4
S
)log
2
i
A
∼
i
=1
Doubling a point on the Kummer line only costs 3
M
+2
S
, and thus the cost for
A
=2dropsdownto
2
(3
M
+2
S
)(log
2
√
p
)
2
.
Isogeny-based.
The only quadratic term in
e
A
appears at Step 8. Since we do
not need the
y
coordinate of the points involved in this step, we only need the
1
While
x
coordinates are enough to compute Velu's isogenies and the image curve,
this forces the other party to use
y
-coordinate-free formulas for point multiplication.
