International Association
for Cryptologic Research

In the problem of anonymous authentication (Boneh et al. CCS 1999), a sender wishes to authenticate a message to a given recipient in a way that preserves anonymity: the recipient does not know the identity of the sender and only is assured that the sender belongs to some authorized set. Although solutions for the problem exist (for example, by using ring signatures, e.g. Naor, Crypto 2002), they provide no security when the anonymity set is a singleton. This work is motivated by the question of whether there is any type of anonymity possible in this scenario. It turns out that we can still protect the identity of all senders (authorized or not) if we shift our concern from preventing the identity information be revealed to the recipient to preventing it could be revealed to an external entity, other than the recipient. We define a natural functionality which provides such guarantees and we denote it by F_{eaa} for externally anonymous authenticated channel.

We argue that any realization of F_{eaa} must be deniable in the sense of Dodis et al. TCC 2009. To prove the deniability of similar primitives, previous work defined ad hoc notions of deniability for each task, and then each notion was showed equivalent to realizing the primitive in the Generalized Universal Composability framework (GUC, Canetti et al. TCC 2007). Instead, we put forward the question of whether deniability can be defined independently from any particular task. We answer this question in the affirmative providing a natural extension of the definition of Dodis et al. for arbitrary multiparty protocols. Furthermore, we show that a protocol satisfies this definition if an only if it realizes the ideal functionality F_{eaa} in the GUC framework. This result enables us to prove that most GUC functionalities we are aware of (and their realizations) are deniable.

We conclude by applying our results to the construction of a deniable protocol that realizes F_{eaa}.