No fixed-construction reduction from CCA1 security to NM-CPA security

Conditional · against fixed-construction reductions · assuming CCA1 Security · BDPR98

Statement

If an IND-CCA1-secure PKE scheme exists, then there is a PKE scheme that is IND-CCA1-secure but not NM-CPA-secure, so the identity map is no reduction from IND-CCA1 to NM-CPA security — BDPR98.

Sketch

Given an IND-CCA1-secure , let and let ignore the appended bit . A CCA1 adversary against yields one against that strips the bit from each Phase-1 query and appends to . An NM-CPA adversary flips the last bit of , submits the result, which differs from , as its decryption query, and receives , where and ; this is except with probability at most the correctness error of , which is negligible — standard.

Notes