No fixed-construction reduction from CCA1 security to NM-CPA security
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
- IND-CCA1 security implies IND-CPA security (CCA1 ⇒ CPA), so the same scheme is IND-CPA-secure and not NM-CPA-secure — standard.
- A construction other than the identity turns every perfectly correct IND-CPA-secure scheme into an NM-CPA-secure one (IND-CPA ⇒ NM-CPA) — PSV06.
- The converse separation also holds: NM-CPA ⇏ IND-CCA1 — BDPR98.