Bounded CCA2-Secure Encryption

Whereas encryption schemes withstanding 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

IND-CPA-secure

encryption scheme. When instantiated with the Decisional Diffie-Hellman (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

IND-CPA-secure

encryption scheme. Bounded-CCA2 non-malleability is the strongest notion of security yet known to be achievable assuming only the existence of IND-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).