Interactive Encryption and Message Authentication?

Yevgeniy Dodis1 and Dario Fiore2??

1
Department of Computer Science, New York University, USA
dodis@cs.nyu.edu
2
IMDEA Software Institute, Madrid, Spain
dario.fiore@imdea.org

Abstract. Public-Key Encryption (PKE) and Message Authentication (PKMA, aka as digital signatures)
are fundamental cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e.,
single-message). In this work, we initiate rigorous study of (possibly) interactive PKE and PKMA schemes.
We obtain the following results demonstrating the power of interaction to resolve questions which are either
open or impossible in the non-interactive setting.

Efficiency/Assumptions. One of the most well known open questions in the area of PKE is to build,
in a “black-box way”, so called chosen ciphertext attack (CCA-) secure PKE from chosen plaintext attack
(CPA-) secure PKE. In contrast, we show a simple 2-round CCA-secure PKE from any (non-interactive)
CPA-secure PKE (in fact, these primitives turn out to be equivalent). Similarly, although non-interactive
PKMA schemes can be inefficiently built from any one-way function, no efficient signature schemes are known
from many popular number-theoretic assumptions, such as factoring, CDH or DDH. In contrast, we show
an efficient 2-round PKMA from most popular assumptions, including factoring, CDH and DDH.

Advanced Properties. It is well known that no non-interactive signature (resp. encryption) scheme can
be deniable (resp. forward-secure), since the signature (resp. ciphertext) can later “serve as an evidence
of the sender’s consent” (resp. “be decrypted if the receiver’s key is compromised”). We also formalize
a related notion of replay-secure (necessarily) interactive PKMA (resp. PKE) schemes, where the verifier
(resp. encryptor) is assured that the “current” message can only be authenticated (resp. decrypted) by the
secret key owner now, as opposed to some time in the past (resp. future). We observe that our 2-round
PKMA scheme is both replay-secure and (passively) deniable, and our 2-round PKE scheme is both replay-
and forward-secure.

Keywords: Public Key Encryption, Digital Signatures, Chosen Ciphertext Security, Man-in-the-Middle
Attacks.
?
An extended abstract of this work appears in the proceedings of SCN 2014. This is the full version.
??
Work partially done while postdoc at NYU.
 Table of Contents

Interactive Encryption and Message Authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Yevgeniy Dodis and Dario Fiore
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Preliminaries and Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Organization of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Defining Message Transmission Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Interactive Chosen-Ciphertext-Secure Encryption. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Interactive Chosen-Message Secure Public Key Message Authentication. . . . . . . . . . . . . . . 7
3 Basic Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 iCCA Encryption from IND−CPA Encryption and iCMA PKMA . . . . . . . . . . . . . . . . . . . . . . 7
3.2 iCMA-secure PKMA from iCCA security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Secure Round Extension of Message Transmission Protocols . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Advanced Security Properties from the Power of Interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1 Deniability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Forward Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.3 Replay Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A Standard Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
A.1 (Non-Interactive) CCA-secure Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
A.2 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A.3 Message Authentication Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
B DDN 3-round iCCA-Secure Encryption from IND−CPA Security . . . . . . . . . . . . . . . . . . . . . . . . . . 24
C A 1-bounded IND−CCA-Secure Encryption Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
D iCCA-Secure Interactive Encryption with Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
E iCMA-secure PKMA from labeled iCCA-secure encryption. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
F Postponed Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
F.1 Proof of Claim 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
F.2 Proof of Theorem 3 (iCCA security) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
F.3 Proof of Theorem 3 (iCMA security) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1 Introduction

Digital signatures and public-key encryption (PKE) schemes are two of the most fundamental and well
studied cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e., single
message). Aside from obvious convenience — both the sender and receiver need not keep any state —
such non-interactive “one-and-done” philosophy is also critical in many applications. Coupled with the
fact that we now have many (often efficient) candidates for both signature and encryption schemes, it
might appear that there is little value in extending the syntax of signature/encryption schemes to allow
for (possibly) interactive realizations.
In this work we challenge this point of view, and initiate rigorous study of (possibly) interactive sig-
nature and public-key encryption schemes. For the former, we will actually use the term Public-Key Mes-
sage Authentication (PKMA) scheme, as the term “signature” often comes with expectations of “non-
repudiation”, which is orthogonal to the standard notion of “unforgeability” the moment interaction is
allowed. First, although we agree that some applications might critically rely on the non-interactivity of
PKE/PKMA schemes, we believe that many other applications, including arguably the most basic one
of sending/receiving private/authentic messages, might not so be fixated on non-interactivity. For such
applications, it appears natural to allow the sender and the receiver to interact, especially if they are
involved in a conversation anyway.
Second, in this work we will show that, by allowing a single extra message (i.e., a 2-round pro-
tocol), we can “resolve” two arguably most important open problems in the area of non-interactive
PKE/PKMA schemes:3 (a) “black-box” 2-round chosen-ciphertext attack (CCA-) secure PKE from
any (non-interactive) chosen-plaintext attack (CPA-) secure PKE; (b) efficient 2-round strongly un-
forgeable PKMA scheme from a variety of simple assumptions, such as factoring and DDH.
Third, we point out several useful advanced properties of PKE/PKMA schemes which are impossible
to achieve without interaction. While some of these properties (such as deniable PKMA [19,21,20,15])
were already extensively studied in the past, most others (such as interactive forward-secure PKE, and
replay-secure PKE/PKMA) appear to be new.
Related Work. Although our work is the first to offer a detailed and comprehensive study of
interactive PKE/PKMA schemes, it is certainly not the first to consider these notions. The most related
prior work in this regard is the famous “DDN-paper” on non-malleable cryptography [18,19]. This
seminal work had many extremely important and influential results. Among them, it also considered
non-malleable, interactive encryption and authentication, and briefly sketched4 elegant constructions
for both primitives. We discuss more in detail the relation with our work in the next section, when we
describe our improvements over the DDN paper.
To the best of our knowledge, the only other work providing a related definition (only for encryption)
is the one of Katz [29]. However, our definition is stronger, as we place more restriction on the attacker
to declare that the attacker ‘acts as a wire’. Moreover, the solutions given in [29] use so called timing
assumptions, while our constructions are in the standard model.

1.1 Our Results

We now describe our motivations and results in more detail.
Definitional Framework. Our first goal was to extend the short and elegant definitions of non-
interactive encryption/signatures to the interactive setting, without making the definitions long and
tedious. Unfortunately, in the interactive setting things are more complicated, as issues of concurrency
3
Of course, we obtain this by changing the model to allow for interaction, which is the reason for the quotation marks.
4
Due to the massive scope of [19], the DDN paper did not give formal definitions and proofs for the encryption re-
sults (saying they are “outside the scope” of their paper; see page 32), and only sketched the definition/proof for the
authentication case.

1
and state, among others, must be dealt with. The way we managed to achieve our goal, was to split
our definitions into two parts. The first (somewhat boring) part is independent of the particular prim-
itive (e.g., PKE/PKMA), and simply introduces the bare minimum of notions/notation to deal with
interaction. For example (see Section 2 for details), we define (a) what it means to have (concurrent)
oracle access to an interactive party under attack; and (b) what it means to ‘act as a wire’ between
two honest parties (for brevity, we call this trivial, but unavoidable, attack a ‘ping-pong’ attack). Once
the notation is developed, however, our actual definitions of possibly interactive PKE/PKMA are as
short and simple as in the non-interactive setting (see Definitions 5 and 6). E.g., in the PKMA setting
(Definition 6) the attacker A has (concurrent) oracle access to the honest signer (as defined in (a)), and
simultaneously tries to convince an honest verifier (i.e., “challenger”). A wins if the challenger accepts,
and A’s forgery was not a ‘ping-pong’ of one of its conversations with the signer (as defined in (b)).5
Overall, the definition consists of the same couple of lines as in the non-interactive setting! And the same
holds for the encryption case in Definition 5, which naturally generalizes the notion of CCA-security to
the interactive setting.

Better Efficiency/Assumptions via Interaction. Turning from definitions to constructions,

we show how a single extra round of interaction (i.e., a 2-round protocol) can help “solve” (in a sense
explained in Footnote 3) two of the arguably toughest open problems in the areas of non-interactive
PKE and PKMA, respectively.
In the area of PKE, the question is to build a CCA-secure PKE from a CPA-secure PKE. In principle,
such constructions are known using an appropriately-chosen notion of non-interactive zero-knowledge
proofs [19,36,37,39,31]. However, all these constructions are generally inefficient and considered some-
what unsatisfactory, since they use the code of the given CPA-secure encryption scheme. In particular,
the question of finding so called black-box constructions of CCA-encryption from CPA-encryption re-
mains open. In fact, although several partial progress along both positive (e.g., [12,11,32]) and negative
(e.g., [25]) fronts was made, the general question remains elusive. In contrast, we show a relatively
simple, black-box, 2-round CCA-secure encryption from CPA-secure encryption (in fact, the two prim-
itives are equivalent). We notice that the DDN paper [19] itself already made a similar conclusion, by
presenting a 3-round black-box protocol from any CPA-secure PKE.6 Thus, aside from presenting a
formal model for interactive CCA-secure encryption, our result can be viewed as improving the round
efficiency of the DDN paper from 3 to 2.
In the area of PKMA, the “theory” question was settled pretty quickly, by showing that the strongest
security notion for signature schemes — strong existential unforgeability against chosen message attack
— can be realized assuming the mere existence of one-way functions [26,35,3,4,38]. Unfortunately,
the generic constructions were primarily of theoretical interest, and did not result in practical enough
signature schemes. In fact, practical signature schemes (outside of the random oracle model [7,23,40,27])
are only constructed from a handful of “not-too-standard” number-theoretic assumptions, such as ‘strong
RSA’ [14,24] and ‘Bilinear-Diffie-Hellman’ [41], and even these ‘practical’ constructions were generally
somewhat slow, requiring generation of primes, long keys or bilinear maps. In particular, one of the
main open questions is to build an efficient digital signature scheme from a standard assumption, such
as factoring, CDH or DDH.
In contrast, we show very efficient, 2-round, strongly unforgeable PKMA schemes from virtually all
standard assumptions, including factoring, CDH and DDH. In fact, although we are not aware of any
paper explicitly claiming this result, it follows in a relatively simple manner by combining various prior
works.7 Let us explain. With a different motivation in mind, the DDN paper [19] showed a simple 3-

5
This generalizes the notion of strong unforgeability, as opposed to regular unforgeability, as was done in DDN [19].
6
Although they do not give a formal definition/proof, their construction is easily seen to be secure in our model (see
Appendix B).
7
Except only establishing regular unforgeability, but the actual constructions are easily seen to be strongly unforgeable.

2
round8 PKMA scheme from any CCA-secure encryption. At the time, CCA-secure PKE was considered
a very ‘advanced’ primitive, so the construction was not considered ‘efficient’. Over the years, though,
many truly efficient CCA-secure schemes were constructed from virtually all popular assumptions,
including factoring [28], CDH [42] and DDH [13] (despite the fact that no such efficient signature
schemes are known from these assumptions!). Thus, these results, if combined, immediately yield an
efficient 3-round PKMA from all these assumptions. Moreover, it is well known (e.g., see [30,1]) that
one can reduce the number of rounds from 3 to 2 by also using a message authentication code (MAC),
in addition to CCA-secure encryption. Of course, in theory, a MAC is implied by a CCA-secure PKE,
albeit in an inefficient manner. Moreover, until recently, even direct efficient MAC constructions from
concrete assumptions, such as DDH [33] and factoring [34], required long keys (quadratic in security
parameter). Fortunately, Dodis et al. [17] recently observed an elementary efficient (probabilistic) MAC
construction from any CCA-secure scheme. This gives an efficient 2-round PKMA scheme from any
CCA-secure encryption. We also manage to further optimize the resulting construction, and obtain a
really simple (new!) 2-round protocol, depicted in Figure 3. In turn, this gives efficient 2-round PKMA
from a variety of standard assumptions, including factoring, CDH and DDH.9

Duality between Interactive PKE and PKMA. Interestingly, our 2-round CCA-secure PKE uses
a signing key as its long-term “decryption secret” (and generates several ephemeral keys for the CPA-
secure scheme), while our 2-round strongly unforgeable PKMA scheme uses a decryption key for a CCA-
secure encryption as its long term “authentication secret”. We show that this duality is not a coincidence.
In fact, our 2-round results follow as corollaries of two more general schemes, depicted in Figures 1
and 2: an interactive CCA-secure scheme from any (interactive or not) strongly unforgeable PKMA
scheme (plus any CPA-secure PKE10 ), and an interactive strongly unforgeable PKMA scheme from
any (interactive or not) CCA-secure PKE. The ‘duality’ of our results (authentication using encryption
and vice-versa) shows that, perhaps, the practical/theoretical distinction between interactive encryption
and authentication is not as great as one could have guessed by looking at what is known in the non-
interactive setting.

Overcoming Impossibility Results. We also show that our simple definitional framework (one
generic/reusable ‘long-and-boring’ part followed by many application-specific ‘short-and-intuitive’ parts)
easily lends itself to various extensions. Examples include various notions of privacy and/or authenticity
which are impossible in the non-interactive setting, such as forward-secure PKE and the notion of replay-
secure PKE/PKMA that we introduce in this work.

1.2 Preliminaries and Notation.

We denote by λ ∈ N the security parameter. A function (λ) is said negligible if it is a positive function
$
that vanishes faster than the inverse of any polynomial in λ. If X is a set, let x ← X denote the
process of selecting x uniformly at random in X. An algorithm A is called P P T if it is a probabilistic
Turing machine whose running time is bounded by some polynomial in λ. If A is a PPT algorithm,
$
then y ← A(x) denotes the process of running A on input x and assigning its output to y. Definitions
of standard cryptographic primitives are recalled in Appendix A.

8
The construction becomes 2-round if the verifier knows the authenticated message in advance.
9
Of course, in practice one should not use CCA-secure encryption to build a MAC (instead, one should use practical MACs
such as CBC-MAC or HMAC), but here we use it to establish efficient feasibility results from concrete number-theoretic
assumptions.
10
For the sake of elegance and modularity, we use a slightly stronger notion of so called “1-bounded CCA-secure PKE”,
but the latter can be built from any CPA-secure PKE [12].

