Systems and methods are disclosed for privacy-preserving flexible user-selected anonymous and pseudonymous access at a relying party (RP), mediated by an identity provider (IdP). Anonymous access is unlinkable to any previous or future accesses of the user at the RP. Pseudonymous access allows the user to associate the access to a pseudonym previously registered at the RP. A pseudonym system is disclosed. The pseudonym system allows a large number of different and unlinkable pseudonyms to be generated using only a small number of secrets held by the user. The pseudonym system can generate tokens capable of including rich semantics in both a fixed format and a free format. The tokens can be used in obtaining from the IdP, confirmation of access privilege and/or of selective partial disclosure of user characteristics required for access at the RPs. The pseudonym system and associated protocols also support user-enabled linkability between pseudonyms.