Cryptography Reference
In-Depth Information
Remark 11.3.17
In cryptographic protocols, one is often computing [
a
]
P
, where
a
is a
randomly chosen integer modulo
r
. Rather than choosing a random integer
a
and then
converting to a Frobenius expansion, one could choose a random Frobenius expansion of
given weight and length (this trick appears in Section 6 of [
312
] where it is attributed to H.
W. Lenstra Jr.).
2. Muller [
397
] gives an algorithm to
compute Frobenius expansions for elliptic curves over
We have analysed
π
-NAFs in the case
q
=
F
2
e
with
e>
1 (but still small).
2
e
−
1
,...,
2
e
−
1
The coefficients of the expansion lie in
.Smart[
512
] gives an algorithm
for odd
q
, with a similar coefficient set; see Exercise
11.3.18
. Lange [
330
] generalises to
hyperelliptic curves. In all cases, the output is not necessarily in non-adjacent form; to
obtain a
π
-NAF in these cases seems to require much larger digit sets. In any case, the
asymptotic density of
π
-NAFs with large digit set is not significantly smaller than 1
/
2 and
this can easily be bettered using window methods (see Exercise
11.3.19
).
{−
}
Exercise 11.3.18
Let
q>
2. Show that Algorithm
8
can be generalised (not to compute a
π
-NAF, but just a
π
-adic expansion) by taking digit set
{−
q/
2
,...,
−
1
,
0
,
1
,...,
q/
2
}
(or this set with
−
q/
2
removed when
q>
2 is even).
Exercise 11.3.19
Let
E
be an elliptic curve over a field
F
q
,let
π
be the
q
-power Frobenius
map, and let
P
∈
E
(
F
q
m
). Let
S
={−
(
q
−
1)
/
2
,...,
−
1
,
0
,
1
,...,
(
q
−
1)
/
2
}
if
q
is odd
={−
−
−
}
and
S
(
q
2)
/
2
,...,
1
,
0
,
1
,...,q/
2
if
q
is even.
Suppose one has a Frobenius expansion
l
[
a
j
]
π
j
a
(
π
)
=
j
=
0
with
a
j
∈
. Give a sliding window method to compute [
a
(
π
)]
P
using windows
of length
w
. Give an upper bound on the cost of this algorithm (including precomputation)
ignoring the cost of evaluating
π
.
S
.Let
w
∈ N
Exercise 11.3.20
(Brumley and Jarvinen [
105
]) Let
E
be an elliptic curve over
F
q
,
π
be
the
q
-power Frobenius and
P
∈
E
(
F
q
m
) have prime order
r
where
r
#
E
(
F
q
m
). Given a
=
i
[
a
i
]
π
i
, show how to efficiently compute
a
Frobenius expansion
a
(
π
)
∈ Z
such that
a
(
π
)(
P
)
=
[
a
]
P
.
For a complete presentation of Frobenius expansions, and further references, we refer
to Section 15.1 of [
16
]. For multi-exponentiation using Frobenius expansions there is also
a
π
-adic joint sparse form. We refer to Section 15.1.1.e of [
16
] for details.
11.3.3 GLV method
This method is due to Gallant, Lambert and Vanstone [
216
] for elliptic curves and
Stam and Lenstra (see Section 4.4 of [
521
]) for tori.
7
The idea is to use an “efficiently
7
A patent on the method was filed by Gallant, Lambert and Vanstone in 1999.
