Efficient And Deniable Authenticated Encryption

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, and have not been modified in transit. However, Alice does not want to be implicated if Bob later decides to (or is compelled to) disclose her messages, his secret key, and any other relevant secret information. To fulfill these requirements, Alice and Bob can use a "deniable authenticated" encryption scheme.  In this talk we present formalized the notions of strong- and weak deniable authentication. Although these terms have been used before in the cryptographic literature, they have not previously been defined in a rigorous way for encryption schemes. We present two efficient 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 key-generation algorithms, and formally prove that our schemes are secure with respect to confidentiality, data authentication, and strong- and weak deniable authentication.  We have made implementations of our schemes available as stand-alone command line tools, written in Python. We characterize the performance (both time- and space complexity) of these implementations, and show that our schemes incur very limited ciphertext expansion and computation overhead compared to standard symmetric encryption.