PRIVACY-PRESERVING FLEXIBLE ANONYMOUS-PSEUDONYMOUS ACCESS

• US 20120265997A1
• Filed: 06/22/2012
• Published: 10/18/2012
• Est. Priority Date: 06/23/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Laurie, Bennet, Yung, Marcel M. Moti
• Granted Patent: US 9,154,306 B2
• Time in Patent Office: Days
• US Class Current: 713/185
• CPC Class Codes: G06F 21/31 User authentication
• 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 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 63/0421 Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/0815 providing single-sign-on or federations
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• 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/3257 using blind signatures

Abstract

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.

Claims

1. A computer-implemented method of authorizing access for a user to a relying party (RP), mediated by an identity provider (IdP), comprising:

receiving the user'"'"'s registration of a first pseudonym at the IdP in a previous session;

upon verification of the user'"'"'s possession of the first pseudonym, generating, by a processor, a first representation of an access token to the user for accessing the RP, wherein the first representation of the access token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP, the first representation of the access token being modifiable to a second representation of the access token that is unlinkable to the first representation of the access token, and the second representation of the access token remaining as a valid access token for accessing the RP; and

providing the first representation of the access token to the user for accessing the RP.

2. The method of claim 1, further comprising:

receiving a modified token from the user, wherein the modified token is generated by a cryptographic transformation from a original token, the original token is generated from a pre-image, and the pre-image supports both fixed-format and free-format information structures and contains information that is revealed to the RP but not to the IdP.

3. The method of claim 1, further comprising:

receiving the second representation of the access token, wherein the second presentation of the access token is derived from the first representation of the access token by the user; and

verifying the second representation of the access token without ability to link the second representation of the access token to the first representation of the access token.

4. The method of claim 1, wherein the first representation and the second representation of the access token are publicly verifiable, and the verification of the second representation of the access token is performed by the RP.

5. The method of claim 1, wherein the first representation and the second representation of the access token are privately verifiable by the IdP, and the verification of the second representation of the access token is performed by the IdP.

6. The method of claim 1, wherein the first representation of the access token includes a confirmation of at least some user characteristics required for access at the RP.

7. The method of claim 6, wherein the IdP is an authority with information regarding user characteristics, and the method further comprises checking access requirements of the RP and verifying the user characteristics for access eligibility at the RP.

8. A computer-readable storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving the user'"'"'s registration of a first pseudonym at the IdP in a previous session;

upon verification of the user'"'"'s possession of the first pseudonym, generating, by a processor, a first representation of an access token to the user for accessing the RP, wherein the first representation of the access token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP, the first representation of the access token being modifiable to a second representation of the access token that is unlinkable to the first representation of the access token, and the second representation of the access token remaining as a valid access token for accessing the RP; and

providing the first representation of the access token to the user for accessing the RP.

9. The computer-readable storage medium of claim 8, wherein the operations further comprise:

receiving a modified token from the user, wherein the modified token is generated by a cryptographic transformation from a original token, the original token is generated from a pre-image, and the pre-image supports both fixed-format and free-format information structures and contains information that is revealed to the RP but not to the IdP.

10. The computer-readable storage medium of claim 8, wherein the operations further comprise:

receiving the second representation of the access token, wherein the second presentation of the access token is derived from the first representation of the access token by the user; and

verifying the second representation of the access token without ability to link the second representation of the access token to the first representation of the access token.

11. The computer-readable storage medium of claim 8, wherein the first representation and the second representation of the access token are publicly verifiable, and the verification of the second representation of the access token is performed by the RP.

12. The computer-readable storage medium of claim 8, wherein the first representation and the second representation of the access token are privately verifiable by the IdP, and the verification of the second representation of the access token is performed by the IdP.

13. The computer-readable storage medium of claim 8, wherein the first representation of the access token includes a confirmation of at least some user characteristics required for access at the RP.

14. The computer-readable storage medium of claim 13, wherein the IdP is an authority with information regarding user characteristics, and the method further comprises checking access requirements of the RP and verifying the user characteristics for access eligibility at the RP.

15. A system comprising:

one or more computers; and

a computer-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving the user'"'"'s registration of a first pseudonym at the IdP in a previous session;

upon verification of the user'"'"'s possession of the first pseudonym, generating, by a processor, a first representation of an access token to the user for accessing the RP, wherein the first representation of the access token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP, the first representation of the access token being modifiable to a second representation of the access token that is unlinkable to the first representation of the access token, and the second representation of the access token remaining as a valid access token for accessing the RP; and

