Cryptography Reference
In-Depth Information
Theorem 10.2
Suppose that the hash functions H
1
and H
2
are random oracles and
the BDH problem is hard in the groups generated by
G
. Then
BasicIdent
is
IND-ID-CPA secure.
The theorem shows that
BasicIdent
is secure against chosen plaintext attacks
but the scheme is not secure against chosen ciphertext attacks. However, the already
mentioned technique due to Fujisaki-Okamoto transforms an IND-ID-CPA secure
scheme like this one into an IND-ID-CCA secure scheme and we will apply it to
BasicIdent
. The general Fujisaki-Okamoto transformation may be described
as follows. Let
be a probabilistic public-key encryption scheme with encryption
algorithm
Enc
, and denote by
Enc
E
the result of encrypting the message
m
using the public key
pk
and the random value
r
. Then Fujisaki and Okamoto define
a new encryption scheme by using a random value
(
pk
,
r
,
m
)
and two cryptographic hash
functions
H
3
,
H
4
and setting the encryption of
m
to be:
σ
Enc
fo
(
pk
,
m
)
:=
(
Enc
(
pk
,
H
3
(σ,
m
), σ ),
H
4
(σ )
⊕
m
).
Of course, decryption is modified accordingly; we leave its description as an exercise
and we will give the details in the concrete case when the transformation is applied
to
BasicIdent
.
Fujisaki and Okamoto showed that if
E
is an OW-CPA secure encryption scheme,
then the result of applying this transformation to
is IND-CCA secure in the random
oracle model (the hash functions
H
3
and
H
4
are modeled as random oracles in the
proof). Since IND-CPA implies OW-CPA, we see that from an IND-CPA secure
scheme an IND-CCA secure one is obtained. In fact, Boneh and Franklin adapt this
reduction to the identity-based case and show that an IND-ID-CCA secure scheme
FullIdent
can be obtained from
BasicIdent
as follows:
E
Definition 10.10 Boneh-Franklin
FullIdent
scheme.
The Boneh-Franklin
FullIdent
scheme is the scheme
(
Setup, Der, Enc, Dec
)
defined as follows.
•
Setup
: The same as in
BasicIdent
except that, in addition, two hash functions
H
3
:{
n
n
→ Z
p
and
H
4
:{
n
n
are chosen.
0
,
1
}
×{
0
,
1
}
0
,
1
}
→{
0
,
1
}
•
Der
: The same as in
BasicIdent
.
n
and an identity
id
, proceed as follows:
•
Enc
: On input a message
m
∈{
0
,
1
}
G
1
.
1. Compute
Q
id
:=
H
1
(
id
)
∈
n
.
2. Choose a random
σ
←{
0
,
1
}
:=
H
3
(σ,
)
3. Set
r
.
4. Output the ciphertext:
m
r
c
:=
(
rP
,σ
⊕
H
2
(
ˆ
e
(
Q
id
,
P
pub
)
),
m
⊕
H
4
(σ )).
G
1
×{
n
n
andaprivatekey
D
id
∈
G
1
,
•
Dec
: On input
c
=
(
U
,
x
,
y
)
∈
0
,
1
}
×{
0
,
1
}
proceed as follows:
