Cryptography Reference
In-Depth Information
10.4 The Boneh-Franklin IBE Scheme
Next we present the first fully functional IBE scheme, which was introduced by
Boneh and Franklin in 2001 and is explained in detail in [35]. As we will see, this
scheme is pairing-based, so we start by introducing pairings defined on groups.
10.4.1 Pairings
We are going to define a
pairing
, also called a (
nondegenerate
or
admissible
)
bilinear
map
,ora
bilinear pairing
. This definition involves two groups
G
1
,
G
2
, the first of
which will be denoted additively while the second will be denoted multiplicatively.
The identity element of
G
1
will be denoted by
and that of
G
2
by 1. The reason
why these differing notations are used for the groups is historical and is due to the
fact that, in the only cryptographically useful pairings known so far,
G
1
is a subgroup
of an elliptic curve (traditionally written additively),
5
while
G
2
is a subgroup of the
multiplicative group of a finite field. In addition, we will assume that
G
1
and
G
2
are
of order
p
, where
p
is (a large) prime. In particular,
G
1
and
G
2
are cyclic groups
and we will assume that
P
is a generator of
G
1
, so that we may write
G
1
=
O
P
.
Definition 10.7
A
pairing
on
(
G
1
,
G
2
)
is a map
e
ˆ
:
G
1
×
G
1
→
G
2
that satisfies the following conditions:
1. (Bilinearity) For all
R
,
S
,
T
∈
G
1
,
e
ˆ
(
R
+
S
,
T
)
=ˆ
e
(
R
,
T
)
ˆ
e
(
S
,
T
)
and
e
ˆ
(
R
,
S
+
T
)
=ˆ
e
(
R
,
S
)
ˆ
e
(
R
,
T
).
2. (Non-degeneracy)
1.
3. (Computability) There is an efficient algorithm to compute
e
ˆ
(
P
,
P
)
=
e
.
ˆ
Remarks 10.2
Some straightforward consequences of the definition of pairing are,
for all
R
,
S
∈
G
1
:
1.
e
ˆ
(
R
, O)
=ˆ
e
(O,
R
)
=
1.
)
−
1
.
2.
e
ˆ
(
R
,
−
S
)
=ˆ
e
(
−
R
,
S
)
=ˆ
e
(
R
,
S
ab
for all
a
ˆ
(
,
)
=ˆ
(
,
)
,
∈ Z
3.
e
aR
bS
e
R
S
b
.
ˆ
(
,
)
=ˆ
(
,
)
=
4. (Symmetry)
e
R
S
e
S
R
. This follows from the fact that
R
aP
and
S
=
bP
, together with the previous item.
5
Capital letters—often starting with the letter
P
—are commonly used to denote the elements of
G
1
, which comes from the fact that, when
G
1
is an elliptic curve group, its elements are points of