Efficient electronic money

• US 5,511,121 A
• Filed: 09/08/1994
• Issued: 04/23/1996
• Est. Priority Date: 02/23/1994
• Status: Expired due to Term

• Current Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Yacobi, Yacov
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/303,048
• Time in Patent Office: 593 Days
• Field of Search: 380/23, 380/24, 380/25, 380/28, 380/30
• US Class Current: 705/69
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/06 Private payment circuits, e.g. involving electronic currency used among participants of a common payment scheme
• CPC Class Codes: G06Q 20/3678 e-cash details, e.g. blinded, divisible or detecting double spending
• CPC Class Codes: G06Q 20/3825 Use of electronic signatures
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: G06Q 20/383 Anonymous user system
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes
• CPC Class Codes: H04L 9/3257 using blind signatures
• 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

A unique electronic cash system protects the privacy of users in legitimate transactions while at the same time enabling the detection of a double spender of the same electronic coin. The electronic cash system takes advantage of a unique property of El Gamal signatures to achieve these results.

Claims

1. A method for performing an electronic cash transaction comprising the step of

transmitting via a communications link from a first electronic coin processing unit to a second electronic coin processing unit an electronic coin comprising a linkage of a public key of a party and a random element, said linkage being signed using a secret operation of a public key cryptographic system, wherein said public key has the form

View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)

2. The method of claim 1 wherein said linkage is signed using an RSA secret exponent of a bank.

3. The method of claim 1 wherein said transmitting step comprises transmitting said electronic coin via a wireless link.

4. The method of claim 1 wherein said transmitting step comprises transmitting said electronic coin via a public switched telephone network.

5. The method of claim 1 wherein said first electronic coin processing unit is a first money module belonging to a first party i.

6. The method of claim 5 wherein said first money module comprises a central processing unit and a memory.

7. The method of claim 5 wherein said second electronic coin processing unit is a second money module belonging to a second party j.

8. The method of claim 7 wherein said transaction comprises transmitting said coin from said first money module of said first party i to said second money module of said second party j.

9. The method of claims 8 further comprising the steps of

a) transmitting a message m from the party j to the party i,

b) signing the message m at the party i with a signature from the El Gamal family,

c) transmitting the signature to the party j, and

d) verifying the signature at the party j.

10. The method of claim 7 wherein said second money module comprises a central processing unit and a memory.

11. The method of claim 1 wherein said first electronic coin processing unit is a money module belonging to a party j and said second electronic coin processing unit is a bank.

12. The method of claim 11 wherein said transmitting step comprises transmitting said electronic coin from said party j to said bank.

13. The method of claim 12 wherein said the public key in said electronic coin transmitted from said party j to said bank is the public key of a party i who transferred the coin to the party j.

14. The method of claim 13 further comprising the steps of transmitting from said party j to said bank an El Gamal family signature of the party i on a message m and said message m.

15. The method of claim 14 further comprising the steps of

a) maintaining in a memory at said bank a list of coins and corresponding El Gamal family signatures,

b) comparing said coin transmitted to said bank from said party j with the coins in said list,

c) if there is a collision between said coin, transmitted from said party j and a coin on said list, utilizing the El Gamal family signature transmitted from the party j and the El Gamal family signature of the coin in the list to identify a double spender.

16. The method of claim 15 further comprising the steps of

d) transmitting to said bank from the party j a certificate of a public key of the party j, and

e) transmitting from the bank to the party j a new coin equal in value to the coin originally transmitted from the party j to the bank.

17. A method for detecting the double spending of a particular electronic coin in an electronic coin system where each of the coins comprises a certified linkage of a public key of a user and a random element,

said method comprising the steps of

a) storing in a memory a list of coins and El Gamal family signatures on messages obtained using the public keys and random elements in the coins,

b) using an electronic processor, comparing said particular coin to the coins on the list, and

c) if said particular coin and a coin on said list match, using a particular El Gamal family signature of said particular coin on a particular message and the El Gamal family signature and message of said coin on said list to identify a double spender.

18. The method of claim 17 wherein said certified linkage is of the form C.tbd.f(P_i,u,0.sup.γ

)^d$ mod N_$

where

P_i is a public key of a user i,