3
1.3 Organization of the paper

The paper is organized as follows. In Section 2 we introduce our definitional framework for message
transmission protocols with the security notions of (possibly interactive) iCCA-secure PKE and iCMA-
secure PKMA. Next, in Section 3, we focus on realizations of these protocols, notably, iCCA-secure
PKE from iCMA-secure PKMA and CPA-secure encryption, and iCMA-secure PKMA from iCCA-secure
PKE. Finally, Section 4 discusses advanced security properties for (interactive) PKE and PKMA. We
postpone to the appendix the definitions of standard cryptographic primitives (Appendix A), the 3-round
interactive encryption of Dolev, Dwork and Naor [19], the construction of a 1-bounded-IND−CCA-secure
PKE scheme from an IND−CPA-secure one (Appendix C), the extension of (interactive) PKE to support
“labels” and its application to PKMA (Appendices D–E), and a few simple proofs (Appendix F).

2 Defining Message Transmission Protocols

In this section we introduce message transmission protocols: we define their syntax as well as suitable
notions of confidentiality (called iCCA security) and authenticity (called iCMA security).
We give a generic definition of message transmission protocols involving two parties: a sender S and a
receiver R, such that the goal of S is to send a message m to R while preserving certain security properties
on m. In particular, in the next two sections we consider arguably the most basic security properties: the
confidentiality/authenticity of the messages sent by S to R. Formally, a message transmission protocol
Π consists of algorithms (Setup, S, R) defined as follows:

Setup(1λ ): on input the security parameter λ, the setup algorithm generates a pair of keys (sendk, recvk).
In particular, these keys contain an implicit description of the message space M.
S(sendk, m): is a possibly interactive algorithm that is run with the sender key sendk and a message
m ∈ M as private inputs.
R(recvk): is a possibly interactive algorithm that takes as private input the receiver key recvk, and
whose output is a message m ∈ M or an error ⊥.

When S and R are jointly run, they exchange messages in a specific order, e.g., S starts by sending M1 ,
R sends M2 , S sends M3 , and so on and so forth until they both terminate. We say that Π is an n-round
protocol if the number of messages exchanged between S and R during a run of the protocol is n. If Π is
1-round, then we say that Π is non-interactive. Since the sender gets no output, we assume without loss
of generality that the sender always speaks last. 11 Thus, in an n-round protocol, R (resp. S) speaks first
if n is even (resp. odd). For compact notation, we denote with hS(sendk, m), R(recvk)i = m0 the process
of running S and R on inputs (sendk, m) and recvk respectively, and assigning R’s output to m0 . In our
notation, we will use m ∈ M for messages (aka plaintexts), and capital M for protocol messages.

Definition 1 (Correctness). A message transmission protocol Π = (Setup, S, R) is correct if for all

$
honestly generated keys (sendk, recvk) ← Setup(1λ ), and all messages m ∈ M, we have that hS(sendk, m),
R(recvk)i = m holds with all but negligible probability.

Defining Security: Man-in-the-Middle Adversaries. In our work, we assume that the sender and
the receiver speak in the presence of powerful adversaries that have full control of the communication
channel, i.e., the adversary can eavesdrop the content of the communication, and it can stop/delay/alter
the messages passing over the channel. Roughly speaking, the goal of an adversary is to violate a given
security property (say confidentiality or authenticity) in a run of the protocol that we call the challenge
11
This holds wlog because if Π is an n-round protocol in which R sends the last message, then we can construct an
(n − 1)-round protocol Π0 by simply dropping the last message from R to S (and that part of the code of R generating
the last message is run internally).

4
session. Formally, this session is a protocol execution hS(sendk, m), AR(recvk) i or hAS(sendk,·) , R(recvk)i
where the adversary runs with a honest party (S or R). By writing AP , we mean that the adversary has
oracle access to multiple honest copies of party P (where P = R or P = S), i.e., A can start as many
copies of P as it wishes, and it can run the message transmission protocol with each of these copies. This
essentially formalizes the fact that the adversary can “sit in the middle of two honest parties” relaying
messages between them in an active way. Sometimes, we also write APk to denote that the adversary
can start at most k copies of party P. In our model we assume that whenever A sends a message to
the oracle P, then A always obtains P’s output. In particular, in the case of the receiver oracle, when
A sends the last protocol message to R, A obtains the (private) output of the receiver, i.e., a message
m or ⊥.
Since all these protocol sessions can be run in a concurrent way, the adversary might entirely re-
play the challenge session by using its oracle. This is something that we would like to prevent in our
definitions. To formalize this idea, we take an approach similar to the one introduced by Bellare and
Rogaway [6] in the context of key exchange, which is based on the idea of “matching conversations”.
First of all, we introduce a notion of time during the execution of the security experiment. We stress
that this is done for ease of analysis of the security model: there is no need to keep track of global
timing in the real protocols. Let t be a global counter which is progressively incremented every time a
party (including the adversary) sends a message, and assume that every message sent by a party (S,
R or A) gets timestamped with the current time t. Note that this includes all messages of the sessions
established by the adversary using its oracle. Using this notion of time, we define the transcript of a
protocol session as follows:

Definition 2 (Protocol Transcript). The transcript of a protocol session between two parties is the
timestamped sequence of messages exchanged by the parties during a run of the message transmission
protocol Π. If Π is n-round, then a transcript T is of the form T = h(M1 , t1 ), . . . , (Mn , tn )i, where M1 ,
. . . , Mn are the exchanged messages, and t1 , . . . , tn are the respective timestamps.

In a protocol run hS(sendk, m), AR(recvk) i (resp. hAS(sendk,·) , R(recvk)i) we have a transcript T ∗ of the
challenge session between S and A (resp. A and R), and Q transcripts T1 , . . . , TQ , one for each of the Q
sessions established by A with R (resp. S) via the oracle.
While we postpone to the next two sections the definition of specific security properties of message
transmission (e.g., confidentiality and authenticity), our goal here is to formalize in a generic fashion
which adversaries are effective for “uninteresting”/unavoidable reasons. Namely, when the challenge
session is obtained by entirely replaying one of the oracle sessions: what we call a “ping-pong” attack,
that we formalize via the following notion of matching transcripts.

Definition 3 (Matching Transcripts). Let T = h(M1 , t1 ), . . . , (Mn , tn )i and T ∗ = h(M1∗ , t∗1 ), . . . ,

(Mn∗ , t∗n )i be two protocol transcripts. We say that T matches T ∗ (T ≡ T ∗ , for short) if ∀i = 1, . . . , n,
Mi = Mi∗ and the two timestamp sequences are “alternating”, i.e., t1 < t∗1 < t∗2 < t2 < t3 < · · · <
tn−1 < tn < t∗n if R speaks first, or t∗1 < t1 < t2 < t∗2 < t∗3 < · · · < tn−1 < tn < t∗n if S speaks first. We
remark that the notion of match is not commutative.

Given all the definitions above, we can define the notion of ping-pong adversary:

Definition 4 (Ping-pong Adversary). Consider a run of the protocol Π involving A and a honest
party (it can be either hS(sendk, m), AR(recvk) i or hAS(sendk,·) , R(recvk)i), and let T ∗ be the transcript of
the challenge session, and T1 , . . . , TQ be the transcripts of all the oracle sessions established by A. Then
we say that A is a ping-pong adversary if there is a transcript T ∈ {T1 , . . . , TQ } such that T matches
T ∗ , i.e., T ≡ T ∗ .

5
2.1 Interactive Chosen-Ciphertext-Secure Encryption.

Here we propose a suitable notion of confidentiality for message transmission protocols that we call
interactive chosen ciphertext security (iCCA). Our notion is designed as a very natural generalization
of the classical notion of IND−CCA security to the interactive setting. In fact, IND−CCA security is
a special case of iCCA security for 1-round (i.e., non-interactive) protocols (we leave this check to the
reader). Roughly speaking, in the IND−CCA definition the adversary has to distinguish whether a given
“challenge” ciphertext encrypts a message m0 or m1 while having access to a decryption oracle. To
make the definition non-trivial, the adversary is denied to query the decryption oracle on the challenge
ciphertext. Our notion of iCCA security is obtained similarly: the adversary A interacts with a sender
which sends either m0 or m1 and A has to tell the two cases apart while having access to the receiver
(instead of the decryption oracle); the restriction on the challenge ciphertext is replaced by requiring
that A cannot be ping-pong. The formal definition follows.
Let Π = (Setup, S, R) be a message transmission protocol and A be an adversary. To define iCCA
security, consider the following experiment:

Experiment ExpiCCA
Π,A (λ)
$
b ← {0, 1}
$
(sendk, recvk) ← Setup(1λ )
(m0 , m1 )←AR(recvk) (sendk)
b0 ←hS(sendk, mb ), AR(recvk) (sendk)i
If b0 = b and A is not “ping-pong”, then output 1. Else output 0.

Definition 5 (iCCA security). For any λ ∈ N, we define the advantage of an adversary A in breaking
iCCA security of a message transmission protocol Π as AdviCCA iCCA 1
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] − 2 , and we
iCCA
say that Π is iCCA-secure if for any PPT A, AdvΠ,A (λ) is negligible. We call a message transmission
protocol satisfying this notion an interactive encryption scheme.

As we mentioned in the introduction, it is worth noting that our definition is similar to the one
proposed by Katz in [29]. The main difference is in the restrictions applied to the adversary in the
security game. In [29] this is realized by means of a notion of “equality of transcripts” which considers
only equality of messages (in the same order) and leaves any time constraint to the specific protocols
realizations. Our security definition, instead, directly takes into account time constraints in the security
experiment via the notion of matching transcripts. To see the difference between the two definitions
with an example, consider an adversary who creates an oracle session having the same transcript as the
one of the challenge session, but where the timestamps of the messages are not correctly alternating.
Such an adversary would not be legal according to the definition of [29], but is legal (i.e., not ping-pong)
according to ours.
Later, in Section 4.3, we strengthen our requirements by considering an orthogonal security property
for interactive encryption that we call “Replay Security”. This will allow to model MiM attacks more
easily and from a different perspective. It will also turn out to be realizable under our basic iCCA notion.
However, since a replay attack is always possible in any non-interactive solution, replay security will
only be realizable by an interactive protocol.
q-bounded-iCCA Security. In this work we also consider a weaker notion of iCCA security, called
q-bounded-iCCA, in which the adversary is restricted to complete at most q sessions with the oracle R,
i.e., in ExpiCCA Rq
Π,A (λ) we run A . This is the analogous of (non-interactive) q-bounded IND−CCA security
[12].
Labeled (Interactive) Encryption. We define an extension of interactive encryption in which both
the sender and the receiver algorithms take a public string—a label—as an additional input (similarly

6
to the non-interactive setting [8]). Very intuitively, the idea is that the receiver working with label L
decrypts correctly only if the sender works with the same label L. In Appendix D we provide a full
formalization of labeled iCCA encryption and show that it can be generically constructed from ‘plain’
iCCA-secure encryption. Here we briefly recall that for any label L we use SL to denote that an algorithm
S takes as input L.

2.2 Interactive Chosen-Message Secure Public Key Message Authentication.

Here we propose a suitable notion of authenticity for message transmission protocols that we call
interactive unforgeability under chosen message attacks (iCMA). Our notion is designed as a very natural
generalization to the interactive setting of the standard notion of strong unforgeability (suf-cma) for
digital signatures. In fact, suf-cma security is a special case of iCMA security for 1-round protocols.
Roughly speaking, in strong unforgeability the adversary has to produce a valid signature while having
access to the signer. In order for the definition to be non-trivial, however, such signature has to be “new”,
i.e., not obtained from the signing oracle. Our notion of iCMA security naturally extends suf-cma as
follows: the adversary A has to convince a receiver while having oracle access to the sender (instead of
the signing oracle); the requirement that the signature must be new is replaced by requiring that A is
not ping-pong. The formal definition follows.
Let Π = (Setup, S, R) be a message transmission protocol and A be an adversary. To define iCMA
security, consider the following experiment:
Experiment ExpiCMA
Π,A (λ)
$
(sendk, recvk) ← Setup(1λ )
m∗ ←hAS(sendk,·) (recvk), R(recvk)i
If m∗ 6= ⊥ and A is not “ping-pong”, then output 1. Else output 0.

Definition 6 (iCMA security). For any λ ∈ N, the advantage of A in breaking the iCMA security of
a message transmission protocol Π is AdviCMA iCMA
Π,A (λ) = Pr[ExpΠ,A (λ) = 1], and we say that Π is iCMA-
secure if for any PPT A, AdviCMA
Π,A (λ) is negligible. We call a message transmission protocol satisfying
this notion a public key message authentication (PKMA) protocol.

Later, we further motivate the importance of interactive PKMA protocols by considering additional
security notions that can be realized only in the interactive setting. This is the case for our notion
of Replay Security (see Section 4.3), and for the deniability property (see Section 4.1). The former
notion intuitively captures the idea of obtaining security by denying the adversary to access the sender
oracle during the challenge session. Deniability, instead, allows the authenticator to deny his active
participation in a protocol, i.e., it denies the verifier to transfer the information authenticated by S.

3 Basic Constructions

In this section we propose realizations of message transmission protocols satisfying our iCCA and iCMA
security notions. Interestingly, our constructions show that iCCA security is implied by the iCMA and
IND−CPA notions, whereas (somehow vice-versa) iCMA security is directly implied by iCCA. Our results
thus show that in the interactive setting—and with a minimum level of interaction (i.e., 2 rounds)
indeed!—the notions of confidentiality and authenticity present somewhat surprising and interesting
relations unknown in the non-interactive case.

3.1 iCCA Encryption from IND−CPA Encryption and iCMA PKMA

Our result is a simple interactive encryption protocol that is based on a PKMA protocol Π0 and a public
key encryption scheme E = (KG, Enc, Dec). The idea is simple and is illustrated in Figure 1: the receiver

7
 Setting: a key pair (sendk0 , recvk0 ) for an iCMA-secure protocol Π0 is gen-
