Cryptography Reference
In-Depth Information
However, the most-used public-key scheme that can be proved CCA secure in some
(weaker) sense is a variant of RSA called RSA-OAEP that we study in Sect.
8.3.6
.
The security proof for this scheme is a reduction to the RSA assumption (see
8.3.1
below) in the so-called
random oracle model
[18], in which it is assumed that some
underlying hash functions are ideal in the sense that they are modeled as random
oracles.
1
Of course, the hash functions used in practice are not random oracles but it
is expected that their behavior is sufficiently close for security to carry over to the real
world and hence this proof, while not providing a guarantee of security, increases
our confidence in the scheme. For a thorough discussion of the random oracle model
and its implications we refer to [109, Chap. 13].
8.2.2 Hybrid Encryption and Its Security
Public-key encryption has the drawback of being significantly less efficient than
private-key encryption and, in fact, it can be orders of magnitude slower depend-
ing on the implementations (as we will see, the encryption operation for public-
key schemes is usually modular exponentiation which, although efficient from the
complexity-theoretic point of view, is much slower than, say, AES encryption). Thus,
although public-key encryption schemes can be used to encrypt arbitrarily long mes-
sages, they are seldom used when the amount of data to be encrypted is large. To be
more precise, a public-key encryption scheme is often combined with a private-key
encryption scheme in such a way that one gets the advantages of both: on the one
hand, secure communication can be established between the parties without hav-
ing to share previous information (assuming, as usual, secure key distribution for
public keys) and, on the other, efficiency is high, approaching that of the private-
key encryption scheme for large amounts of data. This combination of private-key
with public-key produces a
hybrid encryption scheme
and the basic idea is that the
sender chooses a random symmetric private key (sometimes called a
session key
) and
encrypts it with the public key of the receiver. The sender also encrypts the message
with the symmetric key he generated and sends both ciphertexts to the receiver. The
receiver first uses her private key to recover the symmetric key and then uses this key
to recover the message. The hybrid scheme can then be defined as follows, assuming
that the keys of the private-key scheme
E
2
are contained in the plaintext space of the
public-key scheme
E
1
:
Definition 8.9
Let
E
1
=
(
Gen
1
,
Enc
1
,
Dec
1
)
be a public-key encryption scheme
and
E
2
=
(
Gen
2
,
Enc
2
,
Dec
2
)
a private-key encryption scheme. A hybrid encryption
scheme
E
=
(
Gen
,
Enc
,
Dec
)
is constructed as follows:
1
A random oracle is an ideal hash function which, on each new input query, will pick uniformly at
random some response from its output domain and will always return the same response if asked
the same query again.
