Interactive encryption and message authentication

Yevgeniy Dodis, Dario Fiore

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 numbertheoretic 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.

Original languageEnglish (US)
Title of host publicationSecurity and Cryptography for Networks - 9th International Conference, SCN 2014, Proceedings
EditorsMichel Abdalla, Roberto de Prisco
PublisherSpringer Verlag
Number of pages20
ISBN (Electronic)9783319108780
StatePublished - 2014
Event9th International Conference on Security and Cryptography for Networks, SCN 2014 - Amalfi, Italy
Duration: Sep 3 2014Sep 5 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Security and Cryptography for Networks, SCN 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Interactive encryption and message authentication'. Together they form a unique fingerprint.

Cite this