erated.
S(recvk0 , m) R(sendk0 )
0
R sends ek to S using Π
0 $
Get ek  (ek, dk) ← KG(1λ )

If ek0 6= ⊥ : c = Enc(ek0 , m) - m0 ←Dec(dk, c)

Fig. 1. iCCA protocol from iCMA-secure PKMA and 1-bounded-IND−CCA

encryption.

sends a “fresh” public key ek authenticated using Π0 , and the sender encrypts the message using ek.
As we show in our theorem below, the PKMA protocol has to be iCMA-secure, while the PKE scheme
E needs only to be 1-bounded-IND−CCA-secure. Concretely, Π0 can be a strongly unforgeable signature
and E can be constructed using an IND−CPA-secure encryption (as shown by Cramer et al. [12] and
recalled in Appendix C), thus yielding an optimal 2-round encryption protocol that is iCCA-secure based
only on IND−CPA security. A more precise description follows.
Let Π0 = (Setup0 , S0 , R0 ) be a PKMA protocol, and E = (KG, Enc, Dec) be a (non-interactive) public
key encryption scheme. We build protocol Π = (Setup, S, R) as follows:

Setup(1λ ): run (sendk0 , recvk0 ) ← Setup0 (1λ ) and output sendk = recvk0 and recvk = sendk0 .
$

S(sendk, m): first run the PKMA protocol Π0 with R by playing the role of the receiver, i.e., S runs
R0 (recvk0 ). If Π0 terminates correctly with output ek, then send c = Enc(ek, m) to R. Otherwise, stop
running.
R(recvk): generate (ek, dk) ← KG(1λ ), run S0 (sendk0 , ek) to send ek with authenticity to S, and keep dk
$

as private information. After Π0 terminates, on input a message c from S, the receiver algorithm
computes m←Dec(dk, c) and returns the message m as its private output.

Theorem 1. If E is 1-bounded-IND−CCA-secure and Π0 is iCMA-secure, then Π is iCCA-secure.

Proof. Consider the experiment ExpiCCA ∗

iPKE,A in which T1 , . . . , TQ and T are the transcripts of the oracle
sessions and the challenge session. Each transcript T can be written as T = (T 0 , Tc ) such that T 0 is
the transcript of the PKMA protocol Π0 and Tc is the portion containing the last message c. Let Forge
be the event that in ExpiCCA 0 0 ∗0
iPKE,A the adversary A is not ping-pong in the subprotocol Π (i.e., Ti 6≡ T
∀i = 1, . . . , Q), and that in the challenge session the sender accepts (i.e., R0 terminates correctly returning
ek∗ 6= ⊥). It is not hard to see that

1
AdviCCA iCCA
A,Π (λ) ≤ Pr[ExpiPKE,A = 1 | Forge] − + Pr[Forge].
2
The security of our protocol then follows from showing that: (1) Forge occurs with negligible probability
under the assumption that Π0 is iCMA-secure, and (2) if Forge does not occur, then any adversary
winning in ExpiCCA
iPKE,A can be used to break the 1-bounded-IND−CCA security of the encryption scheme.
We formally prove these facts in the following claims.

Claim 1 If Π0 is iCMA-secure, then Pr[Forge] is negligible.

Claim 2 If E is 1-bounded IND−CCA-secure, then Pr[ExpiCCA

iPKE,A = 1 | Forge] −
1
2 is negligible.

The proof of Claim 1 is straightforward and appears in Appendix F.1. The proof of Claim 2 is given
below.

8
Proof (Claim 2). Assume by contradiction there exists an efficient adversary A such that
1
Pr[ExpiCCA
Π,A (λ) = 1 | Forge] − ≥
2
is non-negligible. Then we build a PPT adversary B that has non-negligible advantage in breaking the
1-bounded-IND−CCA security of the encryption scheme E = (KG, Enc, Dec).
¯ B works as follows:
On input a public key ek,

– Generate a key pair sendk0 , recvk0 ) ← Setup0 (1λ ), set sendk = recvk0 and run A(sendk).
$

– Initialize a counter j←0 for the number of new sessions opened by A with R during the experiment.
$
– Choose a random index µ ← {1, . . . , Q} where Q = poly(λ) is an upper bound on the number of
sessions opened by A with the oracle receiver R. Since Forge does not occur, A is ping-pong in the
subprotocol Π0 and thus in the challenge session A will re-use one of the public keys ek1 , . . . , ekQ
obtained by the oracle R. Therefore, µ represents a guess for the index of such public key ekµ .
– For every oracle query asking to interact with a new copy of R: first, increment j by 1. Now, let j
$
be the index of the current query. If j 6= µ, then B generates a new encryption key pair ekj , dkj ) ←
KG(1λ ), and runs S0 (sendk0 , ekj ) to simulate all the oracle answers of this session corresponding to
¯ and runs S0 (sendk0 , ek).
the run of Π0 . Otherwise, if j = µ, it sets ekµ = ek, ¯
– When A queries R with the last protocol message ci on the i-th opened session: let eki be the public
key previously generated in the above step. If i 6= µ, then B knows the corresponding decryption
key dki , (B generated it by itself), and it answers by computing mi ←Dec(dk, ci ). If i = µ, B asks ci
to the decryption oracle, obtains m̃, and answers m̃. Notice that for i = µ such a query can occur
only once, as ci is the last message of the protocol (the session is then closed).
– Let (m0 , m1 ) be the message pair returned by the adversary A. Then the challenge session starts
and A is expected to “speak first”, by sending ek∗ using Π0 . Since Forge does not occur, we have that
either ek∗ = ⊥, or ek∗ 6= ⊥ and A is ping-pong, i.e., ek∗ ∈ {ek1 , . . . , ekQ }. In the first case B returns
an error (this is a correct simulation by protocol’s construction). In the second case: if ek∗ 6= ekµ ,
then B aborts the simulation and outputs a random bit. Otherwise, it continues as described below.
B forwards (m0 , m1 ) to its challenger, gets back a ciphertext c∗ , and sends c∗ to A in the challenge
session.
– B answers oracle queries as before.
– Finally, let b0 be A’s output, then B outputs the same bit.
Let Abort be the event that B aborts during the experiment. If Abort occurs, then Pr[Exp1−IND−CCA
E,B (λ) =
1 | Abort] = 1/2. Moreover, as long as Abort does not occur the distribution of the public keys simulated
by B is identical to the one in the real experiment, and thus the index µ is perfectly hidden. Hence, we
have that Pr[Abort] = 1/Q and
 
1 1
Adv1−IND−CCA
E,B (λ) ≥ · Pr[Exp 1−IND−CCA
E,B (λ) = 1 | Abort] − .
Q 2
To complete the proof we show that in the case Abort does not occur B’s simulation of the iCCA
game to A is perfect. In particular, we show that as long as A is not ping-pong (as it must be by
definition of iCCA security) B can answer correctly to all queries made by A. Precisely, the tricky case
that needs to be checked is that B can answer with the correct decryption when the adversary sends
the last message on sessions that were already opened. Let T = (T 0 , Tc ) be the transcript of the queried
0
session where ek is the corresponding public key and c is the ciphertext sent by A, and let T ∗ = (T ∗ , Tc∗ )
0
be the transcript of the challenge session. If T 0 6≡ T ∗ , it essentially means that B generated ek and thus
0
it can decrypt. If T 0 ≡ T ∗ , since A is not ping-pong, then it must be that either (I) c 6= c∗ (in this
case B forwards c to the decryption oracle), or (II) c = c∗ and the corresponding timestamps are not
alternating, i.e., t∗n > tn , that is c was sent before B asked (and sent) the challenge ciphertext. Thus B

9
could have asked c to its decryption oracle recall that in the 1-bounded-IND−CCA game such decryption
query is legal.
In conclusion, we obtain: Adv1−IND−CCA
E,B (λ) ≥ Q . t
u

As an interesting consequence of Theorem 1 we obtain an equivalence between the notions of

IND−CPA and iCCA security:
Corollary 1. 2-round-iCCA encryption exists if and only if (non-interactive) IND−CPA PKE exists.

Proof. The first direction (IND−CPA ⇒ 2-round-iCCA) follows by observing that: (i) 1-bounded-IND−CCA
is implied by IND−CPA security (see [12] and Appendix C); (ii) iCMA security can be realized using
digital signatures, and thus from one-way functions (see our Corollary 3). The second direction follows
from the following simple Lemma:
Lemma 1. 2-round-iCCA ⇒ IND−CPA

Proof. Let Π = (Setup, S, R) be a 2-round iCCA protocol (recall that wlog we assume that R speaks
first). We construct a non-interactive encryption scheme E = (KG, Enc, Dec) from Π as follows:
$ $
KG(1λ ): run (sendk, recvk) ← Setup(1λ ), and (R; ρ) ← R(recvk) where we denote with R the message
sent by R, and by ρ its private coins. Output ek = (sendk, R) and dk = (recvk, ρ).
Enc(ek, m): run the sender algorithm S(sendk, m) with input message R. Let C be the message generated
by S. Output C as the ciphertext.
Dec(dk, C): run m←R(DK) with input message C and private random coins ρ, and output m.

Proof of Security. Assume there exists an efficient A that breaks the IND−CPA security of E with
non-negligible advantage , i.e., AdvIND−CPA
A,E (λ) ≥ . We build an adversary B that uses A to obtain
non-negligible advantage in breaking the iCCA security of protocol Π. B is run on input the public
sender key sendk and has oracle access to R. First, B queries R(recvk) to start a new session, and it
$
obtains R. B sets ek = (sendk, R) and runs (m0 , m1 ) ← A(ek). B outputs the same pair of messages, and
then runs the challenge session with S(sendk, mb ), to which it sends R and receives C ∗ back. B finally
$
runs b0 ← A(C ∗ ) and outputs the same bit b0 . It is easy to see that the simulation of the IND−CPA
IND−CPA
experiment is perfect, and thus AdviCCA
B,Π (λ) = AdvA,E (λ) ≥ . t
u

For the case of non-interactive public key encryption, it is an open problem to understand whether
the notion of IND−CPA security implies the one of IND−CCA security (in a fully black-box sense), and
there have been provided some evidences that it may not be the case [25]. In contrast, our result shows
that by adding a single round of communication the basic notion of IND−CPA-security is sufficient to
realize 2-round iCCA-secure encryption.
It is worth noting that a 3-round encryption protocol based on IND−CPA encryption was earlier
proposed by Dolev, Dwork and Naor [19]. While the protocol in [19] can be proven in our formalization
of interactive encryption (see Appendix B), our contribution is a protocol which is optimal (2 rounds)
and is based on the same weaker assumption (IND−CPA security).

3.2 iCMA-secure PKMA from iCCA security

We show how to realize iCMA-secure message transmission from any message transmission protocol that
is iCCA-secure, and any strongly unforgeable MAC. The protocol is based on an old idea of realizing
public key authentication via CCA-secure encryption and message authentication codes. The basic
idea is that the authenticator shows its ability to decrypt: the verifier encrypts a MAC key r for the
authenticator, who decrypts and sends back the MAC of message m using the key r. This protocol (briefly
sketched in Figure 2) implicitly appeared first in [30] and was proven secure in [1]. Here we generalize

10
 Setting: generate a key pair (sendk0 , recvk0 ) for an iCCA protocol Π0 .

S(recvk0 , m) R(sendk0 )
0 $
R sends r to S using Π r ← Gen(1λ )
0
Get r 
If Ver(r, m, σ) = 1 :
m, σ = Tag(r0 , m) - return m.

Fig. 2. iCMA protocol from iCCA-secure encryption and MACs.

this construction in the framework of our definitions, i.e., by using (possibly interactive) iCCA-secure
encryption in place of (non-interactive) IND−CCA-secure encryption. Furthermore, in Appendix E we
generalize a 3-round protocol earlier proposed by Dolev, Dwork and Naor [19] that is based only on
iCCA security.
Let MAC = (Gen, Tag, Ver) be a strongly unforgeable MAC with message space M and key space
K, and let Π0 = (Setup0 , S0 , R0 ) be an encryption protocol with message space K. We build a PKMA
protocol Π = (Setup, S, R) as follows.

Setup(1λ ): run (sendk0 , recvk0 ) ← Setup0 (1λ ) and output recvk = sendk0 and sendk = recvk0 . The message
$

space of the protocol Π is the message space M of the MAC.

S(sendk, m): run the encryption protocol Π0 with R with reversed roles, i.e., S runs the receiver algorithm
R0 of Π0 while R will run the sender algorithm S0 . Let r be the output of R0 at the end of the run of
protocol Π0 . Then S sends (m, σ = Tag(r, m)) to R as the last message.
$
R(recvk): generate a fresh MAC key r ← Gen(1λ ) and send r to S using the encryption protocol Π0 , i.e.,
R runs S0 (sendk0 , r). Once the encryption protocol is over, R waits for a message (m, σ 0 ) from S. If
Ver(r, m, σ 0 ) = 1 then R outputs m. Otherwise, it outputs ⊥.

We can now state the following theorem.

Theorem 2. If Π0 is iCCA-secure and MAC is strongly-unforgeable, then Π is an iCMA-secure message

transmission protocol.

Proof. To prove the theorem we define the following hybrid games and we denote with Gi the event
that the outcome of Game i, run with A, is 1.

Game 0: this is the real iCMA game.

Game 1: this is the same as Game 0 except that in the challenge session the receiver generates a
$
random key r∗ ← Gen(1λ ) but runs the encryption protocol Π0 with the message 0, i.e., R runs
0
S0 (sendk , 0). We point out that the receiver keeps using r∗ as the random string associated with the
run of the encryption protocol in the challenge session. This means that:
1. the receiver uses r∗ to check whether Ver(r∗ , m∗ , σ ∗ ) = 1, where (m∗ , σ ∗ ) is the forgery returned
by the adversary (i.e., the last message of A in the challenge session);
2. the receiver uses r∗ to compute σ = Tag(r∗ , m) in all those queries to S(sendk, m) where the
plaintext is m and all previous messages of the session are exactly the same as those of the
challenge session (basically, the adversary replayed all messages of the encryption protocol but
asked for a different plaintext m 6= m∗ ).
Via a straightforward reduction to the iCCA-security of the encryption protocol, it is possible to
show that there exists an adversary B such that:

Pr[G0 ] − Pr[G1 ] ≤ 2 · AdviCCA

Π0 ,B (λ).

11
 Setting: (ek, dk) a key-pair for a labeled encryption scheme
(KG, EncL , DecL ) is generated.

S(dk, m) R(ek)
0 ek0
0
r0 ←Decek (dk, c)  ek , c = Enc (ek, r) $
(ek0 , dk0 ) ← KG(1λ )
$
r ← {0, 1}λ
If r0 6= ⊥ : m, σ = Encm (ek0 , r0 ) - If Decm (dk0 , σ) = r
return m.

Fig. 3. 2-round iCMA protocol from labeled IND−CCA-secure encryption.

Setting: a key pair (sendk0 , recvk0 ) for an n-round protocol Π0 is generated.

$
S(sendk0 , m)  r ← {0, 1}λ R(recvk0 )

S sends (m|r) to R using Π0 Get (m0 |r0 )

- If r0 = r :
return m0

Fig. 4. (n + 1)-round protocol Π from n-round protocol Π0 (S0 speaks first).

Finally, if we consider Game 1 it is not hard to see that by the strong unforgeability of the MAC we
have that Pr[G1 ] ≤ Advsuf -cmva t
u
A,MAC (λ).

Remark 1. While the protocol uses a fresh MAC key for every session, we stress that a one-time MAC
(e.g., a pairwise independent hash function) is not sufficient to prove iCMA security. Intuitively, the
reason is that the adversary may fully-replay the first portion of the protocol (i.e., the one related to
Π0 ) from the challenge session to many copies of the sender, each initialized with a different plaintext
m 6= m∗ , thus obtaining several MACs under the same key.
If we instantiate the above construction with a 1-round (aka non-interactive) iCCA-secure encryption
scheme, and one of the constructions of MACs from IND−CCA encryption proposed in [17] (that have
the advantage of having a ‘compact’ secret key), we then obtain an elegant and efficient 2-round PKMA
protocol based only on IND−CCA security. Moreover, by directly observing the MAC of [17] and the
resulting protocol, we managed to further optimize this protocol: we notice that the ephemeral secret key
dk0 (which is part of the MAC key with r) is only used for verification, and there is no need to encrypt
it inside c; instead, we use labels to bind ek0 with c. The resulting optimized protocol is presented in
Figure 3.
By instantiating the result of Theorem 2 (and our optimization above) with known constructions of
CCA-secure encryption from Factoring [28], DDH [13], or CDH [42], we obtain the following corollary.
Corollary 2. If the Factoring (resp. DDH, CDH) assumption holds, there exists an efficient 2-round
PKMA.

3.3 Secure Round Extension of Message Transmission Protocols

The basic idea for constructing an (n + 1) message transmission protocol Π from an n-round Π0 is
sketched in Figure 4, and consists in letting the party who speaks first send a random nonce r, and then
running the n-round protocol with plaintext m|r. Finally, the receiver will terminate correctly only if
the n-round protocol returns a plaintext m|r, where r is the same nonce sent in the first message. A
formal description of our round-extension construction follows.
If Π0 = (Setup0 , S0 , R0 ) is an n-round message transmission protocol, then we construct an (n + 1)-
round protocol Π = (Setup, S, R) as follows. The key generation algorithm is the same, i.e., Setup =

12
Setup0 and sendk = sendk0 , recvk = recvk0 . To build algorithms S and R we distinguish two cases according
to which party speaks first in Π0 : S0 or R0 .

1. R speaks first. In the new protocol Π0 , it will be S0 who will speak first.
S0 (sendk0 , m): first, choose r ← {0, 1}λ and send r to R0 . To react to the later messages, run
$

S(sendk, m|r) (i.e., on the message obtained by concatenating m and r).

R0 (recvk0 ): wait for the message r from S0 . Next, store r and run R(recvk). At the end of a session,
let m = (m0 |r0 ) be the the message returned by R. If r0 = r, then return m0 , otherwise, output
⊥.
2. S speaks first. In the new protocol Π0 , it will be R0 who will speak first.
S0 (sendk0 , m): wait for the message r from R0 and then run S(sendk, m|r).
R0 (recvk0 ): first, choose a random r ← {0, 1}λ and send r to S0 . Next, run R(recvk), and let m =
$

(m0 |r0 ) be the the message returned by R at the end of its execution. If r0 = r, then return m0 ,
otherwise output ⊥.

In the following theorem we prove that the above construction preserves iCCA and iCMA security.
Theorem 3. For any n ≥ 1, if Π0 is an iCCA (resp. iCMA) secure n-round protocol, there exists an
(n + 1)-round protocol Π that is iCCA (resp. iCMA) secure.
The proof of the Theorem appears in Appendix F.2 and F.3. In what follows we show the following
interesting corollary, where (a) is obtained by applying our observation that 1-round iCMA-secure PKMA
is equivalent to strongly unforgeable signatures, and (b) follows from our Theorem 1.
Corollary 3. (a) For any n ≥ 1, one-way functions are sufficient to build an n-round PKMA proto-
col that is iCMA-secure. (b) For any n ≥ 2, IND−CPA-secure PKE is sufficient to build an n-round
encryption protocol that is iCCA-secure.

4 Advanced Security Properties from the Power of Interaction

We discuss three advanced security properties of message transmission protocols, each requiring inter-
action: deniability, forward security, and replay security.
While the first two properties have been already considered in previous work in the context of
encryption, key exchange, and message authentication, the last one, replay security, is new and aims at
obtaining more intuitive security definitions of message transmission. Interestingly, we show that replay
security can be achieved only by interactive protocols, and that with enough interaction our notions of
iCCA and iCMA security already provide replay-secure protocols.
Below we start with an informal discussion of these advanced security notions. Then, we proceed
by defining and discussing these properties in more detail: deniability (Section 4.1), forward-security
(Section 4.2), and replay-security (Section 4.3).
Deniability. We already mentioned that interactive PKE/PKMA might achieve advanced security
properties which are impossible in the non-interactive setting. One such (well studied [19,21,20,15])
notion is that of deniable authentication, which was actually the original motivation of the DDN paper.
Since this is not the main topic of this work, we only define the weakest notion of passive deniability
(and its extension called ‘passive forward deniability’ [15]), and observe that our optimized 2-round
variant from non-interactive CCA-secure PKE is passively forward deniable.12
Forward Security. Another example is the notion of forward security, which (intuitively) states
that ‘old’ message transmissions should remain private even if the party’s long term secret key is later
compromised. Prior to our work, forward security has been extensively studied in the KE literature
12
The construction can be made ‘actively deniable’, with more rounds, using the techniques developed by [21].

13
(in fact, in many cases being a mandatory part of a ‘secure’ KE). On the other hand, forward security
is (obviously) impossible for non-interactive PKE without “changing the model”; e.g. by introducing
global time periods, and periodically refreshing the secret key [9]. In contrast, no such impossibility
exists for interactive PKE, and, indeed, our interactive PKE schemes are forward-secure, since all of
them use ephemeral keys to actually encrypt the message.
Replay-Security. Yet another limitation of non-interactive PKE/PKMA schemes is that they nec-
essarily suffer from what we informally (for now) term “replay” attacks. In the case of encryption, for
example, an attacker can always record an ‘old’ ciphertext, and then manage to decrypt it much later.
Similarly, a verifier can always pass an ‘old’ signature to another verifier in the future. Motivated by this
impossibility, we formalize (to the best of our knowledge, for the first time) the notion of replay-secure
(necessarily) interactive PKMA/PKE schemes. For the former, a honest verifier is assured that the
“current” message is actually being authenticated by the secret key owner “now”, as opposed to some
time in the past. For the latter, a honest encryptor is similarly assured that the “current” message can
only be decrypted by the secret key owner “now”, as opposed to some time in the future. We then show
that any interactive PKE/PKMA scheme which has at least 2 rounds is already replay-secure.13 For ex-
ample, we automatically get replay-secure PKE/PKMA schemes, by using the 2-round solutions in this
paper.14 We also notice that a very special case of our replay-secure PKMA, when the message space has
cardinality 1, essentially corresponds to the strongest security notion for identification schemes, called
impersonation security under concurrent attacks [5]. Here the attacker has concurrent oracle access to
the prover (i.e., ‘signer of a fixed message’), then loses this oracle access, and, finally, has to convince an
honest verifier. In fact, our 2-round PKMA protocols, when specialized to this trivial case, essentially
“collapse” to well-known challenge-response identification protocols from CCA-encryption and signature
schemes, respectively. Of course, by having an extra “non-trivial” message, we think that replay-secure
PKMA schemes should have more applications than concurrently secure identification schemes.

4.1 Deniability
Informally speaking, a PKMA protocol is deniable if the authenticator S can authenticate a message
m to the receiver R in such a way that R cannot use the transcript of their conversation as evidence to
later convince third parties about the fact that S took part in the protocol and authenticated m.
The area of deniable authentication has attracted a lot of attention [21,20,29,15] and has several
variants depending on the exact attack scenario. While a detailed exploration of this area is beyond the
scope of our work, to illustrate the potential of interactivity we show that our PKMA protocols based
on iCCA encryption already satisfies the weakest form of (perfect) passive deniability, which we define
below.
Definition 7 (Passive Deniability). A PKMA protocol Π = (Setup, S, R) is passive deniable if there
$
exists a PPT simulator Sim such that for all honestly generated keys (recvk, sendk) ← Setup(1λ ), and for
any message m ∈ M, Sim(recvk, m) generates a transcript πS that is (computationally, statistically, or
perfectly) indistinguishable from a transcript π of a real execution hS(sendk, m), R(recvk)i of the protocol.

Forward Deniability. As noted by Di Raimondo and Gennaro [15], the standard definition of
deniability provides guarantees only to the sender. However, if the sender later changes its mind, it
might be able to exhibit some witness (e.g., its private key) that proves its participation in the protocol.
To rule out even this possibility, Di Raimondo and Gennaro introduced the notion of forward deniability,
and showed that every protocol which is deniable in a statistical or perfect sense is also forward deniable.
13
For encryption, we also define a stronger notion of replay-security, which requires at least 3 rounds, and is realized by
any 3-round CCA secure scheme.
14
This includes already mentioned 2-round PKMA from CCA-encryption and 2-round PKE from signatures, as well as
simple 2-round PKE/PKMA obtained by “extending” 1-round PKE/PKMA schemes.

14
Remark 2 (Strong Deniability). It is possible to also consider a stronger form of deniability [21], in
which the receiver might be dishonest. The resulting definition is essentially very similar to the one for
dishonest verifier zero-knowledge. We refer to [21] for more details.

Building Forward Deniable PKMA. Let Πmac and Πlab be our PKMA protocols in Section 3.2
and Appendix E based on iCCA encryption and MACs and on labeled iCCA encryption, respectively,
when instantiated with non-interactive, i.e., 1-round, (labeled) iCCA protocols. Then we can state the
following theorem:
Theorem 4. The protocols Πmac and Πlab are passive forward deniable.
For protocol Πlab , the proof simply follows by observing that the following PPT simulator Sim satisfies
$
Definition 7. Sim(recvk, m) chooses a random r ← M̃ (where M̃ is the message space of the labeled
iCCA encryption protocol), and outputs πS = hm, Sm (recvk, r), ri. It is easy to observe that πS is
exactly distributed as the transcript of a real execution of the protocol. For the protocol Πmac the proof
is essentially the same except that the simulated transcript is πS = hS(recvk, r), Tagr (m)i. Finally, note
that since the transcripts are perfectly indistinguishable the protocols are also forward deniable.
As already noticed in previous work [21,16], both protocols Πmac and Πlab can be modified by adding
a challenge-response subprotocol in order to make them strong deniable for sequential executions.

4.2 Forward Security

Intuitively, forward security guarantees that any leak of secret information at some time t should not
affect the security of protocol runs that occurred in the past, i.e., at any time t0 < t. Forward security is
a desirable property that is not known to be achieved by standard non-interactive public key encryption.
Here we formalize suitable definitions of forward security for interactive encryption protocols, and we
show that our constructions satisfy this property.
We consider both a weak and a strong version of forward security. To define weak forward security,
we introduce an oracle Corrupt, which outputs the secret key recvk of the receiver R. Then we define the
experiment ExpwFS iCCA
Π,A (λ) to be the same as ExpΠ,A (λ) except that A is additionally given access to the
oracle Corrupt that can be queried only after the challenge session is completed.

Definition 8 (Weak Forward Security). We define the advantage of an adversary A in breaking

weak forward security (wFS) of protocol Π as AdvwFS wFS 1
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] − 2 , and we say that Π
is weak forward secure (wFS) if for any PPT A, AdvwFS
iPKE,A (λ) is negligible.

To define strong forward security we introduce another oracle, StateCorrupt, which outputs the
receiver’s secret key recvk as well as R’s private state, consisting of random coins and private information
generated during the run of the protocol. In order to make the game non-trivial for the adversary, we
restrict the revealed state only to sessions that are at the time of the query not completed, and whose
transcript T does not partially match with the transcript T ∗ of the challenge session. We say that a
transcript T partially matches with T ∗ if T matches T ∗ in the old sense up to the first n0 messages,
where n0 is the length of T , i.e., if T ∗ has length n and T has length n0 ≤ n, we consider the first
portion T̃ ∗ of length n0 of the transcript T ∗ , and we apply the previous definition of match, i.e., T ≡ T̃ ∗ .
This notion of partial match is introduced to formalize the fact that the adversary should obtain not
even a small portion of the private state concerning the challenge session. Although this may appear
a restriction, we make the following two observations. First, it follows our intuition for the security of
interactive encryption in which sensitive transmissions should be particularly secured so as not to leak
private state information. Second, it is reasonable to think that once the decryptor loses its control
and reveals all its private state to the adversary (even the state of uncompleted sessions), then there

