No fixed-construction reduction from CPA Security to IND$-CPA Security

Unconditional · against fixed-construction reductions · folklore

Statement

The identity map is not a reduction from CPA security to IND$-CPA security of SKE: appending a constant bit to every ciphertext of a CPA-secure $\mathsf{SKE}$, so that the ciphertext space becomes $\mathcal{C}\times \{0,1\}$, preserves CPA security, while an IND$-CPA adversary that checks the bit on one query has advantage $1/2$ — folklore.

Sketch

The appended bit is independent of the message, so a CPA adversary against the modified scheme yields one against the original; a uniform ciphertext carries the constant bit only with probability $1/2$.

Notes

• The converse holds: IND$-CPA security implies CPA security, with a factor-2 loss (IND$-CPA ⇒ CPA) — standard.