Cryptology ePrint Archive: Report 2013/817

Interactive Encryption, Message Authentication, and Anonymous Key Exchange

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 $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. We also define and construct stronger forms of necessarily interactive PKE/PKMA schemes, called {\em confirmed encryption} and {\em confidential authentication}.

Anonymous Key Exchange. We extend our definitional framework for interactive PKE and PKMA schemes to give definitions and constructions of (necessarily interactive) {\em anonymous key exchange} (1-KE), where an anonymous (unkeyed) party establishes a key with an authenticated (keyed) party. Unlike the prior work, defining 1-KE by ``downgrading'' the hairy and complex definition of {\em mutually authenticated} key exchange (2-KE), our definition is very ``short'' and easy to understand. We also show simple and general connections between anonymous KE and (interactive) confirmed PKE/confidential PKMA schemes. As a result, we obtain old and new schemes for anonymous KE in a clean and modular manner.

Category / Keywords: foundations / public-key encryption, digital signatures, chosen-ciphertext security, man-in-the-middle attacks, anonymous key-exchange

Date: received 4 Dec 2013, last revised 22 Jan 2014

Contact author: dario fiore at imdea org

Available format(s): PDF | BibTeX Citation

Version: 20140122:085452 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]