Cryptography Reference
In-Depth Information
g
p
f
P
. Now, using part 4 of Lemma
8.5.17
df
Q
f
Q
=
Hence, one can let
f
Q
=
d
(
g
p
f
P
)
g
p
df
P
+
f
P
dg
p
g
p
f
P
g
p
f
P
=
.
Part 6 of Lemma
8.5.17
gives
dg
p
=
pg
p
−
1
dg
=
0 (since we are working in
F
p
) and
df
P
=
af
a
−
P
df
P
. Hence
df
Q
f
Q
=
a
df
P
f
P
,
which proves the result.
Exercise 26.4.4
Generalise Lemma
26.4.3
to arbitrary curves.
Lemma
26.4.3
therefore maps the DLP in
E
(
F
p
)[
p
]toaDLPin
F
p
(
E
). It remains to
solve the DLP there.
O
E
. Write
Lemma 26.4.5
Let the notation be as in Lemma
26.4.3
. Let t be a uniformiser at
t
−
p
f
1
t
−
(
p
−
1)
f
2
t
−
(
p
−
2)
f
P
=
+
+
+···
. Then
df
P
f
P
=
(
f
1
+···
)
dt.
Proof
Clearly,
f
−
1
P
t
p
f
1
t
p
+
1
=
−
+···
. From part 8 of Lemma
8.5.17
we have
∂f
P
∂t
dt
pt
−
p
−
1
1)
f
1
t
−
p
df
P
=
=
(
−
−
(
p
−
+···
)
dt.
F
p
we have
df
P
=
(
f
1
t
−
p
+···
Since we are working in
)
dt
. The result follows.
Putting together Lemma
26.4.3
and Lemma
26.4.5
:if
Q
=
[
a
]
P
then
df
P
/f
P
=
(
f
1
+
···
)
dt
. Hence, as long as one can compute the expansion
of
df
P
/f
P
with respect to
t
, one can solve the DLP. Indeed, this is easy: use Miller's
algorithm with power series expansions to compute the power series expansion of
f
P
and follow the above calculations. R uck [
455
] gives an elegant formulation (for general
curves) that computes only the desired coefficient
f
1
; he calls it the “additive version of the
Tate-Lichtenbaum pairing”.
)
dt
and
df
Q
/f
Q
=
(
af
1
+···
26.5 Computational problems
26.5.1 Pairing inversion
We briefly discuss a computational problem, that is required to be hard for many crypto-
graphic applications of pairings.
Definition 26.5.1
Let
G
1
,G
2
,G
T
be groups of prime order
r
and let
e
:
G
1
×
G
2
→
G
T
be
a non-degenerate bilinear pairing. The
pairing inversion problem
is: Given
Q
∈
G
2
,z
∈
G
T
to compute
P
∈
G
1
such that
e
(
P,Q
)
=
z
.
