On the Relationship Between Weak and Strong Deniable Authenticated Encryption

Abstract

Consider a scenario in which a whistleblower (Alice) would like to disclose confidential documents to a journalist (Bob). Bob wants to verify that the messages he receives are really from Alice; at the same time, Alice does not want to be implicated if Bob is later compelled to (or decides to) disclose her messages, together with his secret key and any other relevant secret information. To fulfil these requirements, Alice and Bob can use a deniable authenticated encryption scheme. In this paper we formalize the notions of strong- and weak deniable authentication, and discuss the relationship between these definitions. We show that Bob can still securely authenticate messages from Alice after all his secret information is revealed to the adversary, but only when using a weakly (but not strongly) deniable scheme. We refer to this ability as post-compromise message authentication. We present two efficient encryption schemes that provide deniable authentication. Both schemes incur overhead similar to that of non-deniable schemes. As such, they are suitable not only when deniability is needed, but also as general encryption tools. We provide details of the encryption, decryption, forgery and keygeneration algorithms, and formally prove that our schemes are secure with respect to confidentiality, data authentication, and strong- and weak deniable authentication.