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 [RS91], 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.  

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