15
should be no specific security guarantees for every session which is significantly related with the revealed
private state.
Formally, we define the experiment ExpsFS iCCA
Π,A (λ) to be the same as ExpΠ,A (λ) except that A is
additionally given access to the oracle StateCorrupt, that can be queried only after the challenge session
is completed.
Definition 9 (Strong Forward Security). We define the advantage of A in breaking the strong
forward security (sFS) of Π as AdvsFS sFS 1
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] − 2 , and we say that Π is strong
sFS
forward secure (sFS) if for any PPT A, AdviPKE,A (λ) is negligible.

Building Forward Secure (Interactive) PKE. Below we show that our construction of interactive
encryption from IND−CPA-secure encryption proposed in Section 3.1 achieves strong forward security.
Intuitively, this follows from observing that the long-term private key of R is the signing key sk
whereas its private state consists of one-time decryption keys dk. In more detail, we show that our proof
of iCCA security (Theorem 1) can be adapted to the case of strong forward security as follows. First, we
can define the same event Forge, and observe that the proof of Claim 1 to bound Pr[Forge] remains the
same. Indeed, in this proof StateCorrupt queries do not have to be simulated as the entire simulation
will stop before the challenge session is completed. Second, the remaining part of the proof of Theorem
1 can be easily changed as follows to enable the simulator B answer StateCorrupt queries. B knows the
secret key recvk = sendk0 (it is the secret key generated by B itself), which can thus be returned in
output. Then, by definition of strong forward security the only sessions whose state is to be revealed
are those sessions that do not partially match with the challenge session: essentially those sessions for
which B already knows the one-time decryption key dk.

Remark 3. While we showed that our construction of Section 3.1 satisfies strong forward security, we
observe that a construction obtained by applying our round-extension Theorem 3 instead cannot be
proven strong forward secure because of the following attack (here we consider the case when S speaks
first).
– The adversary starts the challenge session with to get the first message r∗ from the challenger.
– Next, it chooses some r 6= r∗ and queries R by sending r to start a new session.
– It receives back ek from R (at the end of Π0 ), and forwards ek to the challenger as the second message.
– Let c∗ be the message received by the challenger. Now, A queries StateCorrupt which will return the
secret key dk corresponding to ek. Notice that such a query is legal as this session does not partially
match with the challenge one as r 6= r∗ .
– Finally, A uses dk to decrypt the ciphertext c∗ .
The above issue stems from the fact that our round extension transformation does not preserve forward
secrecy. However, nothing is lost as the issue can be fixed, thus achieving strong forward security even
for iCCA protocols obtained via round-extension. To do this, we can modify our generic transformation
as follows: when R receives the random r from S, R signs every protocol message together with r, and
includes such signatures along with the messages. Clearly, the above attack no longer applies as A will
not be able to create valid protocol messages for an r 6= r∗ . A formal proof easily follows the intuition
above, and is omitted.

4.3 Replay Security

In what follows we formalize the notion of replay security, and then we show that traditional non-
interactive protocols (e.g., CCA encryption and signatures) cannot be replay-secure. Intuitively, the
reason is that a ciphertext or a digital signature can always be “replayed” after its transmission (this
also explains our choice for the name of this notion).

16
Time Intervals and Concurrent Sessions. To formalize our definitions and argue more easily
about concurrent sessions, we refine our notion of time and we introduce an intuitive terminology. If t
and t0 are time instants such that t < t0 , then we denote with [t, t0 ] the time interval between t and t0 ,
i.e., the sequence ht, t + 1, t + 2, . . . , t0 i. For every protocol transcript T = h(M1 , t1 ), . . . , (Mn , tn )i (i.e.,
for every session) of an n-round protocol there exists a corresponding time interval [t1 , tn ] in which the
session starts and ends. Let [t∗1 , t∗n ] and [t1 , tn ] be the time intervals of two protocol sessions. We say that
[t∗1 , t∗n ] and [t1 , tn ] overlap if [t1 , tn ] ∩ [t∗1 , t∗n ] 6= ∅. Moreover, we say that A is an overlapping adversary if
it generates an oracle session [t1 , tn ] that overlaps with the challenge session [t∗1 , t∗n ].
In the following lemma we show that in any protocol with at least two rounds, any ping-pong
adversary is also overlapping. We use this general statement to prove that any 2-round secure message-
transmission protocol is also replay-secure.

Lemma 2. Let n ≥ 2 and Π be an n-round message transmission protocol. If A is a ping-pong adversary

against Π, then A is overlapping.

Proof. Assume by contradiction that A is not overlapping, then we show that A is not ping-pong. Let
T ∗ and [t∗1 , t∗n ] be the transcript and time interval of the challenge session. Since A is not overlapping,
no oracle session T overlaps with T ∗ , i.e., for every oracle session with time interval [t1 , tn ] it holds
[t∗1 , t∗n ] ∩ [t1 , tn ] = ∅. However, since n ≥ 2, it is easy to see that if [t∗1 , t∗n ] ∩ [t1 , tn ] = ∅ then the
timestamps of these two sessions are not alternating, and thus T 6≡ T ∗ . t
u

Replay-Secure Public-Key Message Authentication. Informally speaking, a PKMA protocol is

replay-secure if all oracle sessions initialized with the challenge plaintext m∗ do not overlap with the
challenge session. This essentially means that the adversary loses access to the legitimate signer (on
message m∗ ) before starting to forge m∗ .
For a more formal definition, consider the experiment ExpiCMA Π,A (defined in Section 2.1) and let
[t1 , t∗n ] be the time interval of the challenge session, and {[ti1 , tin ]}i=1,...,Q be the time intervals of all the
∗

oracle sessions established by A. Moreover, let mi be the plaintext used to initialize the sender oracle
S(sendk, mi ) in the i-th oracle session. Then we call A a replay adversary if there exists i ∈ {1, . . . , Q}
such that mi = m∗ and [ti1 , tin ] ∩ [t∗1 , t∗n ] 6= ∅. Replay security for PKMA is defined as as follows:

Definition 10 (Replay Secure PKMA). Let ExpRSMA Π,A be the same experiment as ExpiCMA
Π,A , except
that A is required not to be a replay adversary (instead of not being ping-pong). Then we say that an
interactive protocol Π is a replay secure PKMA (RSMA for short) if for any PPT A, its advantage
AdvRSMA RSMA
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] is negligible.

First, in the following theorem we show that 1-round PKMA protocols cannot be replay-secure. Its
proof is rather simple and follows from the fact that in 1-round protocols there is clearly no overlap
between different sessions. Hence, the dummy adversary who replays a signature received from the
legitimate signer is a valid adversary in the RSMA experiment.

Theorem 5. Any 1-round iCMA-secure PKMA protocol is not RSMA-secure.

It is worth noting that one can obtain 1-round replay-secure solutions in different models, e.g., by
introducing global time periods and requiring the signer to always sign the message with the current
timestamp. However, such a solution falls outside the pure non-interactive model considered by our
work.
Therefore, while 1-round replay-secure PKMA cannot be achieved, in the following theorem we show
that with at least two rounds of interaction any iCMA-secure protocol is a replay-secure PKMA.

Theorem 6. For n ≥ 2, any n-round iCMA-secure protocol Π is RSMA-secure.

17
Proof. The proof follows by observing that if A is not a replay adversary in ExpRSMA Π,A (for Π with at
least 2 rounds), then A is also not ping-pong in ExpiCMA Π,A . Namely, we show that for a non-replay A
we have that for all i = 1, . . . , Q, Ti 6≡ T . For every i, there are only two possible cases: mi = m∗ or
∗

mi 6= m∗ . If mi = m∗ , then Ti 6≡ T ∗ follows by Lemma 2. In the case of sessions i where mi 6= m∗ ,

assume by contradiction that Ti ≡ T ∗ . Then by definition of match the sessions must share the same
protocol messages in the same order (i.e., Mji = Mj∗ ) which, by correctness, implies that mi = m∗ , a
contradiction. t
u

From Theorem 6 we obtain two interesting results that we summarize in the following corollary:
Corollary 4. (1) There exists a simple 2-round replay-secure PKMA protocol based on any strongly
unforgeable signature scheme (and thus on one-way functions); (2) there exists a simple 2-round replay-
secure PKMA protocol based on any IND−CCA-secure PKE.
The construction (1) follows by combining Theorem 6 with our round-extension result (Theorem 3)
applied to any strongly unforgeable signature (aka 1-round iCMA-secure PKMA). The construction (2)
from IND−CCA-secure PKE is instead obtained by applying Theorem 6 to our 2-round construction of
Theorem 2 (instantiated with a non-interactive IND−CCA-secure PKE scheme).

Remark 4 (Relation to Concurrent-Secure Identification Schemes). Notice that in the special case when
the message space has cardinality 1, our notion of replay-secure PKMA essentially corresponds to the
strongest security notion for identification schemes, called impersonation security under concurrent
attacks [5]. In this case (i.e., message space of cardinality 1), a PKMA can be indeed seen as an
identification scheme. Moreover, by considering authentication with an empty message space, the 2-
round PKMA protocols mentioned in Corollary 4 recover well known 2-round, signature-based and
encryption-based, identification schemes (see, e.g., [2], and notice that outputting the secret key is
indeed a secure MAC for an empty message space).

Replay-Secure Public-Key Encryption. Informally speaking, a PKE protocol is replay-secure if

there is no overlap between the challenge session and all oracle sessions in which the plaintext revealed
by the receiver is one of the two challenge plaintexts. In essence, this means that during the challenge
session the adversary loses access to the legitimate decryptor, but only on the challenge plaintexts
m0 or m1 . More formally, consider the experiment ExpiCCA ∗ ∗
Π,A (defined in Section 2.1) and let [t1 , tn ] be
the time interval of the challenge session, and {[ti1 , tin ]}i=1,...,Q be the time intervals of all the oracle
sessions established by A. Moreover, let mi be the plaintext revealed by the receiver in the i-th oracle
session (wlog we only consider completed sessions). Then, we call A a replay adversary if there exists
i ∈ {1, . . . , Q} such that mi = m0 or mi = m1 , and [ti1 , tin ] overlaps with [t∗1 , t∗n ]. Replay security for
PKE is defined as follows:
Definition 11 (Replay-Secure Encryption). Let ExpRSE iCCA
Π,A be the same as experiment ExpΠ,A , ex-
cept that A is required not to be a replay adversary (instead of denying it to be ping-pong). Then we
say that an interactive protocol Π is a replay-secure encryption (RSE) if for any PPT A, its advantage
AdvRSE RSE 1
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] − 2 is negligible.

It is worth mentioning that the notion of replay-secure PKE is similar to the notion of Replayable
CCA-secure encryption (RCCA) introduced by Canetti, Krawczyk and Nielsen [10]. In RCCA security
the adversary is allowed to submit any ciphertext c to the decryption oracle, except that if c decrypts
to m0 or m1 the adversary gets a special string test as response.
Similarly to replay-secure PKMA, in the following theorems we show that replay-secure PKE requires
at least 2-rounds of interaction to be achieved.
Theorem 7. Any 1-round iCCA-secure PKE protocol is not RSE-secure.

18
The proof is obtained by considering the adversary who replays the challenge ciphertext to the receiver.

Theorem 8. For n ≥ 2, any n-round iCCA-secure protocol Π is RSE-secure.

Proof. The proof follows by observing that if A is not a replay adversary in ExpRSE Π,A where Π has at least
iCCA
2 rounds, then A is also not ping-pong in ExpΠ,A . Namely, we show that for a non-replay adversary
A we have that for all i = 1, . . . , Q, it holds Ti 6≡ T ∗ . For every i, there are only two possible cases: (1)
mi = m0 or mi = m1 , and (2) mi 6= m0 , m1 . In the first case, note that Ti 6≡ T ∗ follows by Lemma 2,
i.e., if the A is not replay, then A is not ping-pong w.r.t. these sessions. In the case of sessions i where
mi 6= m0 , m1 , assume by contradiction that Ti ≡ T ∗ . Then by definition of match, these sessions must
share the same protocol messages in the very same order (i.e., Mji = Mj∗ ). However, by correctness,
this implies mi = mb where b is the secret bit chosen in the experiment, which is a contradiction as we
assumed mi 6= m0 , m1 . t
u

From Theorem 8 we obtain a collection of nice results summarized in the following Corollary:
Corollary 5. (1) IND−CPA-secure PKE is sufficient to build RSE-secure PKE; (2) there exists an
efficient 2-round RSE-secure PKE protocol based on 1-bounded-IND−CCA-secure PKE and signature
schemes (see Theorem 1); (3) there exists an efficient 2-round RSE-secure PKE protocol based on any
IND−CCA-secure PKE (via our round-extension transformation of Theorem 3).
Strong Replay-Secure Encryption. We notice that our definition of replay security (for both PKMA
and PKE) does not allow the adversary to suspend “critical” sessions (e.g., sessions authenticating m∗ ,
or sessions which decrypt to m0 or m1 ) during the challenge session, and to later resume these sessions
once the challenge session is over. While allowing such suspended sessions would not make sense for
PKMA (indeed observe that the outcome of the security experiment is determined upon the end of
the challenge session), it might be a reasonable strengthening for replay-secure PKE. Here we define
strong-replay-secure PKE, and we show that two rounds of interaction are insufficient to achieve strong
replay-security with suspended sessions (see Theorem 9 below), but three rounds are enough and indeed
any (at least) 3-round iCCA-secure PKE is strong replay-secure (cf. Theorem 10).
Towards defining strong replay security more formally, let us say that [t1 , tn ] is off during [t∗1 , t∗n ]
if for all j = 1, . . . , n we have that tj ∈/ [t∗1 , t∗n ]. We call A a strong replay adversary if there exists
i ∈ {1, . . . , Q} such that m = m0 or m = m1 , and [ti1 , tin ] is not off during [t∗1 , t∗n ].
i i

Definition 12 (Strong Replay-Secure Encryption). Let ExpsRSE iCCA

Π,A be the same experiment as ExpΠ,A ,
except that A is required not to be a strong replay adversary (instead of denying it to be ping-pong).
Then we say that an interactive protocol Π is a strong replay secure encryption (sRSE) if for any PPT
A, its advantage AdvsRSE sRSE 1
Π,A (λ) = Pr[ExpΠ,A (λ) = 1] − 2 is negligible.

