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.Category / Keywords: cryptographic protocols / Key Exchange, Authentication, Deniability, Privacy, Zero-Knowledge, Plaintext-Awareness Publication Info: Accepted to ACM CCS'06. This is the current full version. Date: received 17 Aug 2006 Contact author: rosario at us ibm com Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20060819:180931 (All versions of this report) Discussion forum: Show discussion | Start new discussion