BIB-VERSION:: CS-TR-v2.0 ID:: ncstrl.dartmouthcs//TR2008-615 ENTRY:: April 08, 2008 ORGANIZATION:: Dartmouth College, Computer Science REQUESTED-BY:: sws@cs.dartmouth.edu REQUESTED-FOR:: patrick@cs.dartmouth.edu REQUESTED-DATE:: Wed Apr 2 10:11:23 EDT 2008 TITLE:: PPAA: Peer-to-Peer Anonymous Authentication (Extended Version) TYPE:: Technical Report (paper) REVISION:: 2 AUTHOR:: Tsang, Patrick P. AUTHOR:: Smith, Sean W. DATE:: April 2008 RETRIEVAL:: For a paper copy, email RETRIEVAL:: For a paper copy, write to Technical Report Librarian Department of Computer Science Dartmouth College 6211 Sudikoff Laboratory Hanover, NH 03755-3510 USA RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2008-615.pdf ABSTRACT:: In the pursuit of authentication schemes that balance user privacy and accountability, numerous anonymous credential systems have been constructed. However, existing systems assume a client-server architecture in which only the clients, but not the servers, care about their privacy. In peer-to-peer (P2P) systems where both clients and servers are peer users with privacy concerns, no existing system correctly strikes that balance between privacy and accountability. In this paper, we provide this missing piece: a credential system in which peers are {\em pseudonymous} to one another (that is, two who interact more than once can recognize each other via pseudonyms) but are otherwise anonymous and unlinkable across different peers. Such a credential system finds applications in, e.g., Vehicular Ad-hoc Networks (VANets) and P2P networks. We formalize the security requirements of our proposed credential system, provide a construction for it, and prove the security of our construction. Our solution is efficient: its complexities are independent of the number of users in the system. NOTE:: This technical report is the extended version of the paper to appear in ACNS '08 under the same title. END:: ncstrl.dartmouthcs//TR2008-615