No fixed-construction reduction from NM-CPA security to CCA1 security
Statement
If an NM-CPA-secure PKE scheme exists, then there is a PKE scheme that is NM-CPA-secure but not IND-CCA1-secure, so the identity map is no reduction from NM-CPA to IND-CCA1 security — BDPR98.
Sketch
Given an NM-CPA-secure , fix two distinct messages of equal length. Let also sample into the secret key, let and , and let return on the string , where is bit of , return on , where is bit of , and return on every other string. has the message space and the correctness of . A CCA1 adversary makes the queries , then the queries , reassembles and decrypts . In the parallel NM-CPA game of BS99 all decryption queries are made at once, before learns , so a reduction that samples itself and answers on every query errs with probability at most — standard.
Notes
- The converse separation also holds: IND-CCA1 ⇏ NM-CPA — BDPR98.