Paper 2006/280

Deniable Authentication and Key Exchange

Mario Di Raimondo, Rosario Gennaro, and Hugo Krawczyk


We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis. SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first ``natural'' application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model. SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, ``partial deniability" property: a party may not be able to deny that it was ``alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors. We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Accepted to ACM CCS'06. This is the current full version.
Key ExchangeAuthenticationDeniabilityPrivacyZero-KnowledgePlaintext-Awareness
Contact author(s)
rosario @ us ibm com
2006-08-19: received
Short URL
Creative Commons Attribution


      author = {Mario Di Raimondo and Rosario Gennaro and Hugo Krawczyk},
      title = {Deniable Authentication and Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2006/280},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.