IND-CPA KEM ⇒ IND-CPA PKE

Fully-black-box reduction · standard model · folklore · security loss: a factor 2: the IND-CPA advantage is at most twice the KEM IND-CPA advantage

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.