Untraceable electronic cash

• US 5,768,385 A
• Filed: 08/29/1995
• Issued: 06/16/1998
• Est. Priority Date: 08/29/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Simon, Daniel R.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/521,124
• Time in Patent Office: 1,022 Days
• Field of Search: 380/23, 380/24, 380/25, 380/29, 380/30, 380/49, 380/59, 380/4, 380/9, 380/50
• US Class Current: 705/69
• CPC Class Codes: G06Q 20/0425 the cheque being electronic only
• 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/24 Credit schemes, i.e. "pay after"
• 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/383 Anonymous user system
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00

Abstract

An electronic cash protocol including the steps of using a one-way function f₁ (x) to generate an image f₁ (x₁) from a preimage x₁ ; sending the image f₁ (x₁) in an unblinded form to a second party; and receiving from the second party a note including a digital signature, wherein the note represents a commitment by the second party to credit a predetermined amount of money to a first presenter of the preimage x₁ to the second party.

Claims

1. A method of implementing an electronic cash protocol comprising the steps of:

using a one-way function f₁ (x) to generate an image f₁ (x₁ ) from a preimage x₁ ;

sending the image f₁ (x₁) in an unblinded form to a second party; and

receiving from the second party a note including a digital signature, said note representing a commitment by the second party to credit a predetermined amount of money to a first presenter of said preimage x₁ to the second party.

2. The method of claim 1 further comprising sending the preimage x₁ to a third party as payment for purchase of goods or services from the third party.

3. The method of claim 1 further comprising:

selecting a second preimage x₂ ;

using a second one-way function f₂ (x)to generate a second image f₂ (x₂) from the second preimage x₂ ;

sending the first preimage x₁ and the unblinded form of the second image f₂ (x₂) to the second party; and

receiving from the second party a second note including a digital signature, said second note representing a commitment by the second party to credit said predetermined amount of money to a first presenter of said second preimage x₂ to the second party.

4. The method of claim 3 wherein functions f₁ (x) and f₂ (x) are identical to each other.

5. The method of claim 4 wherein the step of sending the first preimage x₁ and the unblinded form of the second image f₂ (x₂) to the second party is performed anonymously.

6. The method of claim 5 wherein the second party is a bank.

7. The method of claim 3 further comprising sending the second preimage x₂ to a third party as payment for purchase of goods or services from the third party.

8. The method of claim 1 further comprising:

concatenating a signature key of a third party with the first preimage x₁ to form a block of information;

encrypting the block of information by using an encryption key of the second party to generate an encrypted block of information; and

sending the encrypted block of information to the third party.

9. A method of implementing an electronic cash protocol comprising the steps of:

receiving a first preimage x₁ from a first party, said preimage x₁ producing a first image f₁ (x₁) when processed by a first one-way function f₁ (x) and there being associated with said first preimage x₁ a commitment by a second party to credit a predetermined amount of money to a first presenter to the second party of said first preimage x₁ ;

selecting a second preimage x₂ ;

using a second one-way function f₂ (x)to generate a second image f₂ (x₂) from the second preimage x₂ ;

sending the first preimage x₁ and an unblinded form of the second image f₂ (x₂) to the second party; and

receiving from the second party a note including a digital signature, said note representing a commitment by the second party to credit said predetermined amount of money to a first presenter of said second preimage x₂ to the second party.

10. The method of claim 9 wherein functions f₁ (x) and f₂ (x) are identical to each other.

11. The method of claim 9 wherein the step of sending the first preimage x₁ and the unblinded form of the second image f₂ (x₂) to the second party is performed anonymously.

12. A method of implementing an electronic cash protocol comprising the steps of:

receiving from a first party an encrypted block of information, wherein said block of encrypted information was generated by first concatenating a public signature key of a second party with a first preimage x₁ to form a block of information and then encrypting the block of information by using an encryption key of a third party;

selecting a second preimage x₂ ;

using a second one-way function f₂ (x) to generate an image f(x₂) from the preimage x₂ ;

forming a message including the encrypted block of information along with the image f(x₂) in an unblinded form;

sending the message to the third party; and

receiving from the third party a signed note including a digital signature, said note representing a commitment by the third party to credit a predetermined amount of money to a first presenter of said preimage x₂ to the third party.

13. The method of claim 12 wherein functions f₁ (x) and f₂ (x) are identical to each other.

14. The method of claim 12 further comprising signing the message before sending it to the third party, wherein the step of signing is performed using a private signature key corresponding to a public signature key possessed by the third party.

15. The method of claim 12 wherein the second party is the party receiving the encrypted block of information from the first party.

16. A method of implementing an electronic cash protocol comprising the steps of:

receiving from a first entity an unblinded form of an image f₁ (x₁) that was generated by applying a one-way function f₁ (x) to a preimage x₁ ;

