@inproceedings{MS09,
	title={Bit Encryption is Complete},
	author={Steven Myers and abhi shelat},
	booktitle={FOCS'09},
	year={2009}
}

PDF

Under CPA and CCA1 attacks, a secure bit encryption scheme can be applied bit-by-bit to construct a secure many-bit encryption scheme. The same construction fails, however, under a CCA2 attack. In fact, since the notion of CCA2 security was introduced by Rackoff and Simon, it has been an open question to determine whether single bit CCA2 secure encryption implies the existence of many-bit CCA2 security. We positively resolve this long-standing question and establish that bit encryption is complete for CPA, CCA1, and CCA2 notions under both indistinguishability and non-malleability security requirements.

Our construction is black-box, and thus requires novel techniques to avoid known impossibility results concerning trapdoor predicates. To the best of our knowledge, our work is the first example of a non-shielding reduction (introduced by Gertner, Malkin and Myers) in the standard model.