The present invention relates to a method and system for securely proving ownership of pseudonymous or anonymous electronic credentials. A credential system is described consisting of users and organizations. An organization knows a user only by a pseudonym. The pseudonyms of the same user, established for use with different organizations, cannot be linked. An organization can issue a credential to a pseudonym, and the corresponding user can prove possession of this credential to another organization that knows him under another pseudonym. During the prove of possession of the credential nothing besides the fact that he owns such a credential is revealed. A refinement of the credential system provides credentials for unlimited use, so called multiple-show credentials, and credentials for one-time use, so called one-show credentials.