*Scribed by Guoming Wang*

** 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 a random , and outputs
- Decryption: given a private key and a ciphertext , 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 **

The intuition behind the security of this scheme is as follows. For any adversary mounting a CCA attack on , we distinguish between the case that it does not query to the random oracle and the case that it does. In the first case, the adversary learns nothing about , and so we reduce the CCA security of to the CCA security of the private-key encryption scheme . In the second case, the adversary has managed to invert RSA. Under the RSA trapdoor permutation assumption, this case can only happen with negligible probability.

This intuition is formalized in the proof of the following theorem.

Theorem 1Suppose 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.

*Proof:* Suppose is a CCA attack on of complexity such that there are two messages

We will derive from an algorithm running in time which is a CCA attack on . If succeeds with probability at least in distinguishing between and , 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 .

The algorithm is designed to attack the private-key encryption scheme by running as a subroutine. Its idea is to convert the ciphertext into the ciphertext and then use to distinguish it. It needs to answer ‘s oracle queries to , by accessing its own oracles . In particular, in order to make its answers to the random oracle queries consistent, uses a data structure (a table) to remember the pairs that have been queried so far. The formal definition of is as follows:

**Algorithm** :

**Input**: // is unknown,

- pick RSA keys .
- pick a random .
- pairs of strings are stored in a table which is initially empty.
- simulate as follows:
- when queries :
- If there is an entry in the table, return to ;
- otherwise, pick a random , store in the table, return to .
- If , FAIL.

- when queries :
- pick a random , compute as above, return to .

- when queries :
- compute .
- if , compute as above, return to ;
- if , query to the decryption oracle and return the result to .

- when queries :

needs time to compute the answer of every oracle query from . Given that has complexity , we get has complexity . Furthermore, never submits its challenge ciphertext to its own decryption oracle , because the only way this could happen would be if submitted its challenge ciphertext to its own decryption oracle , but this is not allowed.

Let denote the event that queries to the random oracle during its execution. Note that in ‘s strategy of answering ‘s decryption queries, has implicitly set . If happens, i.e. queries , returns a random to in response to this query, but might not be equal to the unknown , and this will cause an inconsistency in ‘s answers. However, if does not happen, the answers gives to in response to its oracle queries to are always consistent and distributed identically to the answers obtained from the corresponding real oracles. So in this case, the behavior of remains unchanged. Thus we get

and hence

Then by the triangle inequality we obtain

So at least one of and must be greater than .

If , then breaks the CCA-security of , contradicting our assumption. So we should have . But in this case, we can devise an algorithm of complexity such that solves RSA with probability .

The idea of is also to simulate by providing it with appropriate input and oracle query answers. Similarly, also needs a data structure (a table) to record the answers it has given so far. However, now only knows the public RSA keys , but does not know the private key . Consequently, when decrypting a ciphertext , it cannot compute (without factoring ). Then how can we get without knowing ? In order to overcome this obstacle, we store triples of strings , instead of pairs , in the table. If is unknown yet, we use a special symbol to represent it. Now we no longer check whether the first item of each entry in the table is equal to , but check whether the second item of each entry is equal to . Because there is a one-to-one correspondence between and (given ), by checking the second item, we can get without knowing .

The formal definition of is as follows:

**Algorithm** :

**Input**: ,, // is unknown

- pick a random .
- triples of strings are stored in a table which initially contains only .
- simulate as follows: //M is the message for which (1)
- when queries :
- if , output , halt;
- if there is an entry in the table, return to ;
- otherwise, if there is an entry in the table, replace it with , return to ;
- otherwise, pick a random , store in the table, return to .

- when queries :
- pick a random , compute as above, return to .

- when queries :
- if there is an entry or in the table, return to ;
- otherwise, pick a random , store in the table, return to .

- when queries :

also needs time to compute the answer of every oracle query from . Given that has complexity , we get has complexity . Moreover, the answers gives to in response to its oracle queries to are always consistent and distributed identically to the answers obtained from the corresponding real oracles. Thus, the behavior of remains unchanged. Especially, the event remains unchanged. Furthermore, correctly solves the given RSA instance whenever occurs. So we have

which contradicts with the assumption that RSA is -secure. This concludes the proof of the theorem.

Good stuff, liked this post