Paper 2020/177

Revisiting (R)CCA Security and Replay Protection

Christian Badertscher, Ueli Maurer, Christopher Portmann, and Guilherme Rito


This paper takes a fresh approach to systematically characterizing, comparing, and understanding CCA-type security definitions for public-key encryption (PKE), a topic with a long history. The justification for a concrete security definition $X$ is relative to a benchmark application (e.g. confidential communication): Does the use of a PKE scheme satisfying $X$ imply the security of the application? Because unnecessarily strong definitions may lead to unnecessarily inefficient schemes or unnecessarily strong computational assumptions, security definitions should be as weak as possible, i.e. as close as possible to (but above) the benchmark. Understanding the hierarchy of security definitions, partially ordered by the implication (i.e. at least as strong) relation, is hence important, as is placing the relevant applications as benchmark levels within the hierarchy. CCA-2 security is apparently the strongest notion, but because it is arguably too strong, Canetti, Krawczyk, and Nielsen (Crypto 2003) proposed the relaxed notions of Replayable CCA security (RCCA) as perhaps the weakest meaningful definition, and they investigated the space between CCA and RCCA security by proposing two versions of Detectable RCCA (d-RCCA) security which are meant to ensure that replays of ciphertexts are either publicly or secretly detectable (and hence preventable). The contributions of this paper are three-fold. First, following the work of Coretti, Maurer, and Tackmann (Asiacrypt 2013), we formalize the three benchmark applications of PKE that serve as the natural motivation for security notions, namely the construction of certain types of (possibly replay-protected) confidential channels (from an insecure and an authenticated communication channel). Second, we prove that RCCA does not achieve the confidentiality benchmark and, contrary to previous belief, that the proposed d-RCCA notions are not even relaxations of CCA-2 security. Third, we propose the natural security notions corresponding to the three benchmarks: an appropriately strengthened version of RCCA to ensure confidentiality, as well as two notions for capturing public and secret replay detectability.

Available format(s)
Publication info
A major revision of an IACR publication in Pkc 2021
Composable SecurityPKECCARCCAReplay Protection
Contact author(s)
guilherme teixeira @ inf ethz ch
christian badertscher @ iohk io
2021-09-08: revised
2020-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Badertscher and Ueli Maurer and Christopher Portmann and Guilherme Rito},
      title = {Revisiting (R)CCA Security and Replay Protection},
      howpublished = {Cryptology ePrint Archive, Paper 2020/177},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.