RSA ⇒ IND-CCA KEM

Random oracle model · Sho01b · security loss: tight: the inverter finds the $e$-th root of the challenge ciphertext among the adversary’s oracle queries by testing each, with no guessing step

Statement

RSA-KEM samples $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N$, sends $c=r^e\mathrm{mod}N$ and derives the key $\mathsf{H}(r)$. If the RSA assumption holds, RSA-KEM is an IND-CCA-secure KEM in the random oracle model — Sho01b.

Sketch

An adversary that distinguishes $\mathsf{H}(r)$ from uniform must query $\mathsf{H}$ at the $e$-th root of the challenge ciphertext. The reduction plants its RSA instance as $c^{\ast }$, reads the preimage off the query list, and uses the same list, with lazily assigned keys, to simulate decapsulation.

Notes

• A ciphertext is one element of ${\mathbb{Z}}_N$; encapsulation costs one exponentiation by $e$ and one evaluation of $\mathsf{H}$, decapsulation one exponentiation by the secret exponent and one evaluation of $\mathsf{H}$ — standard.