Cryptography Reference
In-Depth Information
4.1 Parameter Generation
For any fixed choice of
e
A
and
e
B
, one can easily test random values of
f
(of
any desired cryptographic size) until a value is found for which
p
=
e
A
e
B
·
f −
1or
p
=
e
A
e
B
f
+ 1 is prime; the prime number theorem in arithmetic
progressions (specifically, the effective version of Lagarias and Odlyzko [11])
provides a sucient lower bound for the density of such primes.
Once the prime
p
=
e
A
e
B
·
1isknown,Broker [2] has shown that it is easy
to find a supersingular curve
E
over
·
f
±
1)
2
=(
e
A
e
B
f
)
2
.
F
p
2
having cardinality (
p
∓
·
Starting from
E
, one can select a random supersingular curve
E
0
over
F
p
2
by
means of random walks on the isogeny graph; alternatively, one can simply take
E
0
=
E
.Ineithercase,
E
0
has group structure (
)
2
. To find a basis
Z
/
(
p
∓
1)
Z
for
E
0
[
e
A
], choose a random point
P
F
p
2
) and multiply it by (
e
B
f
)
2
to obtain a point
P
of order dividing
e
A
. With high probability,
P
will have
order exactly
e
A
; one can of course check this by multiplying
P
by powers of
A
. If the check succeeds, then set
P
A
=
P
; otherwise try again with another
P
. A second point
Q
A
of order
e
A
can be obtained in the same way. To check
whether
Q
A
is independent of
P
A
, simply compute the Weil pairing
e
(
P
A
,Q
A
)in
E
[
e
A
] and check that the result has order
e
A
; as before, this happens with high
probability, and if not, just choose another point
Q
A
. Note that the choice of
basis has no effect on the security of the scheme, since one can convert from one
basis to another using extended discrete logarithms, which are easy to compute
in
E
0
[
e
A
∈
R
E
0
(
·
]by[22].
4.2 Key Exchange
It remains to describe how Alice and Bob can compute isogenies of a given kernel.
We show how to compute
φ
A
:
E
0
→
;
the same procedure suces to compute all the other isogenies mentioned. The
computation is performed using a version of Hensel lifting modulo
A
.Let
R
0
:=
[
m
A
]
P
A
+[
n
A
]
Q
A
. The order of
R
0
is
e
A
.For0
E
A
where
E
A
=
E
0
/
[
m
A
]
P
A
+[
n
A
]
Q
A
≤
i<e
A
,let
e
A
−i−
1
A
E
i
+1
=
E
i
/
R
i
,
i
:
E
i
→
E
i
+1
,
i
+1
=
φ
i
(
R
i
)
,
where
φ
i
is a degree
A
isogeny from
E
i
to
E
i
+1
.Then
E
A
=
E
e
A
and
φ
A
=
φ
e
A
−
1
◦···◦
φ
0
.
Figure 2 gives two algorithms for this task. They both compute iteratively
(
R
i
,
e
A
−i−
A
R
i
,φ
i
,E
i
+1
)for
i<e
A
, but they differ in the strategy. The first
one, which we will refer to as
multiplication-oriented
, computes at each iteration
e
A
−i−
1
A
R
i
from
R
i
using point addition (or duplication, or triplication). The
second one, which we call
isogeny-oriented
, first forms the list (
j
A
R
0
)
j<e
A
using
point addition, then at each iteration computes the list (
j
A
R
i
+1
)
j<e
A
−i−
1
by
evaluating
φ
i
(
j
A
R
i
)foreach
j
. Observe that Alice and Bob can use one algorithm
or the other independently.
A quick analysis shows that both algorithms require
O
(log
2
p
)operationsin
F
p
. The major cost in the multiplication-based one is scalar point multiplica-
tion; this costs
O
(
e
A
log
2
A
) double-and-adds at each iteration and is repeated
