Bit Encryption Is Complete

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 [21], 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. Our construction is black-box, and thus requires novel techniques to avoid known impossibility results concerning trapdoor predicates [10]. To the best of our knowledge, our work is also the first example of a non-shielding reduction (introduced in [9]) in the standard (i.e., not random-oracle) model.