Bounded CCA2-Secure Encryption

Whereas encryption schemes withstanding only passive chosen-plaintext attacks (CPA) can be constructed based on a variety of computational assumptions, only a few assumptions are known to imply the existence of  encryption schemes withstanding adaptive chosen-ciphertext attacks (CCA2). Towards addressing this asymmetry, we consider a weakening of the CCA2 model---bounded CCA2-security---wherein security needs only hold against adversaries that make an a-priori bounded number of queries to the decryption oracle.  Regarding this notion we show (without any further assumptions):

• For any polynomial $q$, a simple black-box construction of $q$-bounded IND-CCA2-secure encryption schemes, from any CPA secure encryption scheme. When instantiated with the DDH assumption, this construction additionally yields encryption schemes with very short ciphertexts.

• For any polynomial $q$, a (non-black box) construction of $q$-bounded NM-CCA2-secure encryption schemes, from any CPA secure encryption scheme. As far as we know, bounded-CCA2 non-malleability is the strongest notion of security known to be achievable assuming only the existence of CPA secure encryption schemes.
  

Finally, we show that non-malleability and indistinguishability are not equivalent under bounded CCA2 attacks
(in contrast to general CCA2 attacks).