Composability and on-line deniability of authentication

Yevgeniy Dodis, Jonathan Katz, Adam Smith, Shabsi Walfish

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

41 Scopus citations


Protocols for deniable authentication achieve seemingly paradoxical guarantees: upon completion of the protocol the receiver is convinced that the sender authenticated the message, but neither party can convince anyone else that the other party took part in the protocol. We introduce and study on-line deniability, where deniability should hold even when one of the parties colludes with a third party during execution of the protocol. This turns out to generalize several realistic scenarios that are outside the scope of previous models. We show that a protocol achieves our definition of on-line deniability if and only if it realizes the message authentication functionality in the generalized universal composability framework; any protocol satisfying our definition thus automatically inherits strong composability guarantees. Unfortunately, we show that our definition is impossible to realize in the PKI model if adaptive corruptions are allowed (even if secure erasure is assumed). On the other hand, we show feasibility with respect to static corruptions (giving the first separation in terms of feasibility between the static and adaptive setting), and show how to realize a relaxation termed deniability with incriminating abort under adaptive corruptions.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 6th Theory of Cryptography Conference, TCC 2009, Proceedings
Number of pages17
StatePublished - 2009
Event6th Theory of Cryptography Conference, TCC 2009 - San Francisco, CA, United States
Duration: Mar 15 2009Mar 17 2009

Publication series

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


Other6th Theory of Cryptography Conference, TCC 2009
Country/TerritoryUnited States
CitySan Francisco, CA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Composability and on-line deniability of authentication'. Together they form a unique fingerprint.

Cite this