Non-transferable anonymous credentials

• US 7,222,362 B1
• Filed: 05/15/2000
• Issued: 05/22/2007
• Est. Priority Date: 05/15/2000
• Status: Expired due to Term

• Current Assignee: Rakuten, Inc. (Rakuten Group, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Ravikumar, Shanmugasundaram, Tomkins, Andrew S., Rajagopalan, Sridhar, Sahai, Amit, Charikar, Moses Samson, Canetti, Ran
• Primary Examiner(s): Revak; Christopher
• Assistant Examiner(s): Abrishamkar; Kaveh
• Application Number:
  US09/571,602
• Time in Patent Office: 2,563 Days
• Field of Search: 713/200, 713/201, 713/169, 713/155, 726/5, 726/18
• US Class Current: 726/5
• 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/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

Abstract

An anonymous credential system which requires a user who is asserting a credential to have knowledge of the master key of the user who was originally granted that credential. In order for a user to transfer the ability to assert any one of their credentials to another user, they must also transfer their master key to that same user. The master key, however, provides such unlimited rights to its holder that a user is strongly motivated not to share their master key with anyone else. In this manner, anonymous credentials become non-transferrable because a user cannot transfer a credential without transferring their entire electronic identity.

Claims

1. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret;

said master secret comprising a private key, s, of a public/private key encryption pair and said public key, EU, generated by a commitment algorithm, C, performed on private key, s, and denoted C(s), said assertion repeated at least once, said method comprising the steps;

receiving said assertion from said user;

for said received assertion and each repeated instance, thereof;

receiving from said user an initiation of a multi-party protocol in which a prover provides a proof of knowledge of said master secret;

verifying said proof;

wherein said proof is a zero knowledge proof of knowledge;

accepting said at least one AC only if said verifying step is successful, wherein requiring successful completion of said proof for said received assertion and each repeated instance, thereof before accepting said at least one AC prevents transferring said at least one AC without also transferring said master secret, and

said at least one AC granted by an organization O_i based on receiving a request for each of said at least one AC, (O_i;

;

x_i) from a party, authenticating an identity of said party, generating a message, m_i=<

C(s), (O_i;

;

x_i)>

, generating a signed message σ

_i=S_oi(m_i) wherein S_oi is a public signing key of said O_i, and sending σ

_i to said party.

2. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 1, wherein said step of accepting said at least one AC is performed by a doorkeeper.

3. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 1 wherein said proof comprises proving in zero knowledge:

∃

σ

₁, . . . , σ

_k, m₁, . . . , m_k, s such that ∀

iI≦

i≦

k, σ

_i=S_Oi(m_i)

and ∀

i1≦

i≦

k, m_i=<

C(s), O_i;

;

x_i>

and E_U=C(s).

4. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 1, wherein said at least one AC is used for one of anonymous health testing, a web cookie, file access control in a distributed filesystem, or a non-transferable proxy power.

5. A method for accepting from a user an assertion of at least on anonymous credential (AC) granted to a party having a master secret, as per claim 1, wherein said method may be implemented locally or remotely on one or more computer based systems, across networks or existing communication mediums.

6. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 5, wherein said networks comprise any of:

LANs, WANs, cellular, Internet, or Web-based networks.

7. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, comprising the steps:

receiving from a user an assertion of said at least one AC;

receiving from said user an encryption key E″

;

sending a random number, R, to said user;

receiving A=E″

(D_U⊕

R) from said user;

receiving from said user an initiation of an interactive zero knowledge proof of knowledge of said master secret;

verifying said proof of knowledge;

accepting said at least one AC only if said verifying step is successful, and wherein requiring successful completion of said proof of knowledge before accepting said at least one AC prevents transferring said at least one AC without also transferring said master secret, and including E″

, R and A to provide a non-transferrable session.

8. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 7, wherein said AC is granted to said party by an organization.

9. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 8, wherein said organization also performs said step of accepting said at least one AC.

10. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 7, wherein said step of accepting said at least one AC is performed by a doorkeeper.

11. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 7, wherein said master secret is a private key of a public/private encryption key pair.

12. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 7, wherein each of said at least one AC is granted by an O_i in accordance with a method comprising the steps:

receiving, by said O_i, an encryption key E_i′

from said party;

sending a random number, R_i, to said party;

receiving from said party a message, m_i=<

E_i′

, E_i′

(D_U⊕

R_i), R_i, O_i;

;

x_i>

;

verifying a format of said m_i;

receiving an initiation of a multi-party protocol in which said party provides a proof of knowledge of E_i′

(D_U⊕

R_i);

verifying said proof of knowledge of E_i′

(D_U⊕

R_i);

generating a signed message, σ

_i=S_oi(m_i) wherein S_oi is a private signing key of O_i, and sending said σ

_i to said party.

13. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 12 wherein said proof of knowledge of said master secret comprises proving:

∃

σ

₁, . . . , σ

_k, E′

₁, . . . , E′

_k, R₁, . . . , R_k, m₁, . . . , m_k, D_U such that ∀

i1≦

i≦

k, σ

_i=S_oi(m_i)

and ∀

i1≦

i≦

k, m_i=<

E′

_i, E′

_i(D_U⊕

R_i), R_i, O_i;

;

x_i>

, and

A=E″

(D_U⊕

R).

14. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 7, comprising the additional steps:

receiving a receipt message from said user;

receiving, from said user, an initiation of a zero-knowledge proof of knowledge of said receipt message having a valid format, and

verifying said zero-knowledge proof of knowledge of said receipt message having a valid format.

15. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 14, wherein each of said at least one AC is granted by an O_i in accordance with a method comprising the steps:

selecting, by O_i, a public/private encryption key pair <

E_Oi, D_Oi>

;

receiving, by said O_i, an encryption key E_i′

from said party;

sending a random number, R_i, to said party;

receiving from said party a message, m_i=<

E_i′

, E_i′

(D_U⊕

R_i), R_i, O_i;

;

x_i>

;

verifying a format of said m_i;

receiving an initiation of a zero-knowledge proof of knowledge of E_i′

(D_U⊕

R_i) from said party;

verifying said zero-knowledge proof of knowledge of E_i′

(D_U⊕

R_i);

generating a signed message, σ

_i=S_oi(m_i) wherein S_oi is a private signing key of O_i;

sending said σ

_i to said party;

generating an encryption pair <

P_U, S_U>

, and

sending said pair <

P_U, S_U>

to said party.

16. A method of processing at least one anonymous credential (AC) granted to a party having a master secret, D_U, as per claim 15, wherein a doorkeeper, N_D, performs said step of accepting said at least one AC and said receipt message comprises E_oi(S_U(O_i:

;

x_i, N_D)).

17. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 7, wherein said method may be implemented locally or remotely on one or more computer based systems, across networks or existing communication mediums.

18. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, as per claim 17, wherein said networks comprise any of:

LANs, WANs, cellular, Internet, or Web-based networks.

19. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, said master secret comprising a private key, s, of a public/private encryption pair and said public key, EU, generated by a commitment algorithm, C, performed on private key, s, and denoted C(s), said assertion repeated at least once, wherein each of said at least one AC is granted by an organization, O_i, in accordance with a method comprising the steps:

receiving said assertion from said user;

for said received assertion and each repeated instance, thereof;

receiving from said user an initiation of a multi-party protocol in which a prover provides a proof of knowledge of said master secret;

verifying said proof;

wherein said proof is a zero knowledge proof of knowledge;

accepting said at least one AC only if said verifying step is successful, wherein requiring successful completion of said proof for said received assertion and each repeated instance thereof, before accepting said at least one AC, prevents transferring said at least one AC without also transferring said master secret, and

said at least one AC granted by an organization O_i being based on receiving a request from a party for said each of said at least one AC, (O_i;

;

x_i), receiving a random number, r, from said party, and sending to said party a message, S_oi(O_i;

;

x_i, r), wherein S_oi is a private signing key of O_i, and wherein S_oi(O_i;

;

x_i, r) allows linking of a plurality of assertions of (O_i;

;

x_i), said linking performed by a doorkeeper receiving said plurality of assertions.

20. A method for accepting from a user an assertion of at least one anonymous credential (AC) granted to a party having a master secret, said method comprising:

receiving said assertion from said user;

for said received assertion and each repeated instance, thereof;

receiving from said user an initiation of a multi-party protocol in which a prover provides a proof of knowledge of said master secret;

verifying said proof, said verifying said proof comprises said user revealing a discrete logarithm modulo a large prime, q, of a first value, v, relative to a second value, u, said verifying step further comprising;

receiving from said user a pair (u, v) such that t∈

Z_q and v=u^t;

choosing a first random value c∈

Z_q, and a second random value, s∈

Z_q;

computing a commitment, a_o=u^cv^s;

sending a_o to said user;

receiving from said user a first value, a, such that r is a random value, r∈

Z_q, and a=g^r;

sending (c, s) to said user;

receiving from said user a second value, b=cx+r(mod q), wherein x is said master secret;

receiving from said user said random exponent t;

comparing a first equality, g^b=h^ca, and a second equality, u^t=v;

determining verifying said proof is successful if both said first equality and said second equality are true, and

wherein p is a large prime number, p−

1 has a large prime factor q, g is a generator of a multiplicative group of order q in Z_p*, and h=g^s for some random element s∈

z_q chosen by the user,

accepting said at least one AC only if said verifying step is successful,

wherein requiring successful completion of said proof for said received assertion and each repeated instance thereof, before accepting said at least one AC, prevents transferring said at least one AC without also transferring said master secret.