u is said random element,

0.sup.γ

is a string of γ

zeros,

d_$ is the secret RSA exponent of a bank,

N_$ is a modulus of the bank.

19. The method of claim 18 wherein said public key P_i is of the form

20. A method for performing a payment using an electronic coin system comprising the steps of

a) transmitting an electronic coin from a money module belonging to user i to a money module belonging to user j, said electronic coin comprising a certified linkage of a public key P_i of the user i in which there is embedded the identity I_i of the user i and a random value u chosen by the user i,

b) transmitting a message m from said money module of said user j to the money module of the user i,

c) utilizing a processor in the money module of the user i, generating an El Gamal family signature s of the message m using P_i and u,

d) transmitting the signature s to the money module of the party j, and

e) verifying said signature s at the money module of the party j and storing the coin at a memory in the money module of the party j.

21. The method of claim 20 wherein said linkage is signed using a secret key of a bank.

22. The method of claim 20 wherein said secret key of said bank is a secret RSA exponent of said bank.

23. The method of claim 21 further comprising the step of

at said money module of said party j, verifying said coin using a public key of said bank.

24. The method of claim 23 wherein said public key of said bank is a public RSA exponent.

25. The method of claim 20 wherein P_i is a public El Gamal Key and S_i is a secret El Gamal Key of a party i.

26. The method of claim 20 wherein said certified linkage is of the form C.tbd.f(P_i,u,0.sup.γ

)^d$ mod N_$

where

P_i is said public of said user i,

u is said random element,

0.sup.γ

is a string of γ

zeros,

d_$ is a secret RSA exponent of a bank,

N_$ is a modulus of the bank.

27. The method of claim 26 wherein said public key P_i is of the form

28. A method for processing an electronic coin at a bank station containing a processing unit and a memory comprising the steps of:

a) receiving at said bank station a particular electronic coin comprising a certified linkage of a public key P_i of a party i, and a random value u chosen by the party i,

b) using said processing unit at said bank station, comparing said particular coin to a list of electronic coins maintained by said bank in said memory, and

c) if said coin matches a coin in said list, using a message m and an El Gamal family signature s on the message m obtained using P_i and u of said particular coin, and an El Gamal family signature and corresponding message associated with said coin on said list to identify a double spender.

29. The method of claim 28 wherein said coin is received at said bank from a party j other than said party i.

30. The method of claim 28 further comprising the step of receiving at said bank a certificate containing a different public key and a different random value, forming a new certified linkage of said different public key and different random value, and transmitting the new certified linkage to a particular party.

31. The method of claim 28 wherein said certified linkage is of the form C.tbd.f(P_i,u,O.sup.γ

)^d$ mod N_$

where

P_i is said public of said user i,

u is said random element,

0.sup.γ

is a string of γ

zeros,

d_$ is a secret RSA exponent of a bank,

N_$ is a modulus of the bank.

32. The method of claim 31 wherein said public key P_i is of the form

33. A method for electronically withdrawing an electronic coin from a bank comprising the steps of

a) using a processor of a user, performing a blinding operation to blind a candidate linkage, which blinded candidate linkage includes a public key of the user and a random element,

b) transmitting via a communication link from the user to the bank the identity of the user and the blinded candidate linkage,

c) transmitting from the user to the bank an indication to said bank that the public key of the user has an identity of the user embedded therein without revealing the public key of the user to the bank,

d) utilizing a processor at said bank, signing said blinded candidate linkage using a secret key of said bank and transmitting the signed blinded candidate linkage to said user, and

e) at said user, generating a coin from the signed blinded candidate linkage, wherein said public key is of the form

34. A method for certifying a public key of a user of an electronic cash system comprising the steps of

a) utilizing an electronic processor of a user, performing a blinding operation on a candidate certificate to generate a blinded candidate certificate, said blinded candidate certificate including a public key of a user i of the form P_i .tbd.α

^S_i mod p, where S_i is a secret key of the user i containing an identity I_i of the user i, and α and

p are publicly known numbers,

b) transmitting via a communication link, said blinded candidate certificate to a certificate authority,

c) transmitting via said communication link an indication to said certificate authority that P_i contains I_i without revealing P_i to the certificate authority,

