Paper 2021/271

On the CCA Compatibility of Public-Key Infrastructure

Dakshita Khurana and Brent Waters


In this work, we study the compatibility of any key generation or setup algorithm. We focus on the specific case of encryption, and say that a key generation algorithm KeyGen is X-compatible (for X \in {CPA, CCA1, CCA2}) if there exist encryption and decryption algorithms that together with KeyGen, result in an X-secure public-key encryption scheme. We study the following question: Is every CPA-compatible key generation algorithm also CCA-compatible? We obtain the following answers: - Every sub-exponentially CPA-compatible KeyGen algorithm is CCA1-compatible, assuming the existence of hinting PRGs and sub-exponentially secure keyless collision resistant hash functions. - Every sub-exponentially CPA-compatible KeyGen algorithm is also CCA2-compatible, assuming the existence of non-interactive CCA2 secure commitments, in addition to sub-exponential security of the assumptions listed in the previous bullet. Here, sub-exponentially CPA-compatible KeyGen refers to any key generation algorithm for which there exist encryption and decryption algorithms that result in a CPA-secure public-key encryption scheme {\em against sub-exponential adversaries}. This gives a way to perform CCA secure encryption given any public key infrastructure that has been established with only (sub-exponential) CPA security in mind. The resulting CCA encryption makes black-box use of the CPA scheme and all other underlying primitives.

Available format(s)
Publication info
Published by the IACR in Pkc 2021
public key compatibilityCCA securitynon-malleable
Contact author(s)
dakshita @ illinois edu
bwaters @ cs utexas edu
2021-07-09: revised
2021-03-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dakshita Khurana and Brent Waters},
      title = {On the CCA Compatibility of Public-Key Infrastructure},
      howpublished = {Cryptology ePrint Archive, Paper 2021/271},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.