Security against chosen-ciphertext attacks (CCA) concerns privacy of messages even if the adversary has access to the decryption oracle. While the classical notion of CCA security seems to be strong enough to capture many attack scenarios, it falls short of preserving the privacy of messages in the presence of quantum decryption queries. Boneh and Zhandry (CRYPTO 2013) defined the notion of quantum CCA (qCCA) security to address quantum decryption queries. However, their construction is based on an exotic cryptographic primitive, for which only one instantiation is known. In this work, we comprehensively study qCCA security and obtain the following results:
- We show that key-dependent message secure encryption (along with PKE) is sufficient to realize qCCA-secure PKE. This yields the first construction of qCCA-secure PKE from the LPN assumption.
- We prove that hash proof systems imply qCCA-secure PKE, which results in the first instantiation of PKE with qCCA security from group actions.
- We extend the notion of adaptive TDFs (ATDFs) to the quantum setting by introducing quantum ATDFs, and we prove that quantum ATDFs are sufficient to realize qCCA-secure PKE.
- We show that a single-bit qCCA-secure PKE is sufficient to realize a multi-bit qCCA-secure PKE by extending the completeness of bit encryption for CCA security to the quantum setting.
- We define quantum CCA security for predicate encryption, and we show that the generic framework of Koppula and Waters (CRYPTO 2019) for constructing CCA-secure PKE can also be used to realize quantum CCA security for predicate encryption.