providing the first representation of the access token to the user for accessing the RP.

16. The system of claim 15, wherein the operations further comprise:

receiving a modified token from the user, wherein the modified token is generated by a cryptographic transformation from a original token, the original token is generated from a pre-image, and the pre-image supports both fixed-format and free-format information structures and contains information that is revealed to the RP but not to the IdP.

17. The system of claim 15, wherein the operations further comprise:

receiving the second representation of the access token, wherein the second presentation of the access token is derived from the first representation of the access token by the user; and

verifying the second representation of the access token without ability to link the second representation of the access token to the first representation of the access token.

18. The system of claim 15, wherein the first representation and the second representation of the access token are publicly verifiable, and the verification of the second representation of the access token is performed by the RP.

19. The system of claim 15, wherein the first representation and the second representation of the access token are privately verifiable by the IdP, and the verification of the second representation of the access token is performed by the IdP.

20. The system of claim 15, wherein the first representation of the access token includes a confirmation of at least some user characteristics required for access at the RP.

21. The system of claim 20, wherein the IdP is an authority with information regarding user characteristics, and the method further comprises checking access requirements of the RP and verifying the user characteristics for access eligibility at the RP.

22. A computer-implemented method of allowing access for a user to a relying party (RP), mediated by an identity provider (IdP), comprising:

receiving a request to access the RP from the user, the request comprising a second representation of an access token, the second representation of the access token being based on a first representation of the access token issued to the user by the IdP, the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP individually, and the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP in collusion;

if the first representation of the access token is publicly verifiable,

verifying, by a processor, the second representation of the access token; and

providing access to the user upon successful verification of the second representation of the access token;

if the first representation of the access token is privately verifiable by the IdP,

presenting the second representation of the access token to the IdP for verification; and

providing access to the user if the IdP successfully verifies the second representation of the access token.

23. The method of claim 22, wherein the request is for anonymous access at the RP, and the anonymous access is unlinkable to any previous and future access at the RP.

24. The method of claim 22, wherein the request is for pseudonymous access at the RP, and the pseudonymous access is linkable to a pseudonym previously registered at the RP.

25. The method of claim 24, further comprising:

receiving proof of possession of the pseudonym previously registered at the RP, wherein the proof is made by a zero-knowledge proof, by signing, or by decrypting a challenge.

26. The method of claim 22, wherein the request further comprises a pre-image, the pre-image supports both fixed-format and free-format information structures, the pre-image contains user-specific information that is revealed to the RP but not to the IdP, and the first representation of the access token is generated from the pre-image through cryptographic transformations by the user and the IdP.

27. The method of claim 26, wherein the RP is one of a plurality of RPs, the IdP is one of a plurality of IdPs, and the pre-image encodes information that is specific to the RP and the IdP.

28. The method of claim 22, wherein the information token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP.

29. A tangible computer-readable storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a request to access the RP from the user, the request comprising a second representation of an access token, the second representation of the access token being based on a first representation of the access token issued to the user by the IdP, the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP individually, and the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP in collusion;

if the first representation of the access token is publicly verifiable,

verifying, by a processor, the second representation of the access token; and

providing access to the user upon successful verification of the second representation of the access token;

if the first representation of the access token is privately verifiable by the IdP,

presenting the second representation of the access token to the IdP for verification; and

providing access to the user if the IdP successfully verifies the second representation of the access token.

30. The computer-readable storage medium of claim 29, wherein the request is for anonymous access at the RP, and the anonymous access is unlinkable to any previous and future access at the RP.

31. The computer-readable storage medium of claim 29, wherein the request is for pseudonymous access at the RP, and the pseudonymous access is linkable to a pseudonym previously registered at the RP.

32. The computer-readable storage medium of claim 31, wherein the operations further comprise:

receiving proof of possession of the pseudonym previously registered at the RP, wherein the proof is made by a zero-knowledge proof, by signing, or by decrypting a challenge.

33. The computer-readable storage medium of claim 29, wherein the request further comprises a pre-image, the pre-image supports both fixed-format and free-format information structures, the pre-image contains user-specific information that is revealed to the RP but not to the IdP, and the first representation of the access token is generated from the pre-image through cryptographic transformations by the user and the IdP.

34. The computer-readable storage medium of claim 33, wherein the RP is one of a plurality of RPs, the IdP is one of a plurality of IdPs, and the pre-image encodes information that is specific to the RP and the IdP.

