Non-transferable anonymous credential system with optional anonymity revocation

• US 7,360,080 B2
• Filed: 11/02/2001
• Issued: 04/15/2008
• Est. Priority Date: 11/03/2000
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Camnisch, Jan Leonhard, Lysyanskaya, Anna
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): PATEL, NIRAV B
• Application Number:
  US10/000,918
• Publication Number:
  US 20020103999A1
• Time in Patent Office: 2,356 Days
• Field of Search: 713156-158, 713/182, 713/175, 705 74- 76, 705 64- 68, 726/5, 726/9
• US Class Current: 713/156
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

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.

Claims

1. A method for establishing a pseudonym system by having a certificate authority accepting a user as a new participant in said pseudonym system, the method comprising the steps of:

receiving a first public key provided by said user;

verifying that said user is allowed to join the system;

computing a credential by signing the first public key using a secret key owned by said certificate authority; and

publishing said first public key and said credential,

wherein

the step of receiving a first public key further includes receiving an external public key being registered for said user with an external public key infrastructure and receiving an encryption of a secret key encrypted by using said first public key;

the step of verifying that said user is allowed to join the system further includes verifying that said external public key is indeed registered with said external public key infrastructure;

the step of publishing said first public key and said credential comprises publishing said encryption and the name of the external public key infrastructure; and

additionally comprises the step of proving that the secret key corresponding to said external public key is encrypted in said received encryption.

2. The method according to claim 1, wherein

said first public key of the user is derived from at least one first secret key composed by the user.

3. The method according to claim 2, wherein

the step of receiving a first public key derived from a first secret key further comprises receiving a second public key which is derived from a second and a third secret key composed by the user;

and

the step of computing a credential by signing the first public key using a secret key owned by said certificate authority further comprises computing a credential by signing the second public key using said secret key owned by said certificate authority.

4. A computer program product stored on a computer usable medium, comprising computer readable program means for executing the method in claim 1 by a computer.

5. A method for establishing a pseudonym system by having an organization register a user, the method comprising the steps of:

receiving a first public key provided by said user;

receiving a first encryption encrypted by using said first public key;

proving that an existing public key is registered for said user with another organization of said pseudonym system and proving that the secret key corresponding to said existing public key is encrypted in said received first encryption;

publishing said first public key, said first encryption and the name of said other organization.

6. The method according to claim 5, wherein

proving that an existing public key is registered for said user with said other organization of said pseudonym system and proving that the secret key corresponding to said existing public key is encrypted in said received first encryption includes proving possession of a credential issued by said organization of said existing public key.

7. The method according to claim 6, wherein

the step of receiving a first encryption encrypted by using said first public key further comprises receiving a second encryption encrypted by using said existing public key;

the step of proving that the secret key corresponding to said existing public key is encrypted in said received first encryption further comprises proving that the secret key corresponding to said first public key is encrypted in said received second encryption; and

the step of publishing said first public key, said first encryption, and the name of said other organization further comprises publishing said second encryption.

8. The method according to claim 7, wherein

the step of receiving a first encryption encrypted by using said first public key further comprises receiving a third encryption encrypted by using a public key published by a revocation manager;

and

the step of proving that the secret key corresponding to said existing public key is encrypted in said received first encryption further comprises proving that said existing public key is encrypted in said received third encryption.

9. The method according to claim 8, wherein

the first public key of the user is derived from at least two secret keys composed by the user.

10. The method according to claim 9, wherein

the step of proving that the secret key corresponding to said first public key is encrypted in said received second encryption includes proving that all of said at least two secret keys corresponding to said first public key are encrypted in said second encryption.

11. The method according to claim 10, further comprising a step of

proving that the first public key is derived from at least two secret keys and proving that one of the secret keys is identical to one of the secret keys used to derive another public key from which the user claims it is registered with another organization.

12. The method according to claim 11, wherein

the existing public key of the user is derived from at least two secret keys composed by the user.

13. The method according to claim 12, wherein

the step of proving that the secret key corresponding to said existing public key is encrypted in said received first encryption includes proving that all of said at least two secret keys corresponding to said existing public key are encrypted in said first encryption.

14. The method according to claim 13, further comprising the steps of

receiving a third public key provided by said user;

proving that one secret key used to derive said third public key is identical to one secret key used to derive said existing public key from which the user claims it is registered with a specified organization.

15. The method according to claim 14, further comprising the step of:

computing a credential by signing the first public key using a secret key owned by said organization;

and wherein the step of publishing said first public key, said first encryption and the name of said other organization further comprises publishing said certificate.

16. The method according to claim 15, wherein

the step of receiving a first public key derived from a first secret key further comprises receiving a second public key which is derived from a second and a third secret key composed by the user;

and

the step of computing a credential by signing the first public key using a secret key owned by said certificate authority further comprises computing a credential by signing the first and second public key using said secret key owned by said certificate authority.

17. The method according to claim 5, further comprising the steps of:

receiving a request from an organization for revealing a pseudonym or the identity of the user;

judging whether it is justified to reveal the pseudonym or the identity of the user; and

sending the pseudonym or the identity of the user to the requesting organization, in case that this is justified.

18. A method for having a verifier checking possession of a credential by a user issued by a specified organization, the method comprising the steps of:

proving that an existing public key is registered for said user with said specified organization of said pseudonym system,

receiving a third encryption encrypted by using a public key published by a revocation manager; and

proving that said existing public key is encrypted in said received third encryption,

wherein the step of proving that an existing public key is registered for said user with said specified organization of said pseudonym system includes proving possession of a credential issued by said organization of said existing public key.

19. The method according to claim 18, further comprising the steps of:

receiving a third public key provided by said user;

proving that one secret key used to derive said third public key is identical to one secret key used to derive said existing public key from which the user claims it is registered with said specified organization.