Theorem 9. Any 2-round iCCA-secure PKE protocol is not sRSE-secure.

Proof. To prove the theorem we show that there exists an adversary A who is not a strong replay
adversary in ExpsRSE
Π,A but is a ping-pong adversary. Then, being ping-pong, A can trivially obtain a
decryption of the challenge plaintext.
First, observe that in any 2-round protocol we have the first message from R to S. So, consider the
following adversary A that plays the role of the receiver in the challenge session:

– A queries R on a new session and obtains M1 with timestamp t1 = t.

– A sends M1 to the honest sender S as the first protocol message in the challenge session (here M1
gets timestamp t∗1 = t + 1). A receives back M2 from S, where M2 gets timestamp t∗2 = t + 2.
– A forwards M2 to R in the session previously opened in step 1 (this message gets timestamp t2 =
t + 3).

19
While A is clearly ping-pong according to Definition 4, A is still not a strong replay adversary in
ExpsRSE
Π,A since t1 , t2 ∈
/ [t + 1, t + 2]. This is exactly a case in which the adversary suspended a session. t
u
Theorem 10. For n ≥ 3, any n-round iCCA-secure protocol Π is sRSE-secure.

The proof is basically the same as that of Theorem 8, except that here we use the following lemma to
show that for 3-round protocols any ping-pong adversary generates an oracle session (decrypting to one
of the challenge plaintexts) which is not off during the challenge session.
Lemma 3. Let n ≥ 3, and let T , [t1 , tn ] and T ∗ , [t∗1 , t∗n ] be the transcripts and time intervals of two
sessions of an n-round protocol. If [t1 , tn ] is off during [t∗1 , t∗n ], then T does not match with T ∗ .

Proof. Recall that [t1 , tn ] is off during [t∗1 , t∗n ] if for all j = 1, . . . , n we have that tj ∈
/ [t∗1 , t∗n ]. This means
∗ ∗ ∗ ∗
that either one of the following cases occurs: (1) [t1 , tn ] ∩ [t1 , tn ] = ∅, (2) [t1 , tn ] ∩ [t1 , tn ] 6= ∅. Case (1) is
identical to that of Lemma 2. In case (2), we have that the two sessions overlap, and we also know that
/ [t∗1 , t∗n ], ∀j = 1, . . . , n, that is t1 < t∗1 and t3 > t∗3 . Since there are at least 3 rounds, there exists at
tj ∈
least a distinct timestamp t2 such that t1 < t2 < tn and such that t2 satisfies either one of the following
conditions: t1 < t2 < t∗1 , or tn > t2 > t∗n . However, one can again check that in neither one of these cases
the timestamps are correctly alternating. Therefore, T 6≡ T ∗ . t
u

Acknowledgements. The authors would like to thank Adam O’Neill, Victor Shoup and Stefano
Tessaro for valuable discussions on this work. The research of Yevgeniy Dodis is partially supported by
gifts from VMware Labs and Google, and NSF grants 1319051, 1314568, 1065288, 1017471. The research
of Dario Fiore is partially supported by the European Commission Seventh Framework Programme
Marie Curie Cofund Action AMAROUT-II (grant no. 291803), and the Madrid Regional Government
under project PROMETIDOS-CM (ref. S2009/TIC1465).

References
1. M. Bellare, R. Canetti, and H. Krawczyk. A modular approach to the design and analysis of authentication and key
exchange protocols (extended abstract). In 30th Annual ACM Symposium on Theory of Computing, pages 419–428.
ACM Press, May 1998.
2. M. Bellare, M. Fischlin, S. Goldwasser, and S. Micali. Identification protocols secure against reset attacks. In B. Pfitz-
mann, editor, Advances in Cryptology – EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science,
pages 495–511. Springer, May 2001.
3. M. Bellare and S. Micali. How to sign given any trapdoor function (extended abstract). In 20th Annual ACM
Symposium on Theory of Computing, pages 32–42. ACM Press, May 1988.
4. M. Bellare and S. Micali. How to sign given any trapdoor function. Journal of the ACM, 39(1):214–233, 1992.
5. M. Bellare and A. Palacio. GQ and Schnorr identification schemes: Proofs of security against impersonation under
active and concurrent attacks. In M. Yung, editor, Advances in Cryptology – CRYPTO 2002, volume 2442 of Lecture
Notes in Computer Science, pages 162–177. Springer, Aug. 2002.
6. M. Bellare and P. Rogaway. Entity authentication and key distribution. In D. R. Stinson, editor, Advances in Cryptology
– CRYPTO’93, volume 773 of Lecture Notes in Computer Science, pages 232–249. Springer, Aug. 1993.
7. M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In V. Ashby,
editor, ACM CCS 93: 1st Conference on Computer and Communications Security, pages 62–73. ACM Press, Nov.
1993.
8. J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In D. Boneh,
editor, Advances in Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 126–144.
Springer, Aug. 2003.
9. R. Canetti, S. Halevi, and J. Katz. A forward-secure public-key encryption scheme. In E. Biham, editor, Advances in
Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 255–271. Springer, May
2003.
10. R. Canetti, H. Krawczyk, and J. B. Nielsen. Relaxing chosen-ciphertext security. In D. Boneh, editor, Advances in
Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 565–582. Springer, Aug. 2003.
11. S. G. Choi, D. Dachman-Soled, T. Malkin, and H. Wee. Black-box construction of a non-malleable encryption scheme
from any semantically secure one. In R. Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume
4948 of Lecture Notes in Computer Science, pages 427–444. Springer, Mar. 2008.

20
12. R. Cramer, G. Hanaoka, D. Hofheinz, H. Imai, E. Kiltz, R. Pass, A. Shelat, and V. Vaikuntanathan. Bounded CCA2-
secure encryption. In K. Kurosawa, editor, Advances in Cryptology – ASIACRYPT 2007, volume 4833 of Lecture Notes
in Computer Science, pages 502–518. Springer, Dec. 2007.
13. R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext
attack. In H. Krawczyk, editor, Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer
Science, pages 13–25. Springer, Aug. 1998.
14. R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption. In ACM CCS 99: 6th Conference
on Computer and Communications Security, pages 46–51. ACM Press, Nov. 1999.
15. M. Di Raimondo and R. Gennaro. New approaches for deniable authentication. In V. Atluri, C. Meadows, and
A. Juels, editors, ACM CCS 05: 12th Conference on Computer and Communications Security, pages 112–121. ACM
Press, Nov. 2005.
16. M. Di Raimondo, R. Gennaro, and H. Krawczyk. Deniable authentication and key exchange. In A. Juels, R. N.
Wright, and S. Vimercati, editors, ACM CCS 06: 13th Conference on Computer and Communications Security, pages
400–409. ACM Press, Oct. / Nov. 2006.
17. Y. Dodis, E. Kiltz, K. Pietrzak, and D. Wichs. Message authentication, revisited. In D. Pointcheval and T. Johansson,
editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages
355–374. Springer, Apr. 2012.
18. D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography (extended abstract). In 23rd Annual ACM Symposium
on Theory of Computing, pages 542–552. ACM Press, May 1991.
19. D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM Journal on Computing, 30(2):391–437, 2000.
20. C. Dwork and M. Naor. Zaps and their applications. In 41st Annual Symposium on Foundations of Computer Science,
pages 283–293. IEEE Computer Society Press, Nov. 2000.
21. C. Dwork, M. Naor, and A. Sahai. Concurrent zero-knowledge. In 30th Annual ACM Symposium on Theory of
Computing, pages 409–418. ACM Press, May 1998.
22. C. Dwork and A. Sahai. Concurrent zero-knowledge: Reducing the need for timing constraints. In H. Krawczyk, editor,
Advances in Cryptology – CRYPTO’98, volume 1462 of Lecture Notes in Computer Science, pages 442–457. Springer,
Aug. 1998.
23. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M.
Odlyzko, editor, Advances in Cryptology – CRYPTO’86, volume 263 of Lecture Notes in Computer Science, pages
186–194. Springer, Aug. 1986.
24. R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In J. Stern, editor,
Advances in Cryptology – EUROCRYPT’99, volume 1592 of Lecture Notes in Computer Science, pages 123–139.
Springer, May 1999.
25. Y. Gertner, T. Malkin, and S. Myers. Towards a separation of semantic and CCA security for public key encryption. In
S. P. Vadhan, editor, TCC 2007: 4th Theory of Cryptography Conference, volume 4392 of Lecture Notes in Computer
Science, pages 434–455. Springer, Feb. 2007.
26. S. Goldwasser, S. Micali, and R. L. Rivest. A “paradoxical” solution to the signature problem (abstract) (impromptu
talk). In G. R. Blakley and D. Chaum, editors, Advances in Cryptology – CRYPTO’84, volume 196 of Lecture Notes
in Computer Science, page 467. Springer, Aug. 1984.
27. L. C. Guillou and J.-J. Quisquater. A “paradoxical” indentity-based signature scheme resulting from zero-knowledge.
In S. Goldwasser, editor, Advances in Cryptology – CRYPTO’88, volume 403 of Lecture Notes in Computer Science,
pages 216–231. Springer, Aug. 1988.
28. D. Hofheinz and E. Kiltz. Practical chosen ciphertext secure encryption from factoring. In A. Joux, editor, Advances
in Cryptology – EUROCRYPT 2009, volume 5479 of Lecture Notes in Computer Science, pages 313–332. Springer,
Apr. 2009.
29. J. Katz. Efficient and non-malleable proofs of plaintext knowledge and applications. In E. Biham, editor, Advances in
Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 211–228. Springer, May
2003.
30. H. Krawczyk. Skeme: a versatile secure key exchange mechanism for internet. In Network and Distributed System
Security, 1996., Proceedings of the Symposium on, pages 114 –127, feb 1996.
31. Y. Lindell. A simpler construction of cca2-secure public-key encryption under general assumptions. In E. Biham,
editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages
241–254. Springer, May 2003.
32. S. Myers and A. Shelat. Bit encryption is complete. In 50th Annual Symposium on Foundations of Computer Science,
pages 607–616. IEEE Computer Society Press, Oct. 2009.
33. M. Naor and O. Reingold. Number-theoretic constructions of efficient pseudo-random functions. In 38th Annual
Symposium on Foundations of Computer Science, pages 458–467. IEEE Computer Society Press, Oct. 1997.
34. M. Naor, O. Reingold, and A. Rosen. Pseudo-random functions and factoring (extended abstract). In 32nd Annual
ACM Symposium on Theory of Computing, pages 11–20. ACM Press, May 2000.
35. M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In 21st Annual ACM
Symposium on Theory of Computing, pages 33–43. ACM Press, May 1989.

21
36. M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd Annual
ACM Symposium on Theory of Computing, pages 427–437. ACM Press, May 1990.
37. C. Rackoff and D. R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In
J. Feigenbaum, editor, Advances in Cryptology – CRYPTO’91, volume 576 of Lecture Notes in Computer Science,
pages 433–444. Springer, Aug. 1991.
38. J. Rompel. One-way functions are necessary and sufficient for secure signatures. In 22nd Annual ACM Symposium on
Theory of Computing, pages 387–394. ACM Press, May 1990.
39. A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In 40th Annual
Symposium on Foundations of Computer Science, pages 543–553. IEEE Computer Society Press, Oct. 1999.
40. C.-P. Schnorr. Efficient identification and signatures for smart cards. In G. Brassard, editor, Advances in Cryptology
– CRYPTO’89, volume 435 of Lecture Notes in Computer Science, pages 239–252. Springer, Aug. 1989.
41. B. R. Waters. Efficient identity-based encryption without random oracles. In R. Cramer, editor, Advances in Cryptology
– EUROCRYPT 2005, volume 3494 of Lecture Notes in Computer Science, pages 114–127. Springer, May 2005.
42. H. Wee. Efficient chosen-ciphertext security via extractable hash proofs. In T. Rabin, editor, Advances in Cryptology
– CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 314–332. Springer, Aug. 2010.

A Standard Cryptographic Primitives

A.1 (Non-Interactive) CCA-secure Public-Key Encryption

A public key encryption scheme E is a tuple of algorithms (KG, Enc, Dec) defined as follows:
KG(1λ ) on input the security parameter, the key generation returns a public key ek and a secret key
dk.
Enc(ek, m) on input the public key ek and a message m, it outputs a ciphertext c.
Dec(dk, c) given the secret key dk and a ciphertext c, it outputs a message m or an error symbol ⊥.
Consider the following experiment involving the scheme E and an adversary A:
Experiment ExpIND−CCA
E,A (λ)
$
b ← {0, 1}
$
(ek, dk) ← KG(1λ )
(m0 , m1 )←ADec(dk,·) (ek)
$
c∗ ← Enc(ek, mb )
b0 ←ADec(dk,·) (c∗ )
If b0 = b and A is “legal” output 1
Else output 0.
In the above experiment, A is called “legal” if it does not query the decryption oracle Dec(dk, ·) on the
challenge ciphertext c∗ (after A receives c∗ ).
The advantage of an adversary A in breaking the IND−CCA security of an encryption scheme E is

1
AdvIND−CCA
E,A (λ) = Pr[ExpIND−CCA
E,A (λ) = 1] −
2

Definition 13 (IND−CCA security). An encryption scheme E is IND−CCA-secure if for any PPT A,

AdvIND−CCA
E,A (λ) is negligible.

A weaker notion of IND−CCA security that we consider in our work is q-bounded IND−CCA security
[12]. This notion is defined as IND−CCA security except that the adversary is restricted to query the
decryption oracle at most q times (where q is a pre-fixed bound).
A further weaker notion of security for public key encryption is semantic security, or indistinguisha-
bility against chosen-plaintext attacks (IND−CPA). Its definition is the same as IND−CCA security
except that the adversary does not get access to any decryption oracle.

