United States Patent [19]
`Simon
`
`|||||||||||||||||||||||||||||||||||
`5,768,385
`Jun. 16, 1998
`
`US005768385A
`[11] Patent Number:
`[45] Date of Patent:
`
`[54] UNTRACEABLE ELECTRONIC CASH
`[75] Inventor: Daniel R. Simon, Redmond, Wash.
`[73] Assignee: Microsoft Corporation, Redmond,
`Wash.
`
`[21] Appl. No.: 521,124
`[22] Filed:
`Aug. 29, 1995
`[51] Int. Cl* ...
`. H04L 9/00; HO4L 9/30
`[52] U.S. Cl. ................................. 380/24; 380/23: 380/25;
`380/30; 380/49
`[58] Field of Search .................................. 380/23, 24, 25.
`380/29, 30, 49, 59, 4, 9, 50
`
`[56]
`
`4,914,698
`4,947,430
`4,949,380
`4,987,593
`4,991,210
`4,996,711
`5,131,039
`5,276,736
`5,373,558
`
`References Cited
`U.S. PATENT DOCUMENTS
`4/1990
`8/1990
`8/1990
`1/1991
`2/1991
`2/1991
`7/1992
`1/1994
`12/1994
`OTHER PUBLICATIONS
`A. Pfitzmann, “How to Implement ISDNs Without User
`Observability—Some Remarks.” TR 14/85, Fakultät für
`Informatik Universität Karlsruhe, 1985.
`Okamoto, et al., “Universal Electronic Cash,”
`Proc.
`CRYPTO 191, Springer-Verlag (1992), pp. 324–337.
`Rompel, “One-Way Functions Are Necessary and Sufficient
`for Secure Signatures,” Proc. 31st IEEE Symp. on Founda
`tions of Computer Science (1990), pp. 387–394.
`Brands, “Untraceable Off-line Cash in Wallet with Observ
`ers” Proc. CRYPTO '93, Springer–Velag (1994) pp.
`302–318.
`Yacobi, “Efficient Electronic Money.” Proc. ASLACRYPT
`194. Springer-Verlag (1994).
`
`Proc.
`
`Rackoff, et al. “Cryptographic Defense Against Traffic
`Analysis.” Proc. 25th ACM Symp. on the Theory of Com
`putation (1993).
`Chaum, “Online Cash Checks.” Proc. EUROCRYPT '89,
`Springer-Verlag (1989), pp. 288–293.
`Chaum, “The Dining Cryptographers Problem: Uncondi
`tional Sender and Recipient Untraceability,” Journal of
`Cryptology, vol. 1, No. 1 (1988), pp. 65–75.
`Chaum, “Privacy Protected Payments—Unconditional
`Payer and/or Payee Untraceability.” Smart Card 2000: The
`Future of IC Cards—Proc. IFIP WG 11.6 Int’l Conf. North
`Holland (1989) pp. 69–93.
`Pfitzmann, et al. “ISDN-MDXes—Untraceable Communica
`tion with Very Small Brandwidth Overhead.” Proc. Kom
`munikation in verteilten Systemen (1991), pp. 451–463.
`Even, et al. “Electronic Wallet,” Proc. CRYPTO '83, Plenum
`Press (1984), pp. 383–386.
`Chaum, et al. “Untraceable Electronic Cash.”
`CRYPTO '88, Springerverlag (1990), pp. 319–327.
`Franklin, et al., “Secure and Efficient Off—Line Digital
`Money.” Proc. 20th Int’l Colloquim on Automata Languages
`and Programming. Springer-Verlag (1993), pp. 265–276.
`Chaum. “Achieving Electronic Privacy.” Scientific Ameri
`can, vol. 267. No. 2 (1992), pp. 96–101.
`Chaum, “Untraceable Electronic Mail, Return Addresses,
`and Digital Pseudonyms.” CACM, vol. 24, No. 2 (1981) pp.
`84–88.
`Primary Examiner—Bernarr E. Gregory
`Attorney, Agent, or Firm—Michaelson & Wallace; Peter L.
`Michaelson
`ABSTRACT
`[57]
`An electronic cash protocol including the steps of using a
`one-way function f(x) to generate an image fºx1) from a
`preimage xi.; sending the image fi(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 x1 to
`the second party.
`30 Claims, 2 Drawing Sheets
`
`
`
`
`
`10
`
`"Please ossian
`
`C(f(x)+ "The first presenter of the
`preimage of f(x1) will be credited $50;
`Signed, The Bank"
`
`PayPal Ex.1010, p.1
`
`

`
`U.S. Patent
`
`Jun. 16, 1998
`
`Sheet 1 of 2
`
`5,768,385
`
`------
`CUSIOMER
`
`
`
`10
`
`"Pleqse ossi
`
`C(f(x))+ "The first presenter of the
`preimage of f(x ) will be credited $50;
`Signed, The Bank"
`
`30
`
`FIG.
`
`
`
`
`
`
`
`CUSIOMER
`
`C(f(x2))= "The first presenter of the
`preimage of f(x2) will be credited $50,
`Signed, The Bank"
`
`FIG. 2
`
`
`
`CUSTOMER
`
`GOODS PURCHASED
`
`x1, f(x1), C(f(X1), DEPOSIT REQUEST
`
`WENDOR
`
`DEPOST RECEIVED
`
`PayPal Ex.1010, p.2
`
`

`
`U.S. Patent
`
`Jun. 16, 1998
`
`Sheet 2 of 2
`
`5,768,385
`
`
`
`
`
`
`
`
`
`20
`
`VENDOR
`
`x1,f(x1), C(f(x1)),
`Vendor's SPK,
`Other Information
`
`10
`
`CUSTO MER
`
`GOODS PURCHASED
`
`FIG. 6
`
`
`
`
`
`(E, f(x2)) signed with
`Vendor's SPK
`
`
`
`C(f(x2))
`
`E={[x1, f(x1), C(f(x1),..., Vendor's SPK,
`Other Info) •ºns Bank's
`-—
`GOODS PURCHASED
`FIG. 7
`
`10
`
`CUST ONMER
`
`PayPal Ex.1010, p.3
`
`

`
`1
`UNTRACEABLE ELECTRONIC CASH
`
`5,768.385
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`BACKGROUND OF THE INVENTION
`The invention generally relates to electronic cash systems.
`The ultimate intuitive goal of an electronic cash system is
`to combine the best features of physical cash (privacy,
`anonymity, unforgeability) with the best features of elec
`tronic commerce (speed, ease and potential security of
`transport and storage). The fundamental difficulty with
`attempting to implement anonymous electronic cash,
`however, is simple to state: if the possessor of an electronic
`“coin” is not identified in two successive transactions, then
`how is he or she to be prevented from acting as if the first
`transaction never occurred, and spending the same coin
`again. The first proposed solution to this problem was
`presented by Chaum, Fiat and Naor (see D. Chaum. A Fiat
`and M. Naor, Untraceable Electronic Cash, Proc. CRYPTO
`'88, Springer-Verlag (1990), pp. 319–327.), and was based
`on the premise that it would be sufficient for such “double
`spending” to be detected, and the spender identified, upon
`presentation of the same “electronic coin” twice to the
`central bank. This premise has also been used in a number
`of other proposed solution, all with the advantage that the
`bank need not be involved in each transaction. Practically
`speaking, however, this premise has enormous drawbacks.
`Fraudulent transactions are detected only long after they
`have taken place, and if the perpetrator can be confident of
`not being brought to justice (either by being inaccessible or
`by managing to use someone else’s identity and cash), then
`he or she can double-spend at will.
`However, if such fraudulent use of electronic cash is to be
`prevented, then some authority must somehow be involved
`in each transaction as it occurs, so as to be able to recognize
`and alert targets of double-spending. How, then, is anonym
`ity to be preserved. One approach is to rely on tamper
`resistant hardware to force spenders to behave “honestly”
`(ie., not to double-spend) (see, for example, S. Even, O.
`Goldreich and Y. Yacobi. Electronic Wallet, Proc. CRYPTO
`'83, Plenum Press (1984), pp. 383–386.). Schemes based on
`this premise are, however, extremely “brittle”. If anyone
`ever succeeds in tampering with the hardware, then not only
`is that person capable of double-spending, but anyone,
`anywhere who obtains (e.g. purchases, perhaps) the infor
`mation hidden in the hardware can spend arbitrarily high
`amounts at will. Current tamper resistance technology is far
`from being dependable enough to be trusted to thwart such
`an enormous risk.
`Another approach is cryptographic. For example, under
`certain very strong cryptographic assumptions, it is possible
`50
`to construct protocols that create “blinded” cash—
`information which can be recognized later as valid cash, but
`cannot be connected with any particular run of the protocol.
`(See, for example, D. Chaum, Privacy Protected
`Payments—Unconditional Payer and/or Payee
`Untraceability. SMART CARD 2000: The Future of IC
`Cards—Proc. IFIP WG 11.6 Int’l Conf., North-Holland
`(1989), pp. 69–93; and D. Chaum. Online Cash Checks,
`Proc. EUROCRYPT '89, Springer-Verlag (1989), pp.
`288–293.)
`
`45
`
`55
`
`SUMMARY OF THE INVENTION
`We present a simple, practical online electronic cash
`system based on the assumption of a network in which
`anonymous. untraceable communication is possible. In
`general, the invention uses two simple primitives, namely a
`one-way function and a signature scheme. These are both
`
`65
`
`2
`well known in the art; and descriptions can be found in
`publicly available literature on cryptography, e.g. Applied
`Cryptography, Bruce Schneier, John Wiley & Sons, Inc.
`(1994). The anonymity of spenders as well as guaranteeing
`their electronic coins’validity, but also the coins used are
`unforgeable and cannot be spent more than once.
`In general, in one aspect, the invention is an electronic
`cash protocol including the steps of using a one-way func
`tion f(x) to generate an image fi(x1) from a preimage X1;
`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. The received signed note represents a
`commitment by the second party to credit a predetermined
`amount of money to a first presenter of the preimage x1 to
`the second party.
`Preferred embodiments include the following features.
`The electronic cash protocol also includes sending the
`preimage xi to a third party as payment for purchase of
`goods or services from the third party. Alternatively, it
`further includes selecting a second preimage x2; using a
`second one-way function f2(x) to generate a second image
`fz(x2) from the second preimage x2; sending the first pre
`image xi and the unblinded form of the second image fa?z2)
`to the second party; and receiving from the second party a
`note including a digital signature, the note representing a
`commitment by the second party to credit the predetermined
`amount of money to a first presenter of the second preimage
`x2 to the second party. In both cases. f(x) and f2(x) are the
`same function. In the latter case, the sending of the first
`preimage xi and the unblinded form of the second image
`f2(x2) to the second party is performed anonymously and the
`second party is a bank.
`Also in preferred embodiments, the protocol includes the
`steps of concatenating a signature key of a third party with
`the first preimagex, to form a block of information; encrypt
`ing the block of information by using an encryption key of
`the second party to generate an encrypted block of infor
`mation; and sending the encrypted block of information to
`the third party.
`In general, in another aspect, the invention is an electronic
`cash protocol including the steps of receiving a first preim
`age xi from a first party, wherein the preimage xi produces
`a first image fi(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 xi.; selecting a second
`preimage x2 ; using a second one-way function f2(x) to
`generate a second image f, (x2) from the second preimage
`x2; sending the first preimage xi and an unblinded form of
`the second image f.(x2) to the 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 the predetermined amount of money to a first
`presenter of the second preimage x2 to the second party.
`In general, in yet another aspect, the invention is an
`electronic cash protocol including the steps of receiving
`from a first party an encrypted block of information, wherein
`the block of encrypted information was generated by first
`concatenating a public signature key of a second party with
`a first preimage xi 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 x2; using
`a second one-way function f2(x) to generate an image f(x2)
`from the preimage x2; forming a message including the
`encrypted block of information along with the image f(x2) in
`
`PayPal Ex.1010, p.4
`
`

`
`5,768,385
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`65
`
`3
`an unblinded form; sending the message to the third party;
`and receiving from the third party a signed note including a
`digital signature, wherein the note represents a commitment
`by the third party to credit a predetermined amount of money
`to a first presenter of the preimage x2 to the third party.
`In general, in still another aspect, the invention is an
`electronic cash protocol including the steps of receiving
`from a first entity an unblinded form of an image fi(x1) that
`was generated by applying a one-way function f(x) to a
`preimage xi.; generating a message which contains a com
`10
`mitment to credit a predetermined amount of money to a first
`presenter of the preimage x1; signing the message with a
`digital signature; and sending the message along with the
`digital signature to the first party.
`In preferred embodiments, the electronic cash protocol
`also includes subsequently receiving the preimage xi from a
`third party; checking a database for the preimage xi.; if the
`preimage x1 is not found in the database, crediting the third
`party with the predetermined amount of money; and adding
`the preimage xi to the database. Alternatively, the protocol
`includes subsequently receiving the preimage xi and an
`unblinded image f_{x2) from a third party, wherein the
`unblinded image fa(x2) was generated by applying a one
`way function f2(x) to a preimage x2; checking a database for
`the preimage xi.; if the preimage x1 is not found in the
`database, generating a signed note including a digital
`signature. wherein the note represents a commitment to
`credit the predetermined amount of money to a first pre
`senter of the preimage x2; and adding the preimage xi to the
`database.
`Also in preferred embodiments, the invention features
`receiving a message from a second party, wherein the
`message was generated by concatenating an encryption key
`of a third party with a first preimage xi 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_{x2) to the
`encrypted first block of information, wherein the unblinded
`image fa(x2) was generated by using a one-way function
`fz(x) to generate an image fa(x2) from a preimage x2. It
`further features decrypting the encrypted first block of
`information; generating a note including a digital signature,
`wherein the note represents a commitment to credit a
`predetermined amount of money to a first presenter of the
`preimage x2; and sending the note to the second party.
`In general. in yet another aspect, the invention is an
`electronic cash protocol including the steps of sending an
`unblinded image f,(x2) to a second party, wherein the
`unblinded image fa (x2 ) was generated by applying a
`one-way function f2(x) to a preimage x2; receiving a signed
`note from the second party, wherein the unblinded note
`includes a digital signature and represents a commitment to
`credit the predetermined amount of money to a first pre
`senter of the preimage x2; and in response to receiving the
`unblinded note from the second party, authorizing the deliv
`ery of goods and/or services to a third party.
`The invention offers a simple, inexpensive way of doing
`cash-like transactions where the item of exchange (i.e., the
`withdrawn coin) has the properties of actual cash. For
`example, it is: (1) more or less anonymous; (2) secure; (3)
`inexpensive to use; and (4) easy to carry around and
`exchange.
`Parties are protected against a dishonest bank’s reneging
`on withdrawn coins by the fact that they keep secret the
`value x1 for a particular coin until it is spent. As long as a
`particular coin f(x1) is deposited publicly and non
`
`4
`anonymously, the bank can be required to honor it unless it
`can supply the associated x1. Of course, the bank can renege
`on an anonymously exchanged coin f(x1) during the actual
`exchange. by claiming upon receiving xi that the coin has
`already been spent. However, the bank cannot possibly
`know who is being cheated by such a “dine and dash” ploy,
`and is therefore vulnerable to monitoring and public expo
`Surº.
`Finally, banks themselves are protected against counter
`feiting by the security of the digital signature scheme used
`to sign electronic coins. Moreover, they are protected against
`“double-spending” (or “double deposit”) by their ability to
`store x1 values for coins in perpetuity.
`Other advantages and features will become apparent from
`the following description of the preferred embodiment and
`from the claims.
`
`BRIEF DESCRIPTION OF THE DRAWING
`FIG. 1 is a diagram of a non-anonymous withdrawal
`protocol;
`FIG. 2 is a diagram of an anonymous exchange protocol;
`FIG. 3 is a diagram of an anonymous purchase protocol;
`FIG. 4 is a diagram of a non-anonymous deposit protocol;
`FIG. 5 is a diagram of an anonymous alternate payment
`protocol;
`FIG. 6 is a diagram of an anonymous or non-anonymous
`“drop” payment or money order protocol; and
`FIG. 7 is a diagram of an encrypted money order protocol.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`The ability to communicate anonymously is in some sense
`necessary a priori if anonymous cash transactions are to
`occur, since information about a party's communications
`will obviously reveal information about the party's business
`dealings. In practice, the anonymity of communication may
`be based on nothing more than confidence that the telephone
`company safeguards the confidentiality of its system.
`Alternatively, parties may place trust in one or more “anony
`mous remailers” to obscure identities of the parties, or rely
`on an implementation of one of the other techniques from
`the publicly available literature.
`Suppose, not only that communications between parties
`are anonymous with respect to third parties. but also that the
`communicating parties are anonymous to each other. (In
`typical implementations, the latter condition is a natural
`consequence of the former, barring self-identification.) A
`simple, somewhat anonymous electronic cash protocol in
`such a setting is shown in FIG. 1.
`In the following descriptions of various protocols (see
`FIGS. 1–7), we generally refer to three parties, namely, a
`Customer 10, a Vendor 20, and a Bank 30. Customer 10 is
`of course generally representative of the payor and Vendor
`20 is generally representative of the payee. It should be
`understood, however, that these designations are chosen for
`purposes of clarity and that they are not meant to limit the
`scope of the invention. It would be just as valid to have
`referred to them as Party A. Party B and Party C.
`In the figures, the different entities are represented by
`blocks and the transfers of information from one entity to
`another are indicated by lines interconnecting the appropri
`ate blocks. Each line represents a transfer of certain infor
`mation from one entity to another in the direction indicated
`by an arrow at the end of the line. The information that is
`transferred is summarized symbolically below the lines.
`
`PayPal Ex.1010, p.5
`
`

`
`5,768,385
`
`5
`
`10
`
`15
`
`25
`
`5
`Though each block is labeled and will be described below
`as representing a particular entity, it can be implemented by
`a computing device which performs the computations and
`the communications that are carried out by that entity. The
`computing devices might be any of a large variety of
`electronic devices including, for example, a personal
`computer, a PCMCIA card, a PDI, a smart-card, a palm-top
`computer, or a more powerful workstation, just to name a
`few. The barkside of the protocols that are described below
`can be implemented by a server programmed to handle
`electronic transactions, similar to those which currently
`handle ATM transactions. The server would have multiple
`telephone lines coming into it and include data storage
`capability for storing the relevant data.
`It should of course also be understood that the computing
`devices include, either internally or externally, all of the
`memory that is required for the data and programs that are
`involved in implementing the protocols. Further more, they
`include devices (e.g. a modem) which enable them to
`communicate with other computing devices. In addition, the
`communications media over which the transfers of informa
`tion take place can also be any of a large number of
`possibilities, including telephone lines, cable, the Internet,
`satellite transmissions, or radio transmissions, for example.
`In other words, it is not intended that the invention be limited
`with regard to either the types of devices that are used or the
`methods of communication that are employed. The possi
`bilities and combinations are limited only by one’s imagi
`nation.
`For the following protocols, it is assumed that Bank 30
`chooses and makes publicly available a one-way function
`f(x). Alternatively, such a function could be made publicly
`available by any party so long as all parties to the transac
`tions can access and use it. In general, by a one-way
`function, we mean a function f(x) such that using xi pro
`duces f(x1) and given f(x1) you cannot determine x1. In the
`following description, xiwill also be referred to as a preim
`age of f(x1) and f(x,) will be referred to as an image of x1.
`In practice, perfect one-way functions may not actually
`exist. That is, for all functions now believed to be one way
`functions, there may eventually be sufficient computing
`power or techniques for determining x, given f(x1). Thus, by
`the phrase one-way function. we mean to also include those
`functions for which it is very difficult, but not necessarily
`impossible, to compute x1 by knowing f(x1).
`The one-way function can be any one of a number of
`standard hash functions (e.g. MD5, SHA, etc.). In addition,
`one could use several one-way functions and concatenate
`them. There are a wide variety of one-way functions known
`in the art. Typically, many of them are easy to compute, and
`thus they can be implemented on a smart card.
`With that background, the various protocols which
`embody the invention will now be described, starting with a
`withdrawal protocol during which a customer obtains “cash”
`from the bank.
`
`6
`monetary value with f(x1). Bank 30 complies by digitally
`signing a statement to that effect, thus “certifying” f(x1) as
`a valid coin and debits an account which Customer 10
`maintains at Bank 30 by the amount of the value of the coin.
`In other words, Bank 30 issues a statement or representation
`which indicates in effect that “The first presenter of the
`preimage of f(x1) will be credited an amount Z” and then
`Bank 30 signs or certifies that representation.
`Techniques for signing or certifying information (e.g. by
`using a private key-public key pair) and the use of digital
`signatures are well known in the art. For further details, refer
`to any of the widely recognized references in the field, e.g.
`Applied Cryptography by Bruce Schneier, John Wiley &
`Sons, Inc.. (1994).
`In general, a signature scheme is a way of tagging a script.
`It typically uses a public key-private key pair. Public-private
`keys can be implemented using one-way functions, although
`a somewhat more practical approach is to use a trap door
`function, which tends to be more efficient (e.g. see RSA,
`DSS, ElGamal algorithms described by Schneier). The pri
`vate key is used to encrypt either the script or a hash of the
`script to produce a digital signature that is then appended to
`the script. The digital signature represents a signature of the
`entity which owns the private key since no other entity can
`generate such a signature from that script. If a second entity
`can decrypt the tag using the public key, it knows that the
`signature was generated by the entity which owns the private
`key.
`Obviously, for certification to work, it is assumed that
`everyone has and trusts the signing authority’s public key
`and has confidence that the private key has not been com
`promised.
`By publicizing its public key and appending digital sig
`natures to a representation that Bank 30 will pay a specified
`sum to the entity that first presents a preimage of f(x1), Bank
`30 links itself unambiguously to its commitment, and pro
`tects itself against would-be forgers.
`The certified representation that is generated by the bank
`is designated herein as C(f(x,)), also referred to herein as a
`note. This note is returned to Customer 10. In addition, the
`note can be made publicly available since it is of no value
`to anybody who does not know xi.
`EXCHANGE PROTOCOL
`At any time, a party (e.g. Customer 10 or Vendor 20) can
`anonymously “exchange” a coin at Bank 30. Indeed, it is
`particularly important to do this immediately after receiving
`a coin from another party to minimize the risk that some
`body else will supply xi to Bank 30 before the bona fide
`recipient of the coin. A dishonest party could try to send the
`coin multiple times by giving xi to multiple parties. If that
`happens, the first recipient to reach Bank 30 will receive its
`value and all other recipients of the coin will not be able to
`exchange it for another coin. For Vendor 20, the timing of
`the exchange is less crucial because presumably Vendor 20
`will not deliver the goods or services that are being pur
`chased until being assured that the coin that was received is
`still valid.
`Referring to FIG. 2, assuming that Customer 10 wishes to
`anonymously exchange a coin. Customer 10 supplies to
`Bank 30 x1 and another image of the function, f(x2), for
`some randomly chosen x2. In other words. Customer 10
`attempts to make a withdrawal as described earlier but
`simultaneously supplies the amount that is being withdrawn
`as represented by x1. Bank 30 simply certifies f(x2) and
`keeps x1 in a database 40 as proof that f(x1) has already been
`“spent”. It is this exchange that prevents double spending of
`X1.
`
`30
`
`35
`
`45
`
`50
`
`55
`
`WITHDRAWAL PROTOCOL
`A withdrawal is performed in the manner shown in FIG.
`1 Customer 10 chooses a random number x1 and uses f(x) to
`generate an image of x1. The value x1 is a random string
`obtained from a random number generator to which some
`post processing may optionally be applied. It may be, for
`example, 128 bits long. Customer 10 keeps xi secret until a
`payment takes place and then it is sent as the payment.
`Customer 10 then withdraws a coin (non-anonymously)
`from Bank 30 by requesting that Bank 30 associate a
`
`65
`
`PayPal Ex.1010, p.6
`
`

`
`7
`Since f(x1) and C(f(x1)) are already in the possession of
`Bank 30, the sending of that information to Bank 30 along
`with x1 and f(x2) is optional.
`If the Bank’s side of the protocol is implemented on a
`server, it automatically stores the x,’s that are received. And
`each time Bank 30 receives another x, the bank first checks
`it against the x,’s that have already been cashed in (i.e.,
`received).
`One can use a series of exchange transactions to obscure
`who actually is spending the coin. Note that during an
`exchange transaction, only f(x2) need be disclosed but not
`the owner of x2. Unlike alternative approaches to achieving
`anonymity, blinding of the coin or other aspects of the
`transaction is not necessary. Indeed, it is desirable that f(x)
`not be blinded but be made publicly known.
`Whatever steps one wishes to take to secure anonymity of
`communication is sufficient to secure anonymity of the
`transaction (i.e., achieving anonymity is possible but it is
`also optional).
`This procedure can also be used to make change for a coin
`of a given value. Instead of sending f(x2), the party seeking
`the change can send multiple f(x)'s, e.g. f(x2), (x)'s f(x3), f
`(x,a), each for a particular value and the total of which equals
`the value associated with f(x1). The bank returns multiple
`signed notes, C(f(x)).
`Purchase Protocol
`Referring to FIG. 3, the actual spending of coins uses a
`protocol that is similar to the exchange protocol. The spend
`ing party (e.g. Customer 10) passes x1 to the receiving party
`(e.g. Vendor 20). Since it is likely that Vendor 20 does not
`have direct and immediate access to f(x1) and C(f(x1)),
`Customer 10 also includes this information as part of the
`transaction. Vendor 20 then immediately calls Bank 30 and
`exchanges x1 for a “fresh” coin, assuming that Bank 30 first
`verifies that it has not previously been spent. Vendor 20 uses
`the exchange protocol illustrated in FIG. 2 to perform this
`exchange. Assuming that the exchange was successful.
`Vendor 20 then delivers to Customer 10 the goods and/or
`services that were purchased.
`DEPOSIT PROTOCOL
`Referring to FIG.4, unspent coins can also be deposited
`non-anonymously with Bank 30 at any time. For example,
`when Vendor 20 wishes to deposit a coin f(x1) that it has not
`spent, it sends xi to Bank along with a deposit request.
`Vendor 20 may also optionally send f(x1) as well as the note
`C(f(x)).
`Upon receiving xi and the deposit request, Bank 30
`checks its database to determine whether xi has been
`previously presented to the Bank. Of course, if it had been
`previously presented, Bank 30 will not credit the Vendor's
`account and will report to Vendor 20 that it is not a valid
`coin. If Bank 30 has not previously received x1, it credits the
`Vendor's account with the appropriate amount and sends a
`deposit receipt to Vendor 20 confirming that a credit has
`been entered.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`EXTENSIONS TO THE PROTOCOLS
`The exchange payment protocols in the above-described
`electronic cash scheme permit a number of variations, which
`can be tailored to the available means of communication and
`the desired levels of anonymity. For example, referring to
`FIG. 5, if Customer 10 has easier access to Bank 30 than
`Vendor 20, then Vendor 20 can first supply an f(x2) to
`
`65
`
`5,768,385
`
`8
`Customer 10, who then performs the exchange protocol for
`Vendor 20 and returns the signed coin, i.e., C(f(x2)), as proof
`of payment. As mentioned previously, the exchange protocol
`may be performed anonymously.
`Alternatively, if both Customer 10 and Vendor 20 have
`better communications access to Bank 30 than to each other,
`then the parties may use a “drop” payment protocol, such as
`is illustrated in FIG. 6. In accordance with this protocol,
`Customer 10 drops off the payment at Bank 30 for Vendor
`20 and Vendor 20 subsequently picks up the payment from
`Bank 30.
`The steps of the “drop” payment protocol are as follows.
`First, Customer 10 supplies an x2 for a valid coin of a
`specific amount to Bank 30, along with a public signature
`key p of Vendor 20, and other information relating to the
`transaction. For example, among the other information Cus
`tomer 10 might wish to identify the goods being purchased,
`to identify the transaction and/or the vendor, and to indicate
`the declared of the customer intentions regarding payment,
`thereby essentially turning the cash into a kind of “electronic
`money order”. Optionally, Customer 10 can also send f(x1)
`and the note C(f(x)), but as pointed out earlier, since this
`information is already available to Bank 30, sending it may
`not be necessary.
`Note that the a record that may be assembled from the
`other information supplied by Customer 10 may be of
`particular use in remote payment settings, where the nature
`of the transaction is not otherwise implicit in the action of
`payment itself, as is typically the case for in-person pay
`ments.
`If Vendor 20 does not wish to remain anonymous, the
`public signature key may be publicly associated with the
`identity of Vendor 20; or if anonymity is desired, the public
`signature key can be a special-purpose public signature key
`with no associated identity. In the latter case, the public key
`is passed confidentially to trusted acquaintances or simply
`publicized under a pseudonym.
`Bank 30 agrees to assign the amount associated with x1 to
`the first coin f(x) presented to it that it is also signed using
`the private signature key that corresponds with the
`previously-delivered public signature key p. Thus to obtain
`the payment for the goods that Customer 10 wishes to
`purchase, Vendor 20 simply makes a withdrawal from Bank
`30 using the protocol previously described in connection
`with FIG. 1. That is, Vendor 20 randomly selects an x2, and
`uses f(x) to generate its image f(x2). In this instance,
`however, Vendor 20 signs f(x2) with its private signature key
`before sending f(x2) to Bank 30. In addition. in this case the
`withdrawal is not from the account of the vendor but is
`simply a transfer of the amount previously supplied by
`Customer 10.
`Bank 30 uses the Vendor's public signature key of the
`vendor to verify that f(x2) is signed by Vendor 20 (i.e., by the
`party to whom the money transfer is to be made). Upon
`confirming the signature on f(x2), Bank 30 issues a note
`C(f(x2)) which it