Paper 2020/177
Revisiting (R)CCA Security and Replay Protection
Christian Badertscher, Ueli Maurer, Christopher Portmann, and Guilherme Rito
Abstract
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 is relative to a
benchmark application (e.g. confidential communication): Does the use
of a PKE scheme satisfying 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.