Cryptology ePrint Archive: Report 2014/073

Anonymous Authentication with Shared Secrets

Joel Alwen and Martin Hirt and Ueli Maurer and Arpita Patra and Pavel Raykov

Abstract: Anonymity and authenticity are both important yet often conflicting security goals in a wide range of applications. On the one hand for many applications (say for access control) it is crucial to be able to verify the identity of a given legitimate party (a.k.a. entity authentication). Alternatively an application might require that no one but a party can communicate on its behalf (a.k.a. message authentication). Yet, on the other hand privacy concerns also dictate that anonymity of a legitimate party should be preserved; that is no information concerning the identity of parties should be leaked to an outside entity eavesdropping on the communication. This conflict becomes even more acute when considering anonymity with respect to an active entity that may attempt to impersonate other parties in the system.

In this work we resolve this conflict in two steps. First we formalize what it means for a system to provide both authenticity and anonymity even in the presence of an active man-in-the-middle adversary for various specific applications such as message and entity authentication using the constructive cryptography framework of~\cite{Mau11}. Our approach inherits the composability statement of constructive cryptography and can therefore be directly used in any higher-level context. Next we demonstrate several simple protocols for realizing these systems, at times relying on a new type of (probabilistic) Message Authentication Code (MAC) called \emph{key indistinguishable} (KI) MACs. Similar to the key hiding encryption schemes of~\cite{BellareBDP01} they guarantee that tags leak no discernible information about the keys used to generate them.

Category / Keywords: foundations / Anonymity, Authentication, Key Indistinguishabilitiy

Date: received 3 Feb 2014

Contact author: raykov pavel at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140204:170130 (All versions of this report)

Short URL: ia.cr/2014/073

Discussion forum: Show discussion | Start new discussion