Summary
Today we show how to construct an efficient CCA-secure public-key encryption scheme in the random oracle model using RSA.
As we discussed in the previous lecture, a cryptographic scheme defined in the random oracle model is allowed to use a random function which is known to all the parties. In an implementation, usually a cryptographic hash function replaces the random oracle. In general, the fact that a scheme is proved secure in the random oracle model does not imply that it is secure when the random oracle is replaced by a hash function; the proof of security in the random oracle model gives, however, at least some heuristic confidence in the soundness of the design.
1. Hybrid Encryption with a Random Oracle
We describe a public-key encryption scheme which is based on: (1) a family of trapdoor permutations (for concreteness, we shall refer specifically to RSA below); (2) a CCA-secure private-key encryption scheme
; (3) a random oracle
mapping elements in the domain and range of the trapdoor permutation into keys for the private-key encryption scheme
.
- Key generation:
picks an RSA public-key / private-key pair
;
- Encryption: given a public key
and a plaintext
,
picks at random
, and outputs
- Decryption: given a private key
and a cyphertext
,
decrypts the plaintext by computing
and
.
This is a hybrid encryption scheme in which RSA is used to encrypt a “session key” which is then used to encrypt the plaintext via a private-key scheme. The important difference from hybrid schemes we discussed before is that the random string encrypted with RSA is “hashed” with the random oracle before being used as a session key.
2. Security Analysis
Theorem 1 Suppose that, for the key size used in
, RSA is a
-secure family of trapdoor permutations, and that exponentiation can be computed in time
; assume also that
is a
CCA-secure private-key encryption scheme and that
can be computed in time
.
Then
is
CCA-secure in the random oracle model.
We sketch an outline of the proof. We assume that there is an algorithm showing that
is not
CCA-secure. From
we derive an algorithm
running in time
which is a CCA attack on
. If
succeeds with probability at least
as a distinguishing CCA attack against
, then we have violated the assumption on the security of
. But if
succeeds with probability less than
, then we can devise an algorithm
, also of running time
, which inverts RSA with probability at least
.
It takes tenure and tenacity to teach random oracles in a theory class. 🙂
And in the next lecture 24 I give a concrete-security treatment of zero knowledge. (It will appear in the full notes.)