22
A.2 Digital Signatures
A digital signature scheme consists of a triple of algorithms Σ = (Σ.kg, Sign, Ver) working as follows:
Σ.kg(1λ ) the key generation takes as input a security parameter λ and returns a pair of keys (sk, vk).
Sign(sk, m) on input a signing key sk and a message m, the signing algorithm produces a signature σ.
Ver(vk, m, σ) given a triple vk, m, σ the verification algorithm tests if σ is a valid signature on m with
respect to verification key vk.
For security we define the following experiment:
Experiment Expuf -cma (λ)
A,Σ
$
(sk, vk) ← Σ.kg(1λ )
$
(m∗ , σ ∗ ) ← ASign(sk,·) (vk)
If Ver(vk, m∗ , σ ∗ ) = 1 and (m∗ , σ ∗ ) is “new” then output 1
Else Output 0
We say that the forgery (m∗ , σ ∗ ) is “new” if it is different from all the pairs (mi , σi ) obtained from the
signing oracle Sign(sk, ·). We define the advantage of an adversary A in breaking the strong unforgeability
against chosen-message attacks (suf-cma) of Σ as Advsuf -cma (λ) = Pr[Expsuf -cma (λ) = 1].
A,Σ A,Σ
Definition 14 (suf-cma security). A digital signature scheme Σ is suf-cma-secure if for any PPT A,
Advsuf -cma (λ) is negligible.
A,Σ
A weaker notion of security is (simple) unforgeability against chosen-message attacks (uf-cma), which
is defined as the strong version above, except that (m∗ , σ ∗ ) is considered “new” if only the message m∗
(instead of the pair) is different from all messages mi queried to the signing oracle.

A.3 Message Authentication Codes

A message authentication code consists of a triple of algorithms MAC = (Gen, Tag, Ver) working as
follows:
Gen(1λ ): the key generation algorithm takes as input the security parameter λ and returns a key k ∈ K.
Tag(k, m): on input a secret key k ∈ K and a message m ∈ M, the authentication algorithm produces
an authentication tag σ.
Ver(k, m, σ): given the secret key k, a message m and an authentication tag σ, the verification algorithm
tests if σ correctly authenticates m.
$
A scheme MAC is correct if for all λ ∈ N and m ∈ M, the probability Pr[Ver(k, m, σ) = 1 : k ←
$
Gen(1λ ), σ ← Tag(k, m)] is overwhelming. The security is defined via the following experiment:
Experiment Expsuf -cmva (λ)
A,MAC
$
k← Gen(1λ )
Run ATag(k,·),Ver(k,·,·) (λ)
If A makes a verification query (m∗ , σ ∗ ) such that Ver(k, m∗ , σ ∗ ) = 1 and (m∗ , σ ∗ ) is “new”,
then output 1.
Else output 0
where for (m∗ , σ ∗ ) being “new” we mean that it must be different from all the pairs (mi , σi ) obtained
from the tag oracle Tag(k, ·). The advantage of an adversary A in breaking the strong unforgeability
against chosen-message and chosen verification queries attacks (suf-cmva) of MAC is Advsuf -cmva
A,MAC (λ) =
Pr[Expsuf -cmva
A,MAC (λ) = 1].
Definition 15 (suf-cmva security). A message authentication code MAC is suf-cmva-secure if for any
PPT A, Advsuf -cmva
A,MAC (λ) is negligible.

23
B DDN 3-round iCCA-Secure Encryption from IND−CPA Security
In this section we recall the 3-round iCCA-secure PKE proposed by Dolev, Dwork and Naor [19], which
is based on IND−CPA-secure PKE and signature schemes.
Let Σ = (Σ.kg, Sign, Ver) be a (regular) signature scheme, Σ 0 = (Σ.kg0 , Sign0 , Ver0 ) be a one-time
signature scheme, and E = (KG, Enc, Dec) be a (non-interactive) public key encryption scheme. Using
our syntax, the DDN protocol ΠDDN = (Setup, S, R) is as follows:
$
Setup(1λ ): run (sk, vk) ← Σ.kg(1λ ) and output sendk = vk and recvk = sk.
S(sendk, m): first generate a fresh one-time signing key pair (skS , vkS ) ← Σ.kg0 (1λ ) and send vkS to R.
$

Upon receiving the second message from R, the sender checks that Ver(sendk, vkS |ek, σR ) = 1, and if
so computes c ← Enc(ek, m) and σS ← Sign0 (skS , c), and sends (c, σS ).
$ $

$
R(recvk): upon receipt of the first message vkS from S, generate a fresh encryption key pair (ek, dk) ←
$
KG(1λ ), compute σR ← Sign(recvk, vkS |ek) and send (ek, σR ) to S.
Once the message (c, σS ) is obtained, the receiver checks that Ver0 (vkS , c, σS ) = 1, and if so returns
m←Dec(dk, c) as its private output.
Below we sketch the proof of security of ΠDDN under our iCCA notion.
Theorem 11. If E is IND−CPA-secure, Σ is uf-cma-secure, and Σ 0 is one-time uf-cma-secure, then
ΠDDN is iCCA-secure.
∗ ∗ ∗
Proof (Sketch). Consider the experiment ExpiCCA ΠDDN ,A , and let vkS and (c , σS ) be the first and the third
protocol messages, respectively, generated by the honest sender in the challenge session. Let Forge1 be
the event that in the challenge session the adversary A outputs a second protocol message including a
valid signature σR that was not obtained by the R oracle. It is not hard to see that under the assumption
that the signature scheme Σ is secure we have that Pr[Forge1 ] is negligible. Also, let Forge2 be the event
that the adversary queries the receiver oracle with a third protocol message (c, σS ) such that: the first
protocol message of the given session is vk∗S (i.e., the same verification key as in the challenge session),
but c is “new”, in particular c 6= c∗ . Again, it is possible to show that under the assumption that Σ 0 is
a one-time signature the probability Pr[Forge2 ] is negligible.
Finally, it is possible to show that Pr[ExpiCCA
ΠDDN ,A | Forge1 ∧Forge2 ] is negligible under the assumption
that E is IND−CPA-secure. The main observation is that one can simulate answers of the receiver oracle
to third messages (i.e., decryptions). This follows from the fact that when Forge1 and Forge2 do not
occur, a non-ping-pong adversary cannot create a valid third message that uses the same one-time
signature/encryption keys of the challenge session. t
u

C A 1-bounded IND−CCA-Secure Encryption Scheme

Here we recall a black-box construction of a 1-bounded IND−CCA-secure encryption scheme from an
IND−CPA-secure one. The scheme is a (simplified) special case of the q-bounded one of Cramer et
al. [12], but it is also very similar to the scheme of Dolev, Dwork and Naor [19] without NIZK proofs.
Let E 0 = (KG0 , Enc0 , Dec0 ) be a semantic secure public key encryption scheme. The IND−CCA scheme
E = (KG, Enc, Dec) is defined as follows:
KG(1λ ): Generate 2n keys (ekbi , dkbi ) ← KG0 (1λ ) ∀i = 1, . . . , n, b = 0, 1, and a random universal one-
$

way hash function h. Output the public key ek = (h, ek01 , ek11 , . . . , ek0n , ek1n ) and the secret key dk =
(dk01 , dk11 , . . . , dk0n , dk1n ).
Enc(ek, m): First, generate a pair of keys (sk, vk) for a one-time signature, and compute v = h(vk)
(write v = v1 · · · vn using its bitwise representation). Next, generate random messages m1 , . . . , mn
such that m1 ⊕ m2 ⊕ · · · ⊕ mn = m. Then, for i = 1 to n, compute ci ← Enc(ekvi i , mi ), create a
$

signature σ on (c1 , . . . , cn ) using sk, and output C = (vk, σ, c1 , . . . , cn ).

24
Dec(dk, C): Verify that σ is a valid signature on (c1 , . . . , cn ) using verification key vk. Then compute
v = h(vk) and decrypt each ciphertext computing mi ←Dec(dkvi i ). If the signature is valid output
m = m1 ⊕ m2 ⊕ · · · ⊕ mn . Otherwise output ⊥ (reject).

D iCCA-Secure Interactive Encryption with Labels

In an encryption scheme with “labels” the encryption and decryption algorithms are assumed to take a
public string called label as an additional input. While this notion has been already introduced in the
non-interactive setting [8], here we propose its natural extension to the interactive scenario. We will show
an elegant application of labeled iCCA encryption to our notion of public key message authentication
(see Section 2.2).
An interactive encryption protocol with labels is basically the same as the one defined in Section
2.1, except that both sender and receiver work with a public label L (i.e., an arbitrary binary string)
as additional input. For any label L we denote the algorithms with SL (sendk, m) and RL (recvk). For
correctness, we require that for all honestly generated keys (sendk, recvk), all messages m ∈ M and all
labels L, hSL (sendk, m), RL (recvk)i = m holds with all but negligible probability.
The iCCA security notion is extended to the labeled case as follows: when the adversary queries
the receiver oracle, it also specifies a label L, i.e., A interacts with RL (recvk). The adversary A is
also required to output a label L∗ along with the message pair (m0 , m1 ), and the challenge session is
hSL∗ (sendk, mb ), AR(·) (recvk) i. The restriction on A not to be ping-pong is extended in such a way that
for every oracle session with transcript T and label L, it must hold L 6= L∗ or T 6≡ T ∗ .
Building iCCA Encryption with Labels from iCCA Encryption. We show that iCCA encryption
with labels can be realized from iCCA-secure encryption. The idea of the construction is the same
as for the non-interactive case: if L is the label, then the encryption protocol is run with plaintext
mL = L|m, i.e., the concatenation of the label and the plaintext m; when the decryptor obtains a
plaintext m0L = L0 |m0 it checks whether it obtained the label L, i.e., if L0 = L.
A formal description of this construction follows. Let Π = (Setup, S, R) be an interactive encryption
protocol. We build an interactive encryption protocol with labels Π0 = (Setup0 , S0 , R0 ) as follows. The
key generation is the same Setup0 = Setup, thus sendk0 = sendk, recvk0 = recvk. The sender algorithm
S0L (sendk, m) simply runs S(sendk, L|m) (i.e., on the concatenation of the message m and the label L).
The receiver algorithm R0L (recvk) runs R(recvk). At the end of a session, if m0L = (L0 |m0 ) is the the
message returned by R, then R0 returns m0 only if L0 = L. Otherwise, it returns ⊥.
We show the security of this construction via the following theorem.

Theorem 12. If Π is a iCCA-secure encryption protocol, then Π0 is a iCCA-secure encryption protocol

with labels.

Proof. Assume by contradiction that there exists a PPT adversary A that breaks the iCCA security of
the labeled scheme Π0 , then we show how to build a PPT algorithm B that uses A as a subroutine to
break the iCCA security of Π.
B is given sendk, it runs A(sendk) and answers oracle queries as follows. When A will query R0 on
a new session, A has to provide a label L. So, B stores L, queries its oracle, R, and returns its answer
to A. All the oracle queries to R0 for sessions that already started are simply forwarded by B to its R
oracle. When A queries R0 on the last message, B first forwards this query to R, obtains m = (L0 |m0 ),
and returns to A m0 , if L = L0 (where L is the label stored for this session), and ⊥ otherwise.
When A outputs a message pair (m0 , m1 ) and a label L∗ , B starts its challenge session by returning
(L |m0 , L∗ |m1 ) as its message pair. Next, for all subsequent messages B simply forwards them to its
∗

challenge session, and forwards back to A the respective responses. Let T ∗ = h(M1∗ , t∗1 ), . . . , (Mn∗ , t∗n )i
be the transcript of the challenge session between B (who is simulating S0L∗ (sendk, mb )) and A.

25
 Setting: a key pair (sendk0 , recvk0 ) for an iCCA-secure protocol Π0 is gener-
ated.
S(recvk0 , m) R(sendk0 )
m -
$
Get r0 R sends r to S using Π0 with label m r ← {0, 1}λ


r0 - If r0 = r return m

Fig. 5. iCMA-secure protocol from labeled iCCA-secure encryption.

In this second phase, B answers all oracle queries as before except for the following change. Assume
that A sends the last message Mn in some session whose label is L and whose transcript is T =
h(M1 , t1 ), . . . , (Mn , tn )i. If T ≡ T ∗ but L 6= L∗ , then B returns ⊥ as the R0 output. Note that by
correctness of Π, R would decrypt T to some message of the form L∗ |mb . Hence, as L 6= L∗ R0 would
reject this message, that is B’s answer is correctly distributed. If b0 is the output of A at the end of the
simulation, B outputs the same value. To complete the proof, we observe that if A is not ping-pong,
then B is not ping-pong. t
u

E iCMA-secure PKMA from labeled iCCA-secure encryption.

Here we consider another protocol that achieves public key message authentication based on iCCA-
secure encryption. The basic protocol was first proposed by Dolev, Dwork, and Naor in [19], and later
discussed by Dwork, Naor, and Sahai [21,22]. Here we revisit this construction by using the abstraction
of encryption with labels, and by using our notion of (possibly) interactive iCCA-secure encryption (see
Section D). A sketch of the protocol is summarized in Figure 5: (1) S sends the message m to R; (2)
R picks a random string r and confidentially transmits r with label m to S by using the encryption
protocol Π0 ; (3) S obtains r0 and hands r0 to the receiver. If R obtains the same r, then it accepts the
message m.
To improve on round complexity, one can use even a 1-round (aka non-interactive) iCCA-secure la-
beled encryption scheme. In this case, our construction yields a 3-round iCMA-secure protocol. However,
we note that the first round, where S sends m to R, can be dropped in all those applications where the
message is implicitly known to the receiver (e.g., it is some public information). This way, one obtains
an optimal 2-round protocol.
More formally, if Π0 = (Setup0 , S0 , R0 ) is an encryption protocol with labels with message space M̃
such that |M̃| ≈ 2λ , then we build a PKMA protocol Π = (Setup, S, Ver) as follows.

Setup(1λ ): run (sendk0 , recvk0 ) ← Setup0 (1λ ) and output sendk = recvk0 and recvk = sendk0 .
$

S(sendk, m): as first protocol message, send m. Next, run the encryption protocol Π0 by playing the role
of the receiver. More precisely, use m as the label, and run R0m (recvk0 ). Let r0 be the output of R0 at
the end of the encryption protocol. Finally, send r0 to R as the last message.
$
R(recvk): first, wait for message m from S. Next, choose a random string r ← M̃ and run the encryption
protocol Π0 by playing the role of the sender. More precisely, use m as the label and run S0m (sendk0 , r).
If the encryption protocol terminates correctly, then wait for the last message r0 from S. If r0 = r
then output m. Otherwise, output ⊥.
We can now prove the following theorem.
Theorem 13. If Π0 is iCCA-secure encryption with labels, with message space of size at least 2λ , then
the protocol Π described above is iCMA-secure.

