Paper 2013/817

Interactive Encryption and Message Authentication

Yevgeniy Dodis and Dario Fiore


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) {\em 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 {\em deniable} (resp. {\em 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 {\em 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 {\em 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.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.SCN 2014
public-key encryptiondigital signatureschosen-ciphertext securityman-in-the-middle attacks
Contact author(s)
dario fiore @ imdea org
2014-07-25: last of 4 revisions
2013-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yevgeniy Dodis and Dario Fiore},
      title = {Interactive Encryption and Message Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2013/817},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.