Cryptography Reference
In-Depth Information
(the MOV attack) against DLP-based schemes (such as, for example, Elgamal) on
this class of curves (see Sect.
11.3.3
for more details).
In order to define a pairing-based IBE scheme, we need to associate a hard problem
with a pairing on
. For this purpose, Boneh and Franklin introduced in [35]
the
bilinear Diffie-Hellman problem
(BDH problem) which we now define:
(
G
1
,
G
2
)
Definition 10.8
Let
, where
G
1
and
G
2
are groups of
prime order
p
and
P
is a generator of
G
1
.The
BDH problem
in
e
be a pairing on
ˆ
(
G
1
,
G
2
)
(
G
1
,
G
2
,
ˆ
e
)
is the
∈ Z
p
, compute
abc
following: Given
(
P
,
aP
,
bP
,
cP
)
with
a
,
b
,
c
e
ˆ
(
P
,
P
)
∈
G
2
.
An algorithm
A
has advantage
ε
in solving BDH
if
abc
Pr
(A(
P
,
aP
,
bP
,
cP
)
=ˆ
e
(
P
,
P
)
)
≥
ε.
If we consider a BDH generator
, i.e., a PPT algorithm that, on input a security
parameter 1
k
, outputs a set of BDHparameters (i.e., a description of a pairing between
two groups
G
1
,
G
2
, of prime order
p
, where the security parameter
k
is used to
determine the size of
p
), then we say that
the BDH problem is hard relative to
G
G
(or
G
A
that
satisfies the BDH assumption
) if the advantage of any PPT algorithm
in
solving the BDH for
G
is negligible as a function of
k
.
The relevant question now is: how hard is the BDH problem? The natural way to
look at this question is to consider the relationship between BDH and other problems
that are presumed hard. It is obvious that the BDH problem is no harder than the
DLP in
G
1
and the following result is also straightforward:
Proposition 10.4
The BDH problem in
(
G
1
,
G
2
,
ˆ
e
)
is no harder than the CDH
problem in G
1
.
Proof
Given
we may use the CDH algorithm to compute
abP
and
then we may use the pairing to obtain
(
P
,
aP
,
bP
,
cP
)
abc
.
ˆ
(
,
)
=ˆ
(
,
)
e
abP
cP
e
P
P
Exercise 10.8
Show that the BDH problem in
(
G
1
,
G
2
,
ˆ
e
)
is no harder than the
CDH problem in
G
2
.
The converse of these results is an open problem, i.e., we do not know whether
an algorithm for solving the BDH problem is sufficient to solve the CDH problem
in either
G
1
or
G
2
. Apart from the Boneh-Franklin scheme that we are going to
describe, the BDH assumption has been used in other cryptographic schemes such
as one of Joux for tripartite Diffie-Hellman key agreement.
10.4.2 The Boneh-Franklin Scheme
We next define the Boneh-Franklin IBE scheme, starting from the so-called basic
version
BasicIdent
which will subsequently be extended to the more secure
FullIdent
version by means of a generic transformation process.