d) utilizing a processor at said certificate authority, signing said blinded candidate certificate using a secret key of said certificate authority and transmitting the signed blinded candidate certificate to said user i, and

e) at said user i, generating a certificate from said signed blinded candidate certificate.

35. The method of claim 34 wherein said candidate certificate has the form f(P_i, O.sup.γ

),

36. A method for refreshing a certificate of a public key of a user in an electronic cash system comprising the steps of:

(a) transmitting from a user i to a certificate authority an old certificate of an old public key P_i that includes an identity Ii of the user i,

(b) at the user i, using an electronic processor, selecting a new public key P_i '"'"' including the identity I_i, and forming a blinded candidate refresh certificate including said new key P_i '"'"',

(c) transmitting from said user i to said certificate authority said blinded candidate refresh certificate,

(d) transmitting to said certificate authority an indication that P_i '"'"' contains the same I_i as P_i without revealing P_i to said certificate authority,

(e) utilizing an electronic processor at said certificate authority, signing said blinded candidate refresh certificate using a secret key of the certificate authority and transmitting the signed blinded candidate refresh certificate to the user i, and

(f) at said user i, generating a refresh certificate from said signed blinded candidate refresh certificate.

37. The method of claim 36 wherein:

Pi is of the form Pi.tbd.α

^Si mod p, where Si is an old secret key that includes an identity Ii of the user i, and

Pi'"'"' is of the form Pi.tbd.α

^Si mod p, where Si'"'"' is a new secret key including the identity Ii.

38. An electronic coin that can be transmitted via a communications link and stored in an electronic memory and comprising a certified linkage between a public key P_i of a party i and a random element chosen by the party i, the identity I_i of the party i being embedded in the discrete log of the public key and being exposed when there is double spending of the coin.

39. The electronic coin of claim 38 wherein said certified linkage is signed using a secret operation of a public key cryptography system.

40. The electronic coin of claim 39 wherein said certified linkage is signed using an RSA secret exponent.

41. The electronic coin of claim 40 wherein said certified linkage has the form

42. An electronic coin that can be transmitted via a communications link between a first electronic coin processing unit and a second electronic coin processing unit and comprising a certified linkage of a public key P_i .tbd.α

^Si mod p of a user i, where S_i is a secret key of the user i and includes the identity I_i of the user i and α and

p are public numbers, and a random element.

43. The electronic coin of claim 42 wherein said random element is a value u.tbd.α

^r mod p, where r is a random secret integer chosen by a user i for the coin.

44. The electronic coin of claim 42 wherein said certified linkage is signed using a secret operation of a public key cryptographic system.

45. A public key cryptographic method comprising the steps of:

(a) selecting a cryptographic key for a user i, said cryptographic key containing specific predetermined information,

(b) at a certificate authority, using an electronic processor, certifying that said cryptographic key contains said specific predetermined information,

(c) transmitting via a communication link a certificate of said cryptographic key to said user i, and

(d) utilizing said certified public key by said user i in a plurality of real time cryptographic transactions.

46. The method of claim 45 wherein said cryptographic key is a public key P_i of a user i, said specific information is the identity I_i of the user i and said certificate has the form f(P_i,0.sup.γ

)^dc where 0.sup.γ

is a run of γ

zeros and dc is a secret RSA exponent of the certificate authority.

47. The method of claim 46 wherein said public key has a form P_i .tbd.α

^Si mod p, where S_i is a secret key of the user i, and where α and

p are public numbers.

48. The method of claim 45 wherein said certifying step comprises using said electronic processor to sign a candidate certificate including said public key with a secret key of said certificate authority.

49. The method of claim 45 wherein said real time cryptographic transactions comprise transactions utilizing e-coins incorporating said cryptographic key.

50. An electronic money exchange transaction comprising the steps of

(a) transmitting an old electronic coin having a specific monetary value from a user j to a bank via a communications network, said user j having received said electronic coin from another user i,

(b) verifying said coin using an electronic processor at said bank,

(c) at said bank, using said electronic processor, generating a certified linkage of a public key of said user j and a random element known to said user j and transmitting said certified linkage to said user j via said communications network.

51. The method of claim 50 wherein said certified linkage has the form