Cryptography Reference
In-Depth Information
Proof
(Sketch) Consider
t
r
(
Q,P
)
(
q
k
f
r,Q
(
P
)
(
q
k
−
1)
/r
=
−
1)
/r
. Since
r
|
N
,Exercise
26.3.8
implies that this is equal to
f
N,Q
(
P
)
(
q
k
−
1)
/N
.
Indeed
t
r
(
Q,P
)
L
(
q
k
f
LN,Q
(
P
)
(
q
k
f
T
k
−
1
,Q
(
P
)
(
q
k
−
1)
/r
−
1)
/N
−
1)
/N
.
=
=
[
T
k
−
=
O
E
so
take
f
T
k
,Q
=
Now,
1]
Q
one
can
f
T
k
−
1
,Q
.
(To
prove
this,
note
=
T
k
(
Q
)
−
([
T
k
]
Q
)
−
(
T
k
−
O
E
)
=
T
k
(
Q
)
−
−
(
T
k
−
O
E
)
=
that div(
f
T
k
,Q
)
1)(
(
Q
)
1)(
(
T
k
−
1)(
Q
)
−
(
T
k
−
1)(
O
E
).) Hence, the
L
th power of the reduced Tate-Lichtenbaum
pairing is
f
T
k
,Q
(
P
)
(
q
k
−
1)
/N
.Now
f
T,Q
(
P
)
T
k
−
1
f
T,
[
T
]
Q
(
P
)
T
k
−
2
f
T
k
,Q
(
P
)
=
···
f
T,
[
T
k
−
1
]
Q
(
P
)
,
(26.4)
which follows by considering the divisors of the left- and right-hand sides. The final step,
and the only place we use
π
q
(
Q
)
=
[
q
]
Q
=
[
T
]
Q
, is to note that
f
T,Q
(
P
)
f
T,
[
T
]
Q
(
P
)
=
f
T,π
q
(
Q
)
(
P
)
=
(26.5)
where
f
q
denotes raising all coefficients of the rational function
f
to the power
q
.
This follows because
E
and
P
are defined over
F
q
,so
σ
(
f
T,Q
(
P
))
=
f
T,σ
(
Q
)
(
P
) for all
f
T,Q
(
P
)
c
, which completes the
σ
∈
Gal(
F
q
k
/
F
q
). One therefore computes
f
T
k
,Q
(
P
)
=
proof.
q
m
(mod
r
)forsome
Exercise 26.3.14
Generalise Theorem
26.3.13
to the case where
T
≡
m
∈ N
. What is the corresponding value of
c
?
26.3.4 Optimal pairings
Lee, Lee and Park [
331
], Hess [
257
] and Vercauteren [
554
] have used combinations of
pairings that have the potential for further loop shortening over that provided by the ate
pairing.
Ideally, one wants to compute a pairing as
f
M,Q
(
P
), with some final exponentation,
where
M
is as small as possible. Hess and Vercauteren conjecture that the smallest possible
value for log
2
(
M
), for points of prime order
r
in an elliptic curve
E
over
F
q
with embedding
degree
k
(
q,r
), is log
2
(
r
)
/ϕ
(
k
(
q,r
)). For such a pairing, Miller's algorithm would be sped
up by a factor of approximately
ϕ
(
k
(
q,r
)) compared with the time required when not
using loop shortening. The method of Vercauteren actually gives a pairing as a product
of
l
i
=
0
f
M
i
,Q
(
P
)
q
i
(together with some other terms) where all the integers
M
i
are of the
desired size; such a pairing is not automatically computed faster than the naive method, but
if the integers
M
i
all have a large common prefix in their binary expansions then such a
saving can be obtained. If a pairing can be computed with approximately log
2
(
r
)
/ϕ
(
k
(
q,r
))
iterations in Miller's algorithm then it is called an
optimal pairing
.
