Cryptography Reference
In-Depth Information
The bilinear Diffie-Hellman problem was introduced in Definition
23.3.9
. In additive
notation it is: given
P,Q,
[
a
]
Q,
[
b
]
Q
to compute
e
(
P,Q
)
ab
.
Lemma 26.5.2
If one has an oracle for pairing inversion then one can solve BDH.
Proof
Given the BDH instance
P,Q,
[
a
]
Q,
[
b
]
Q
compute
z
1
=
e
(
P,
[
a
]
Q
) and call the
pairing inversion oracle on (
Q,z
1
) to get
P
such that
e
(
P
,Q
)
=
z
1
. It follows that
P
=
[
a
]
P
. One then computes
e
(
P
,
[
b
]
Q
)
e
(
P,Q
)
ab
as required.
=
Further discussion of pairing inversion is given by Galbraith, Hess and Vercauteren [
205
].
Exercise 26.5.3
Show that if one can solve pairing inversion then one can solve the Diffie-
Hellman problem in
G
1
.
Exercise 26.5.4
Show that if one has an oracle for pairing inversion then one can per-
form passive selective forgery of signatures in the Boneh-Boyen scheme presented in
Figure
23.3.9
.
Exercise 26.5.5
Show that if one has an oracle for pairing inversion then one can solve the
q
-SDH problem of Definition
22.2.17
.
26.5.2 Solving DDH using Pairings
Pairings can be used to solve the decision Diffie-Hellman (DDH) problem in some cases.
First, we consider a variant of DDH that can sometimes be solved using pairings.
Definition 26.5.6
Let
E
(
F
q
) have prime order
r
.The
co-DDH problem
is: given (
P,
[
a
]
P,Q,
[
b
]
Q
) to determine whether or not
a
F
q
) be an elliptic curve and let
P,Q
∈
E
(
≡
b
(mod
r
).
∈
Exercise 26.5.7
Show that co-DDH is equivalent to DDH if
Q
P
.
Suppose now that
E
[
r
]
⊆
E
(
F
q
),
P
=
O
E
, and that
Q
∈
P
. Then
{
P,Q
}
generates
E
[
r
] as a group. By non-degeneracy of the Weil pairing, we have
e
r
(
P,Q
)
=
1. It follows
that
e
r
(
P,Q
)
a
e
r
(
P,Q
)
b
.
e
r
([
a
]
P,Q
)
=
and
e
r
(
P,
[
b
]
Q
)
=
Hence, the co-DDH problem can be efficiently solved using the Weil pairing.
The above approach cannot be used to solve DDH, since
e
r
(
P,P
)
1 by the alternating
property of the Weil pairing. In some special cases, the reduced Tate-Lichtenbaum pairing
satisfies
ˆ
t
r
(
P,P
)
=
=
1 and so can be used to solve DDH in
P
. In general, however, DDH
cannot be solved by such simple methods.
When
E
is a supersingular elliptic curve and
P
=
O
E
then, even if
ˆ
t
r
(
P,P
)
=
1,
E
such that
ˆ
t
r
(
P,ψ
(
P
))
there always exists an endomorphism
ψ
:
E
→
=
1. Such an
