Information Security and Cryptography Research Group

Pseudonym Systems

Anna Lysyanskaya, Ronald Rivest, Amit Sahai, and Stefan Wolf

Proceedings of Selected Areas in Cryptography — SAC '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1758, pp. 184–199, Aug 1999.

Pseudonym systems allow users to interact with multiple organizations anonymously, using pseudonyms. The pseudonyms cannot be linked, but are formed in such a way that a user can prove to one organization a statement about his relationship with another. Such a statement is called acredential. 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 definition 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 efficient and easy-to-implement practical scheme.

BibTeX Citation

    author       = {Anna Lysyanskaya and Ronald Rivest and Amit Sahai and Stefan Wolf},
    title        = {Pseudonym Systems},
    booktitle    = {Proceedings of Selected Areas in Cryptography --- SAC~'99},
    pages        = {184--199},
    series       = {Lecture Notes in Computer Science},
    volume       = {1758},
    year         = {1999},
    month        = {8},
    publisher    = {Springer-Verlag},

Files and Links