Deniable Authentication on the Internet

We revisit the question of deniable cryptographic primitives, where, intuitively, a malicious party observing the interaction, cannot later prove to a third party that the interaction took place. Example include deniable message authentication, key exchange and identification. While these question was heavily studied in the literature, we argue that none of the existing definitions (and solutions) to this question is satisfactory.

We propose the strongest and, arguably, the most natural and intuitive definition of deniability for these tasks: the proposed protocol should be secure in the recently proposed Generalized Universal Composability (GUC) Framework of Canetti, Dodis, Pass and Walfish.
Among other things, our definition guarantees on-line deniability and concurrent composition. Quite remarkably, our main result shows that none of the above mentioned tasks (identification, key exchange,
authentication) is realizable against adaptive attackers, even in the REGISTERED PUBLIC KEY MODEL (registered PKI), and even if data erasures are allowed. Registered PKI is the strongest setup assumption which is assumed to be “reasonable”. Thus, our result explains why all the previous attempts to solve deniability felt short of achieving the strongest form of deniability.

We also show that various slight relaxation of our notion ARE achievable, and discuss implications of our results to the general task of designing deniable protocols.