35. The computer-readable storage medium of claim 29, wherein the information token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP.

36. A system comprising:

one or more computers; and

a computer-readable storage medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving a request to access the RP from the user, the request comprising a second representation of an access token, the second representation of the access token being based on a first representation of the access token issued to the user by the IdP, the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP individually, and the second representation of the access token being unlinkable to the first representation of the access token by the RP and the IdP in collusion;

if the first representation of the access token is publicly verifiable,

verifying, by a processor, the second representation of the access token; and

providing access to the user upon successful verification of the second representation of the access token;

if the first representation of the access token is privately verifiable by the IdP,

presenting the second representation of the access token to the IdP for verification; and

providing access to the user if the IdP successfully verifies the second representation of the access token.

37. The system of claim 36, wherein the request is for anonymous access at the RP, and the anonymous access is unlinkable to any previous and future access at the RP.

38. The system of claim 36, wherein the request is for pseudonymous access at the RP, and the pseudonymous access is linkable to a pseudonym previously registered at the RP.

39. The system of claim 38, wherein the operations further comprise:

receiving proof of possession of the pseudonym previously registered at the RP, wherein the proof is made by a zero-knowledge proof, by signing, or by decrypting a challenge.

40. The system of claim 36, wherein the request further comprises a pre-image, the pre-image supports both fixed-format and free-format information structures, the pre-image contains user-specific information that is revealed to the RP but not to the IdP, and the first representation of the access token is generated from the pre-image through cryptographic transformations by the user and the IdP.

41. The system of claim 40, wherein the RP is one of a plurality of RPs, the IdP is one of a plurality of IdPs, and the pre-image encodes information that is specific to the RP and the IdP.

42. The system of claim 36, wherein the information token selectively encodes a partial disclosure based on one or more characteristics of the user known to the IdP, the partial disclosure being a confirmation of at least some characteristics required for user access at the RP.

43. A system for managing user access at relying parties (RPs), mediated by identity providers (IdPs), the system comprising:

a first subsystem for a user to prove possession of a first pseudonym previously registered with an IdP to the IdP;

a second subsystem for the user to obtain a first representation of an access token from the IdP for accessing an RP anonymously;

a third subsystem for the user to modify the first representation of the access token to obtain a second representation of the access token for anonymous access at the RP, where the second representation of the access token is unlinkable to the first representation of the access token by the IdP;

a fourth subsystem for the user to present the second representation of the access token to the RP either anonymously or pseudonymously based on user choice;

a fifth subsystem for the user to connect the second representation of the access token to one of the user'"'"'s pseudonyms previously registered at the RP, wherein the user'"'"'s pseudonyms registered at the RP are unlinkable to the pseudonym registered at the IdP;

a sixth subsystem for the user to prove possession of a second pseudonym previously registered with the RP to the RP; and

a seventh subsystem for allowing user access to the RP upon successful cryptographic proof of either the second representation of the access token for anonymous access, or the second representation of the access token and the pseudonym previously registered with the RP for pseudonymous access.

44. The system of claim 43, further comprising:

an eighth subsystem for the user to present to the RP a pre-image of an original token, wherein the pre-image supports fixed format and free-format data structures, and the first presentation of the access token is based on the original token.

45. The system of claim 44, further comprising:

a ninth subsystem for the user to generate multiple pseudonyms based on a single secret key for registration with at least one of RPs and IdPs, the multiple pseudonyms being unlinkable by the RPs and the IdPs individually, and being unlinkable by the RPs and the IdPs in collusion, wherein the multiple pseudonyms are selectively linkable by the user in a zero-knowledge fashion.

46. The system of claim 43, further comprising:

A tenth subsystem for routing interactions from the user to the RP via a proxy system to hide routing information of the user from the RP.

47. A method, comprising:

maintaining a pseudonym system on a device, the pseudonym system operable to generate an unbounded number of pseudonyms based on a fixed number of cryptographic keys;

generating a plurality of pseudonyms for establishing respective pseudonymous identities with a plurality of entities, the plurality of pseudonyms being generated by the pseudonym system based on at least one of the fixed number of cryptographic keys, and the plurality of pseudonyms being unlinkable to one another by entities that do not possess the cryptographic key;

registering each of the plurality of pseudonymous identities with a respective entity in the plurality of entities using a corresponding pseudonym in the plurality of pseudonyms; and

reproducing and proving possession of each pseudonymous identity without maintaining a persistent copy of the corresponding pseudonym.