IND-CPA KEM ⇒ IND-CPA PKE
Statement
Let be an IND-CPA-secure KEM with key space . The PKE scheme with message space that encrypts as for and decrypts to if or , and to otherwise is IND-CPA-secure, and it is -correct when the KEM is — folklore.
Sketch
The reduction samples , answers the challenge pair with for its KEM challenge , and outputs whether the adversary guesses ; when is uniform, is independent of . Decryption fails exactly when , whatever is.
Notes
- With a one-time IND-CPA SKE scheme in place of the one-time pad, the same argument gives PKE for the SKE scheme’s message space (IND-CPA KEM + SKE ⇒ IND-CPA PKE) — folklore.