Notions of Deniable Message Authentication

Deniable message authentication has drawn significant attention since it was first formalized by Dwork, Naor, and Sahai (STOC 1998). Since then, multiple notions of deniability have been introduced that vary in the considered adversary model and the required level of deniability. Most of the previous works concentrate on fairly strong notions of deniability, allowing the prover to even dispute that an interaction took place. In practice, however, weaker forms of deniability may suffice, such as being able to deny that a certain message has been transmitted at a certain point in time. Our work here thus introduces alternative notions of deniable message authentication, including for example content deniability (where one can deny the actual message) and context deniability (where one can claim that the allegedly transmitted message is taken out of context). We then analyze existing approaches, carving out the deniability properties these protocols achieve. In particular, we investigate the off-the-record messaging protocol (OTR) of Borisov, Goldberg, and Brewer (WPES 2004), which lists deniability of authentication as one of its explicit goals, but escapes the strong notions of deniability in the literature.