Paper 2024/944

Quantum CCA-Secure PKE, Revisited

Navid Alamati, VISA Research
Varun Maram, SandboxAQ
Abstract

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, i.e., when an adversary can query a superposition of ciphertexts. Boneh and Zhandry (CRYPTO 2013) defined the notion of quantum CCA (qCCA) security to guarantee privacy of messages in the presence of quantum decryption queries. However, their construction is based on an exotic cryptographic primitive (namely, identity-based encryption with security against quantum queries), for which only one instantiation is known. In this work, we comprehensively study qCCA security for public-key encryption (PKE) based on both generic cryptographic primitives and concrete assumptions, yielding 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 (isogeny-based) 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 also show how to instantiate quantum ATDFs from the LWE assumption. * 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2024
Contact author(s)
alamati @ umich edu
varun maram @ sandboxaq com
History
2024-06-13: approved
2024-06-12: received
See all versions
Short URL
https://ia.cr/2024/944
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/944,
      author = {Navid Alamati and Varun Maram},
      title = {Quantum {CCA}-Secure {PKE}, Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/944},
      year = {2024},
      url = {https://eprint.iacr.org/2024/944}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.