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 .