generating a message which contains a commitment to credit a predetermined amount of money to a first presenter of said preimage x₁ ;

signing said message with a digital signature; and

sending said message along with said digital signature to said first party.

17. The method of claim 16 wherein the receiving party maintains an account for the first entity and wherein said protocol further comprises debiting the first party'"'"'s account by the predetermined amount of money.

18. The method of claim 16 further comprising:

subsequently receiving the preimage x₁ from a third party;

checking a database for the preimage x₁ ;

if the preimage x₁ is not found in said database, crediting the third party with said predetermined amount of money; and

adding the preimage x₁ to said database.

19. The method of claim 16 further comprising:

subsequently receiving the preimage x₁ and an unblinded image f₂ (x₂) from a third party, wherein the unblinded image f₂ (x₂) was generated by applying a one-way function f₂ (x) to a preimage x₂ ;

checking a database for the preimage x₁ ;

if the preimage x₁ is not found in said database, generating a signed note including a digital signature, said note representing a commitment to credit said predetermined amount of money to a first presenter of said preimage x₂ ; and

adding the preimage x₁ to said database.

20. The method of claim 19 wherein functions f₁ (x) and f₂ (x) are identical to each other.

21. The method of claim 16 further comprising:

receiving a message from a second party, wherein said message was generated by concatenating an encryption key of a third party with a first preimage x₁ to form a block of information, by encrypting the block of information by using a first encryption key to generate an encrypted first block, and by concatenating an unblinded image f₂ (x₂) to the encrypted first block of information, wherein said unblinded image f₂ (x₂) was generated by using a one-way function f₂ (x) to generate an image f₂ (x₂) from a preimage x₂ ;

decrypting the encrypted first block of information;

generating a note including a digital signature, said note representing a commitment to credit a predetermined amount of money to a first presenter of said preimage x₂ ; and

sending said note to the second party.

22. The method of claim 21 wherein functions f₁ (x) and f₂ (x) are identical to each other.

23. The method of claim 21 further comprising:

checking a database for the preimage x₁ ;

generating the signed note only if the preimage x₁ is not found in said database; and

adding the preimage x₁ to said database.

24. A method of implementing an electronic cash protocol comprising the steps of:

obtaining a first image f(x₁) and a first preimage x₁, wherein said first preimage x₁ has a predetermined monetary value associated therewith;

selecting a second preimage x₂ ;

using a second one-way function f₂ (x)to generate a second image f₂ (x₂) from the second preimage x₂ ;

sending the first preimage x₁ and an unblinded form of the second image f₂ (x₂) to the second party; and

receiving from the second party a note including a digital signature, said note representing a commitment by the second party to credit a predetermined amount of money to a first presenter of said second preimage x₂ to the second party, wherein said predetermined amount of money is no greater than said predetermined monetary value.

25. The method of claim 24 wherein said predetermined amount of money is less than said predetermined monetary value.

26. The method of claim 24 wherein fx₁ (x) equals f₂ (x).

27. A method of implementing an electronic cash protocol comprising the steps of:

obtaining a first image f(x₁) and a first preimage x₁, wherein said first preimage x₁ has a predetermined monetary value associated therewith;

selecting a plurality of preimages x_i, wherein I is an integer index that runs from 1 to n, where n is a positive integer;

using a second one-way function f₂ (x) to generate a plurality of images f₂ (x_i) from the second preimages x_i ;

sending the first preimage x₁ and an unblinded form of all of the images f₂ (x_i) to the second party; and

receiving from the second party a plurality of each including a digital signature, said plurality of notes equal in number to the plurality of images f₂ (x_i) and representing a plurality of predetermined amounts, each of said plurality of notes representing a commitment by the second party to credit a corresponding different one of said plurality of predetermined amounts of money to a first presenter of the corresponding preimage x_i to the second party, wherein the total of said plurality of predetermined amounts of money equals said predetermined monetary value.

28. A method of implementing an electronic cash protocol comprising the steps of:

obtaining a first image f(x₁) and a first preimage x₁, wherein said first preimage x₁ has a predetermined monetary value associated therewith;

concatenating a signature key of a second party with the first preimage x₁ to form a block of information;

encrypting the block of information by using an encryption key of a third party to generate an encrypted block of information; and

sending the encrypted block of information to the third party.

29. The method of claim 28 further comprising concatenating other information with the signature key of a second party and the first preimage x₁ to form the block of information.

30. A method of implementing an electronic cash protocol comprising the steps of:

sending an unblinded image f₂ (x₂) to a second party, wherein the unblinded image f₂ (x₂) was generated by applying a one-way function f₂ (x) to a preimage x₂ ;

receiving a signed note from the second party, said unblinded note including a digital signature, said unblinded note representing a commitment to credit said predetermined amount of money to a first presenter of said preimage x₂ ; and

in response to receiving the unblinded note from the second party, authorizing the delivery of goods or services to a third party.