Cryptography Reference
In-Depth Information
ˆ
(
,
)
=
∈
=
O
5.
e
R
S
1 for all
S
G
1
implies that
R
. Note that this just a reformulation
of the non-degeneracy property.
The existence of a pairing on
establishes a strong connection between
properties of
G
1
related to discrete logarithms and the corresponding properties of
G
2
. For example, we have the following reduction which was proved by Menezes et
al. in [139]:
(
G
1
,
G
2
)
Proposition 10.2
(MOV reduction)
If there is a pairing on
(
G
1
,
G
2
)
, then the DLP on G
1
is no harder than in G
2
.
∈ Z
+
Proof
Let
R
,
S
∈
G
1
. We want to find
a
such that
S
=
aR
. Setting
g
=ˆ
e
(
R
,
R
)
and
h
=ˆ
e
(
S
,
R
)
we have, because of the bilinearity of
e
, that
ˆ
a
g
a
. Thus we have that log
R
S
h
=ˆ
e
(
S
,
R
)
=ˆ
e
(
aR
,
R
)
=ˆ
e
(
R
,
R
)
=
=
log
g
h
and
we can compute the former logarithm by computing the latter.
Observe that, as a consequence of the MOV reduction, in order for the discrete
logarithm problem to be hard in
G
1
, it must be also hard in
G
2
and this must always
be taken into account when selecting the security parameter for a DLP-based scheme
on
G
1
.
Another important consequence of the existence of a pairing on
(
G
1
,
G
2
)
is the
following:
Proposition 10.3
If there is a pairing on
(
G
1
,
G
2
)
, then the decisional Diffie-
Hellman problem on G
1
can be efficiently solved.
Proof
Recall that the DDH problem on
G
1
is to distinguish between the distrib-
utions
(
aP
,
bP
,
abP
)
and
(
aP
,
bP
,
cP
)
when
a
,
b
,
c
are randomly chosen in
Z
p
.
Then, on input
(
P
,
A
,
B
,
C
)
, where
G
1
=
P
and
A
,
B
,
C
∈
G
1
, the distinguisher
=ˆ
(
,
)
=ˆ
(
,
)
(
,
,
)
computes
g
1
e
P
C
and
g
2
e
A
B
and it guesses that
A
B
C
is of the
(
,
,
)
if and only if
g
1
=
form
aP
bP
abP
g
2
. To see that the distinguisher succeeds
except with negligible probability, let
A
=
aP
,
B
=
bP
,
c
=
cP
, where
a
,
b
,
c
∈ Z
p
c
and
and either
c
=
ab
mod
p
or
c
is random. Then
g
1
=ˆ
e
(
P
,
cP
)
=ˆ
e
(
P
,
P
)
ab
. Since
P
is a generator of
G
1
, we have that
cP
g
2
=ˆ
e
(
aP
,
bP
)
=ˆ
e
(
P
,
P
)
=
abP
if and only if
c
=
ab
mod
p
and, since
e
ˆ
(
P
,
P
)
is a generator of
G
2
, the latter con-
dition is equivalent to
g
1
=
g
2
. Hence
g
1
=
g
2
if and only if the triple is of the form
(
. In this case the distinguisher succeeds and, if
c
is random, it also
succeeds except when
c
aP
,
bP
,
abP
)
ab
mod
p
, which only occurs with negligible probability.
Thus the problem can be efficiently solved with two pairing evaluations and one
comparison.
=
Remark 10.3
The result of the preceding proposition does not seem to extend to
the computational Diffie-Hellman problem (recall that the CDH problem in
G
1
is to
compute
abP
given
aP
,
bP
, for randomly chosen
a
,
b
∈ Z
p
). Joux and Nguyen have
given examples of pairings on
where the CDH problem in
G
1
is believed
to be hard. In [139] it is shown that the MOV reduction may be applied to a pairing
defined on a special class of elliptic curves, giving a successful cryptanalytic attack
(
G
1
,
G
2
)
