** 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 .

### Like this:

Like Loading...

*Related*

## 2 comments

Comments feed for this article

April 23, 2009 at 6:19 pm

hoeteckIt takes tenure and tenacity to teach random oracles in a theory class. :)

April 23, 2009 at 7:55 pm

lucaAnd in the next lecture 24 I give a concrete-security treatment of zero knowledge. (It will appear in the full notes.)