Interactive Encryption and Message Authentication

Yevgeniy Dodis; Dario Fiore

Paper 2013/817

Interactive Encryption and Message Authentication

Yevgeniy Dodis and Dario Fiore

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) {\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 -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 -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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. SCN 2014
Keywords: public-key encryption digital signatures chosen-ciphertext security man-in-the-middle attacks
Contact author(s): dario fiore @ imdea org
History: 2014-07-25: last of 4 revisions; 2013-12-06: received; See all versions
Short URL: https://ia.cr/2013/817
License: CC BY

BibTeX

@misc{cryptoeprint:2013/817,
      author = {Yevgeniy Dodis and Dario Fiore},
      title = {Interactive Encryption and Message Authentication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/817},
      year = {2013},
      url = {https://eprint.iacr.org/2013/817}
}