Cryptography Reference
In-Depth Information
of revocation that must also be dealt with in this context. Thus the design of IBE
schemes is a highly nontrivial endeavor for which there are no automatic methods.
In particular, there are no obvious ways to turn a standard public-key encryption
scheme into an identity-based scheme. We shall give a more formal definition below
but, for now, let us give an informal description of an IBE scheme.
An IBE scheme is a family of four algorithms, called
Setup, Der
(also called
KeyDer
or
Extract
),
Enc
and
Dec
.
Setup
is run by the PKG and generates the
system parameters
mpk
(the
master public key
) and
msk
(the
master private key
); the
first is public and the second is known only to the PKG. The pair
mk
)
is called the
master key
. The key derivation algorithm
Der
is also run by the PKG
(on behalf of the users that request a private key) which, after checking the identity
of a user, generates the private key, say,
usk
.
Enc
and
Dec
are the encryption and
decryption algorithms and behave similarly to their counterparts in standard public-
key cryptography, with the user identity acting as the public key in
Enc.
In order to better appreciate the difficulties involved in trying to produce an IBE
scheme from a standard public-key encryption scheme, let us examine an attempt to
derive an IBE scheme from the RSA encryption scheme.
=
(
mpk, msk
Example 10.1
A seemingly plausible idea to turn RSA into an IBE scheme would
be to let all users share a common modulus, with the public key of a user being the
encryption exponent and the private key the decryption exponent. Thus the scheme
would be defined by the following algorithms:
•
Setup
: The PKG runs
Gen
RSA
and generates an RSA modulus
n
=
pq
.The
master public key is
mpk
=
n
and the master private key is
msk
=
(
p
,
q
)
.
•
The encryption exponent
e
(i.e., the public key) of a user is obtained by applying
a publicly known hash function to the user identity string.
•
Der
: Given a user's identity the PKG uses the master key to compute the user's
private key (the decryption exponent
d
).
•
Enc
and
Dec
are given by the RSA functions RSA
and RSA
, respectively.
(
n
,
e
)
(
n
,
d
)
It is easy to see that this scheme is a complete failure from a security point of view.
The reason is that, as we have seen, a user that knows (
n
d
), where
n
is an RSA
modulus,
e
an encryption exponent and
d
the decryption exponent corresponding to
the pair
,
e
,
, may use eitherMiller's PPT algorithmor the Coron-May deterministic
algorithm referred to in Sect.
8.3.1
to compute the prime factors of
n
and hence the
master key
mk
(
n
,
e
)
.
1
As a consequence, any user of the system would be
able to recover the master key and hence to compute the private key of any other
user, and could also issue private keys to new users. The problem of producing, from
a user identity, an RSA modulus with a global trapdoor that only allows the PKG
(but not users) to factor the modulus is still open.
=
(
n
,(
p
,
q
))
1
Alternatively, the result given in Proposition 8.5 may be used to mount a 'common modulus attack'
which allows any user to decrypt messages addressed to another user who shares the same RSA
modulus.