You are looking at a specific version 20140122:085452 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
public-key encryptiondigital signatureschosen-ciphertext securityman-in-the-middle attacksanonymous key-exchange
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.