Pseudonym Systems (Extended Abstract)
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, Stefan Wolf · 2000
Abstract. Pseudonym systems allow users to interact with multiple organizations anonymously, using pseudonyms. The pseudonyms cannot be linked, but are formed in such away that a user can prove to one organization a statement about his relationship with another. Such a statement is called a credential. Previous work in this area did not protect the system against dishonest users who collectively use their pseudonyms and credentials, i.e., share an identity. Previous practical schemes also relied very heavily on the involvement of a trusted center. In the present paper we give a formal de nition of pseudonym systems where users are motivated not to share their identity, and in which the trusted center's involvement is minimal. We give theoretical constructions for such systems based on any one-way function. We also suggest an e cient and easy-to-implement practical scheme.