26
Proof. To prove the theorem we define the following hybrid games and we denote with Gi the event
that the outcome of Game i, run with A, is 1.

Game 0: this is the real iCMA game.

Game 1: this is the same as Game 0 except that in the challenge session the challenger generates
$
two random strings r∗ ← M̃, and it runs the encryption protocol Π0 with a fixed string r1∗ (e.g.,
r1∗ = 0λ ), i.e., B runs S0m∗ (sendk0 , r1∗ ). However, the challenger keeps using r0∗ as the random string
associated with the run of the encryption protocol in the challenge session, i.e., the remaining part
of the game (outside the encryption protocol) remains the same as Game 0. Precisely, this means
that the challenger uses r0∗ to check the validity of the last message r0 provided by the adversary in
the challenge session, i.e., it checks whether r0 = r0∗ .

Via a straightforward reduction to the iCCA-security of the encryption protocol, it is possible to show
that there exists an adversary B such that

Pr[G0 ] − Pr[G1 ] ≤ 2 · AdviCCA

Π0 ,B (λ)

Finally, if we analyze Game 1, it is not hard to see that in order to let Game 1 output 1, the
adversary has to correctly guess the value of r0∗ . However, in Game 1, the string r0∗ is randomly chosen
and is not used in the encryption protocol. Hence, its value is information-theoretically hidden to any
adversary A. Hence, we have that Pr[G1 ] ≤ 21λ , which is negligible, as desired. t
u

F Postponed Proofs

F.1 Proof of Claim 1

Proof (Claim 1). Assume by contradiction that there exists an efficient adversary A such that Pr[Forge] ≥
 for a non-negligible value . Then we show how to build a PPT adversary B that has non-negligible
advantage against the iCMA security of the message transmission protocol Π0 .
B is given in input the public receiver key recvk0 and it has oracle access to the sender S0 (sendk0 , ·).
B proceeds as follows:
– Run A(sendk) with sendk = recvk0 .
– For every oracle query asking to interact with a new copy of R: generate a new encryption key pair
(ek, dk) ← KG(1λ ), and query S0 (sendk0 , ek) to simulate the first part of the protocol.
$

– When the adversary makes the last query to R on a session that is already opened: let ek be the first
message previously generated in the above step, and let c be the message sent by A for this query.
B answers by computing m←Dec(dk, C) (where dk is the decryption key generated by B together
with ek).
– When A outputs the message pair (m0 , m1 ), B also starts its challenge session, and forwards all A’s
messages of the subprotocol Π0 to its challenger. If Π0 in the challenge session terminates with ek∗ ,
then B returns ek∗ .
If Forge occurs then, by the definition of the event, A is not ping-pong and thus B is not ping-pong
either. Hence, Advsuf -cma (λ) = Pr[Forge] ≥ , which concludes the proof of the claim. t
u
B,Σ

F.2 Proof of Theorem 3 (iCCA security)

Assume by contradiction there exists a PPT adversary A that breaks the iCCA security of Π0 , then we
show how to build a PPT algorithm B that uses A as a subroutine to break the iCCA security of Π.
Here too, we distinguish between the above two cases according to which party speaks first.

27
1. R speaks first. B is run on input sendk. It runs A(sendk) and answers oracle queries as follows.
Since in Π0 it is S0 who speaks first, when A will query R0 to start a new session, A will also send a
nonce r ∈ {0, 1}λ . B stores r, queries R and returns its answer to A. R0 oracle queries for sessions
that already started before are forwarded by B to R, except for the following change for the last
message. B forwards the message received from A to R. Let (m0 |r0 ) be its response, and let r be the
string stored for this session by B. If r = r0 then B returns m0 . Otherwise, it returns ⊥.
$
When A outputs a message pair (m0 , m1 ) B chooses a random string r∗ ← {0, 1}λ \ {r1 , . . . , rQ }
(where r1 , . . . , rQ are all the strings sent by A to the oracle R0 in the previous phase), and sends
r∗ to A. Note that as long as the r string is sufficiently large, the distribution of this choice of r∗
is statistically close to the one in the real experiment. So, B outputs (r∗ |m0 , r∗ |m1 ) as its message
pair, and continues the simulation by forwarding the remaining messages of the challenge session to
its challenger.
In this second phase, all oracle queries are answered as before, except for the following change.
Assume that the challenge session is completed, let T ∗ = h(r∗ , t∗1 ), (M1∗ , t∗2 ), . . . , (Mn∗ , t∗n+1 )i be its
transcript, and assume that A queries R0 on an already opened session by sending the last message. B
should then answer with the output of R0 . Let T = h(r, t1 ), (M1 , t2 ), . . . , (Mn , tn+1 )i be the transcript
of the queried session. Since A is not ping-pong, T 6≡ T ∗ , and we would like to argue that B must
not be ping-pong as well while still being capable to answer queries correctly.
0
Let us write T ∗ = (r∗ , t∗1 ), T ∗ and T = (r, t1 ), T 0 (i.e., we explicitly separate the first message from
the transcript of the n-round protocol). If T 6≡ T ∗ , either one of the following cases holds:
0
– T 0 6≡ T ∗ : B is not ping-pong in its game and it can answer the query by forwarding A’s last
message to its oracle R.
0
– T 0 ≡ T ∗ , t∗1 > t1 and r = r∗ : t∗1 > t1 means that r∗ was generated after r has been sent from A.
However, by construction of the simulation it must be r∗ 6= r. So, this case cannot occur.
0
– T 0 ≡ T ∗ , t∗1 < t1 and r∗ 6= r: This means that all timestamps are correctly alternating, and the
two sessions differ only in the first message, i.e., r 6= r∗ . This is the case where B changes its
way of answering: it does not forward the last message to its oracle R, and returns ⊥ to A. We
0
argue that B’s answer is correct. Indeed, since T 0 ≡ T ∗ , by correctness of Π, R’s private output
will be a message of the form r∗ |mb . However, since r∗ 6= r R0 would reject this message
At the end, B returns the same output of A.
2. S speaks first. B is run on input sendk. It runs A(sendk) and answers oracle queries as follows.
Since in Π0 it is R0 who speaks first, when A will query R0 on a new session, A does not send any
message, and B simulates the answer by returning a randomly chosen string r ∈ {0, 1}λ . B stores r,
and then forward all subsequent queries on this session to its oracle R, forwarding the corresponding
answers to A. The only change is in simulating answers to the last message. B forwards the message
received from A to R. Let (m0 |r0 ) be its response, and let r be the string stored for this session by
B. If r = r0 then B returns m0 . Otherwise, it returns ⊥.
When A outputs a message pair (m0 , m1 ) — recall that A (who is playing the role of the receiver)
is supposed to speak first in the challenge session — B waits for the message r∗ ∈ {0, 1}λ from A.
B stores r∗ and starts forwarding all messages to its own challenge session which is initialized by
choosing (r∗ |m0 , r∗ |m1 ) as the challenge message pair.
In this second phase all oracle queries are answered as before, except for the following changes. First,
$
in every query from A to R0 to open a new session, B chooses the nonce r ← {0, 1}λ \{r∗ }. It is easy to
see that the distribution of this choice of r is statistically close to the one in the real experiment. Sec-
ond, assume that the challenge session is completed, let T ∗ = h(r∗ , t∗1 ), (M1∗ , t∗2 ), . . . , (Mn∗ , t∗n+1 )i be
its transcript, and assume that A queries R0 on an already opened session by sending the last message.
B should then answer with the (simulated) output of R0 . Let T = h(r, t1 ), (M1 , t2 ), . . . , (Mn , tn+1 )i
be the transcript of the queried session. Since A is not ping-pong, T 6≡ T ∗ , and we would like to
argue that B must not be ping-pong as well while still being capable to answer queries correctly.

28
 0
Let us write T ∗ = (r∗ , t∗1 ), T ∗ and T = (r, t1 ), T 0 (i.e., we explicitly separate the first message from
the transcript of the n-round protocol). If T 6≡ T ∗ , either one of the following cases holds:
0
– T 0 6≡ T ∗ : B is clearly not ping-pong and it can answer forwarding this query to its oracle R.
0
– T 0 ≡ T ∗ , t1 > t∗1 and r = r∗ : t1 > t∗1 means that r was generated by B after r∗ has been sent by
A. However, by construction of B (see above) we always have r∗ 6= r. So this case cannot occur.
0
– T 0 ≡ T ∗ , t1 < t∗1 and r∗ 6= r: This means that all timestamps are correctly alternating, and the
two sessions differ only in the first message, i.e., r 6= r∗ . In this case B outputs ⊥. By the same
reasons in case (1) of the proof, this answer is correct.
At the end, B returns the same output of A. t
u

F.3 Proof of Theorem 3 (iCMA security)

Assume by contradiction there exists a PPT adversary A that breaks the iCMA security of Π0 , then we
show how to build a PPT algorithm B that uses A as a subroutine in order to break the iCMA security
of Π. We distinguish between the following two cases according to which party speaks first.

1. R speaks first. B is run on input recvk. It runs A(recvk) and answers oracle queries as follows.
Since in Π0 it is S0 who speaks first, when A queries S0 on a new session (providing a plaintext m),
B simulates the first message from S0 by returning a random string r ∈ {0, 1}λ , which is stored by
B. All subsequent queries on this session are forwarded from B to its oracle S (initialized with the
plaintext m|r).
When A starts the challenge session, A must start speaking by sending a string r∗ . B stores r∗ ,
starts its challenge session and forwards all messages to and from A. After the challenge session has
$
started, B chooses the nonces r ← {0, 1}λ \ {r∗ }. It is easy to see that the distribution of this choice
of r is statistically close to the one in the real experiment.
Observe that by construction of R0 , if A makes R0 (recvk) accept and return a message m∗ in the
simulated challenge session with B, then B (who forwards the very same queries) will make R(recvk)
accept with message r∗ |m∗ in its challenge session. Therefore, to complete the proof, it is left to show
that if A is not ping-pong, the same holds for B. Namely, let T ∗ = h(r∗ , t∗1 ), (M1∗ , t∗2 ), . . . , (Mn∗ , t∗n+1 )i
be the transcript of the challenge session between B (simulating R0 (recvk)) and A, and let T =
h(r, t1 ), (M1 , t2 ), . . . , (Mn , tn+1 )i be the transcript of the any session between A and its oracle S0
0
(simulated by B). Since A is not ping-pong, T 6≡ T ∗ . Let us write T ∗ = (r∗ , t∗1 ), T ∗ and T = (r, t1 ), T 0
(i.e., we explicitly separate the first message from the transcript of the n-round protocol). If T 6≡ T ∗ ,
either one of the following cases holds:
0
– T 0 6≡ T ∗ : B is also not ping-pong in its game.
0
– T 0 ≡ T ∗ , t∗1 > t1 and r = r∗ : t∗1 > t1 means that r∗ was generated after r has been sent from
A. However, by construction of the simulation we only have r 6= r∗ , and thus this case cannot
occur.
0
– T 0 ≡ T ∗ , t∗1 < t1 and r∗ 6= r: This means that all timestamps are correctly alternating, and the
0
two sessions differ only in the first message, i.e., r 6= r∗ . Since T 0 ≡ T ∗ , by correctness of Π, R
would accept in the challenge session with a message of the form m∗ |r∗ , but this implies that R0
rejects this message as r∗ 6= r.
2. S speaks first. B is run on input recvk. It runs A(recvk) and answer oracle queries as follows. Since
in Π0 it is R0 who speaks first, when A will query S0 on a new session, A has to provide a string r
(in addition to the chosen plaintext m). B then queries its oracle S with plaintext m|r and starts
forwarding all subsequent queries of this session to A.
$
When A starts the challenge session, B chooses a random string r∗ ← {0, 1}λ \ {r1 , . . . , rQ } (where
r1 , . . . , rQ are all the strings sent by A to the oracle R0 in the previous phase), and sends r∗ to A. Note
that as long as the r string is sufficiently large, the distribution of this choice of r∗ is statistically

29
close to the one in the real experiment. Next, in the challenge session B simply relay all messages
between A and its challenger.
Observe that by construction of R0 , if A would make R0 (recvk) accept and return a message m∗ in the
simulated challenge session with B, then B (who forwards the very same messages) can make R(recvk)
accept with message m∗ |r∗ in its challenge session. Therefore, to complete the proof, it is left to show
that if A is not ping-pong, the same holds for B. Namely, let T ∗ = h(r∗ , t∗1 ), (M1∗ , t∗2 ), . . . , (Mn∗ , t∗n+1 )i
be the transcript of the challenge session between B (simulating R0 (recvk)) and A, and let T =
h(r, t1 ), (M1 , t2 ), . . . , (Mn , tn+1 )i be the transcript of any session between A and its oracle S0 (sim-
0
ulated by B). Since A is not ping-pong, T 6≡ T ∗ . Let us write T ∗ = (r∗ , t∗1 ), T ∗ and T = (r, t1 ), T 0
(i.e., we explicitly separate the first message from the transcript of the n-round protocol). If T 6≡ T ∗ ,
either one of the following cases holds:
0
– T 0 6≡ T ∗ : B is clearly not ping-pong in its game.
0
– T 0 ≡ T ∗ , t1 > t∗1 and r = r∗ : t1 > t∗1 means that r was generated after r∗ has been sent from
A. However, by construction of the simulation we only have r 6= r∗ , and thus this case cannot
occur.
0
– T 0 ≡ T ∗ , t1 < t∗1 and r∗ 6= r: This means that all timestamps are correctly alternating, and the
0
two sessions differ only in the first message, i.e., r 6= r∗ . Since T 0 ≡ T ∗ , by correctness of Π, R
would accept in the challenge session with a message of the form m∗ |r∗ , but this implies that R0
rejects this message as r∗ 6= r. t
u

30