31-05-2012, 01:03 PM
An Efficient System for Non-transferable Anonymous Credentials
with Optional Anonymity Revocation
An E±cient System for Non-transferable Anonymous.pdf (Size: 320.2 KB / Downloads: 23)
Abstract
A credential system is a system in which users can obtain credentials from organizations and
demonstrate possession of these credentials. Such a system is anonymous when transactions
carried out by the same user cannot be linked. An anonymous credential system is of signi¯cant
practical relevance because it is the best means of providing privacy for users. In this paper we
propose a practical anonymous credential system that is based on the strong RSA assumption
and the decisional Di±e-Hellman assumption modulo a safe prime product and is considerably
superior to existing ones: (1) We give the ¯rst practical solution that allows a user to unlink-
ably demonstrate possession of a credential as many times as necessary without involving the
issuing organization.
Introduction
As information becomes increasingly accessible, protecting the privacy of individuals becomes a
more challenging task. To solve this problem, an application that allows the individual to control
the dissemination of personal information is needed. An anonymous credential system (also called
pseudonym system), introduced by Chaum [Cha85], is the best known idea for such a system.
In this paper, we propose a new e±cient anonymous credential system, considerably superior to
previously proposed ones. The communication and computation costs of our solution are small,
thus introducing almost no overhead to realizing privacy in a credential system.
Formal De¯nitions and Requirements
A basic credential system has users, organizations, and veri¯ers as types of players. Users are
entities that receive credentials. The set of users in the system may grow over time. Organizations
are entities that grant and verify the credentials of the users. Each organization grants a unique
(for simplicity of exposition) type of credential. Finally, veri¯ers are entities that verify credentials
of the users.
Protocol Notation
By neg(k) we denote any function that vanishes faster than any inverse polynomial in k. By poly(k)
we denote a function bounded by a polynomial in k.
In the description of our scheme, we use the notation introduced by Camenisch and Stadler[CS97]
for various proofs of knowledge of discrete logarithms and proofs of the validity of statements about
discrete logarithms. For instance,