Efficient electronic money

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.

FIELD OF THE INVENTION 
The present invention relates to electronic money, specifically, to a form 
of electronic money which is the electronic equivalent of cash or other 
currency. The invention provides a form of electronic money which deters 
double spending of a specific electronic coin, while at the same time 
protecting the privacy of payers (spenders) and payees (recipients) in 
cash transactions. 
BACKGROUND OF THE INVENTION 
Electronic money (e-money) comes in the same forms as ordinary money. For 
example, there are electronic equivalents of checks (e-checks) and 
electronic equivalents of cash (e-cash). 
Electronic checks are easier to implement than electronic cash. In a paper 
check, the most important component is the user's signature. This 
signature is supposed to insure the correctness of an obligation to 
transfer a certain amount of money from the signer ("payer") to a 
specified payee. In addition, certain properties of the paper of which the 
check is made are designed so that changes to the content of the paper 
check will be noticeable. All of these properties are inherent to digital 
signatures (see e.g., W. Diffie, M. Hellman, "New Directions in 
Cryptography" IEEE Trans. IT. 1976 and R. Rivest, A. Shamir, and L. 
Adelman, "A Method for Obtaining Digital Signatures and Public Key 
Cryptosystems", CACM, vol. 21, 1978, pp. 120-126). Thus, it is 
straightforward to implement digital checks. Similarly, it is easy to 
implement digital credit cards. A digital signature in this case indicates 
the authenticity of the user and the user's consent to a particular 
transaction. 
It is harder to create the digital equivalent of cash. (For a discussion of 
e-cash, see e.g., D. Chaum, et al. "Untraceable Electronic Cash", Proc. 
Crypto 1988, D. Chaum "Achieving Electronic Privacy" Scientific American, 
August 1992, pp 96-101, S. Brand "Electronic Cash Systems Based on the 
Representation Problem in Groups of Prime Order" Proceedings of Crypto '93 
Santa Barbara 1993 pp 26-26.15; S. Even et al. "Electronic Wallet" Proc. 
Crypto '83). The main problem is this. Suppose that a bunch of digital 
bits represents a coin. What can prevent the payer from double spending 
the digital coin? 
Two approaches have been used in the prior art to resolve this problem. 
Prevention and after the fact detection. For example, to prevent double 
spending, tamper resistant devices may be used. Such devices, called 
electronic wallets (e-wallets) or money modules, store a user's balance in 
a manner so that even the owner of the device cannot illegally modify the 
balance. A balance on one of these money modules can change if two such 
devices "agree" to a specified transaction, whereby one money module (the 
payer) agrees to pay X dollars to another money module (the payee). In 
this case, the balance in each money module is changed so that the sum of 
the two balances remains unchanged. A transaction between a bank and a 
user is similar except that it involves additional steps such as moving 
money from the user's checking account into the user's money module where 
the money now becomes e-cash. The use of tamper-resistant devices, i.e. 
money modules, to prevent the double spending of e-cash is preferred by 
banks because banks want to prevent double spending, not detect double 
spending after such double spending occurs. 
However, it is impossible to create a 100% tamper proof money module type 
device. It is only a question of resources devoted to reverse engineering 
and decription, etc. If by gaining unauthorized access or "unwrapping" one 
money module one could forge ten million dollars, then it makes economic 
sense (but not moral sense) to invest one million dollars to penetrate the 
money module. There is a spectrum of tamper-resistant technologies that 
range in price and quality and some economic optimum must be reached. 
This optimum is less expensive if a second line of defense can be added. 
Such a second line of defense might be the use of a process which provides 
for after the fact exposure of the double spender. 
Another issue that arises in connection with the use of e-cash is privacy. 
For large transactions (e.g. buying a house), traceable forms of e-money 
such as e-checks can be used. Usually these kinds of transactions are not 
viewed as secret transactions and usually the parties want evidence as to 
these transactions. Electronic cash (e-cash) is generally used for smaller 
daily transactions (e.g. buying groceries and buying newspapers, etc.). A 
user would not want a government or large private agency a bank) to be 
able to constantly know his/her whereabouts and the details of daily 
purchases based on the payment of e-cash to various payees. Thus, after 
ordinary legitimate uses, the identity of an e-cash spender should not be 
traceable. On the other hand, the e-cash system should enable detection of 
the identity of a double spender of the same e-coin. 
It is an object of the present invention to provide e-cash or e-coins with 
certain highly desirable characteristics. The characteristics include the 
following: 
1. Once a bank detects double spending (i.e. the same e-coin is deposited 
twice), the bank should have enough information to efficiently expose the 
identity of the double spender. However, one legitimate deposit of a 
particular e-coin should not provide the bank with enough information to 
compute the identity of the person who paid the particular e-coin to the 
depositor. 
2. The e-cash should be useable in the following transactions; (a) payment 
from payer to payee without revealing identity of payer, (b) deposit of 
money into the bank by the payee without revealing the identity of the 
payer, (c) an exchange transaction wherein a depositor gets a certain 
amount of fresh money from the bank in exchange for depositing the same 
amount of old money into the bank without revealing his/her identity, and 
(d) withdrawal from the bank. 
3. The system should be efficient. Specifically, the system should require 
as few real time operations as possible during transactions, especially at 
the money modules used by individual users as the money modules have 
limited processing power. As many operations as possible should be done in 
advance of and apart from the transactions which take place in real time. 
The present invention provides an e-cash system which has these advantages. 
The e-cash system of the present invention relies on certain prior art 
techniques. These prior art techniques are described below: 
A. Public Key Cryptography 
In a typical public key cryptographic system, each party i has a public key 
P.sub.i and a secret key S.sub.i. The public key P.sub.i is known to 
everyone, but the secret key S.sub.i is known only to party i. A clear 
text message m to user i is encrypted to form the cipher text message c 
using a public operation P which makes use of the public key P.sub.i known 
to everyone, i.e., c=P(m,P.sub.i). The cipher text message c is decrypted 
using a secret operation S which makes use of the secret key S.sub.i, 
i.e., m=S(c,S.sub.i). Only the party i which has the secret key S.sub.i 
can perform the secret operation to decrypt the encrypted message. 
Public key cryptographic techniques may also be used for authentication. If 
it is true that P(S(m, S.sub.i),P.sub.i)=m, then the owner of the 
corresponding keys P.sub.i, S.sub.i could sign message m by producing 
s=S(m,S.sub.i), where s indicates the signature. The verifier, given m and 
s will verify m=P(s,P.sub.i). A signature system could be used for 
verification as follows: Challenge the party claiming to be i with message 
m and ask the party to sign the message m using his secret key S.sub.i, 
then verify the signature using P.sub.i. 
An example of a public key cryptographic technique is the well known RSA 
technique. In accordance with this technique, a party i has a public key 
in the form of an exponent e and modulus N and a secret key in the form of 
an exponent d. Thus,a party with a message to send to party i encrypts the 
message m to form c.tbd.m.sup.e mod N. The party i can then decrypt c to 
obtain m by performing the operation m=c.sup.d mod N. 
Another public key crytographic technique is the Rabin modular square root. 
In this technique, the secret operation involves obtaining a modular 
square root and the public operation involves a modular squaring 
operation. 
B. EL Gamal Signature Scheme 
Let P.sub.i and S.sub.i be the public and secret keys of user i, where 
P.sub.i =.alpha..sup.Si mod p, where p is a large prime or a product of 
large primes, and .alpha. is a generator in Z.sub.p.sup.*. An El-Gamal 
signature by user i, on message m is an ordered pair s=(u,v), for which 
EQU P.sub.i.sup.u .multidot.u.sup.v .tbd..alpha..sup.m mod p (1) 
Thus a recipient of a signature can easily verify it. To create a 
signature, user i chooses a random number r, and computes u=.alpha..sup.r 
mod p. From eq (1) it follows that: 
EQU S.sub.i .multidot.u+r.multidot.v.tbd.m mod p-1 (2) 
Hence i, who is the only one who knows S.sub.i, can compute v, provided 
gcd(r,p-1)=1. The El Gamal signature scheme is disclosed in T. El Gamal "A 
Public Key Cryptosystem and a Signature Scheme Based on Discrete 
Logarithms", IEEE Trans IT, Vol. IT-31, No. 4, July, 1985, pp. 469-472. 
The El-Gamal signature system has the curious property that if the signer i 
tries to use the same r twice to sign two different messages, then these 
two signatures expose his secret key S.sub.i. To see how double use of r 
exposes S.sub.i, note that from eq (2) that 
EQU S.sub.i .multidot.u+r.multidot.v.sub.1 .tbd.m.sub.1 mod p-1; S.sub.i 
.multidot.u+r.multidot.v.sub.2 .tbd.m.sub.2 mod p-1 (3) 
Hence, 
EQU r(v.sub.1 -v.sub.2).tbd.(m.sub.1 -m.sub.2) mod p-1 (4) 
If gcd (v.sub.1 -v.sub.2, p-1)=1, anybody knowing the messages m.sub.1, 
m.sub.2 and their signatures (u,v.sub.1), (u,v.sub.2) can find r, and if 
gcd(v,p-1)=1, then S.sub.i can be computed. This unique property of the El 
Gamal signature scheme is used as the basis for an e-cash system according 
to the invention in which the identity of a double spender of a particular 
e-coin is exposed. 
Other signature schemes such as NIST-DSS and Schnorr also have the property 
that if two distinct messages are signed using the same random element 
(e.g. r), then the secret key of the signer can be computed by anyone 
having the messages, the signatures and public information such as the 
public key of the signer. As used herein, the term El Gamal family of 
signatures refers to signature schemes with this property. 
C. Blind Signature 
The idea of a blind signature is to mimic a situation in which a person 
signs a closed envelope. The envelope includes some document and a carbon 
paper, so that the signature appears (via the carbon paper) on the 
document, without the signer knowing the contents of the document. The 
recipient can later fetch the signed document from the envelope. This 
seemingly bizarre idea proves very helpful in establishing 
nontraceability. A blind signature may be implemented using RSA as 
follows. The signer is associated with N,e,d (public modulus, public 
exponent, and secret exponent, respectively). The secret message to be 
signed is m. The recipient picks a random x.epsilon.Z.sub.N.sup.*, and 
presents a "message-in-envelope" c.tbd.x.sup.e .multidot.m mod N to the 
signer, who signs it, i.e. computes c.sup.d .tbd.x.multidot.m.sup.d mod N, 
from which the recipient, and only the recipient (who knows x), can 
compute the signed message m.sup.d .tbd.c.sup.d x.sup.-1 mod N. 
The public key cryptography techniques described above are used to provide 
a unique e-cash system according to the invention. 
SUMMARY OF THE INVENTION 
In accordance with an illustrative embodiment of the present invention, an 
e-cash system has four players. These are a certification authority, a 
bank, a payer also known as user i, and a payee also known as user j. 
There are six basic operations which may be carried out in the e-money 
system. These are: Initial certificate, refresh certificate, withdrawal, 
payment, deposit and exchange. The elements of the e-money system of the 
present invention and the operations are described below. 
A. Public Key and Secret Key 
A user i has a public key P.sub.i, where for example, P.sub.i 
=.alpha..sup.Si mod p, where .alpha. and p are universally known. S.sub.i 
is a secret key of the user i. The secret key S.sub.i includes the 
identity I.sub.i of the user i. Illustratively, S.sub.i is a concatenation 
of the user's name I.sub.i and a string of random bits R.sub.i known only 
to the user i, i.e., S.sub.i =(I.sub.i, R.sub.i). Alternatively, the 
secret exponent key S.sub.i may include multiple copies of I.sub.i. It 
should be noted that P.sub.i and S.sub.i are, for example, El Gamal public 
and secret keys, respectively. As is shown below, this feature is 
important for detecting the identity of a double spender of a particular 
e-coin. Alternatively, P.sub.i and S.sub.i may be keys from a different 
signature scheme in the El Gamal family of signature schemes. NIST DSS and 
Schnorr are included in the El Gamal family. However, it is desirable for 
S.sub.i to contain the user's identity I.sub.i. 
B. Certification of the Public Key 
The user may also have a certificate of the public key P.sub.i. A 
certificate of a public key is a linkage between a user's identity I.sub.i 
and the user's claimed public key P.sub.i. In the present invention, this 
certificate is a proof that the public key P.sub.i is legitimate and that 
the user's identity is embedded in the exponent or otherwise embedded in 
the public key. The certificate proves an implicit linkage between the 
user's name and certificate. The certificate is, for example, a signature 
(e.g. an RSA signature) of a trusted authority on f(P.sub.i, 
.gamma..sup.2), where 0.sup..gamma. denotes a run of .gamma. zeros. The 
use of the function f is entirely optional. Thus, in some embodiments of 
the invention f(P.sub.i,0.sup..gamma.)=(P.sub.i,0.sup..gamma.). In other 
embodiments of the invention, f is a publicly known collision free hash 
function. Specifically, let 1(p)=log.sub.2 (p).sub.+.gamma.. 
Let .SIGMA.={0,1}.sup.1(p) and f: .SIGMA..fwdarw..SIGMA. be a publicly 
known collision free one way hash function. (Sometimes f is used for 
.SIGMA.={0,1}.sup.1(p.spsp.2.sup.) and this is clear from the context.) 
The certificate of P.sub.i is illustratively computed "off--off line". 
As used herein the term "off--off line" designates operations which are 
performed rarely. Specifically, the term "off--off line" designates 
operations which may be performed once and whose results are used in many 
real time operations. The "off--off line" operations are to be contrasted 
with "off-line" operations which are used in on/off line digital signature 
schemes. In an on/off line digital signature scheme, for each real time 
digital signature to be performed, as much of the computation as possible 
performed ahead of time to reduce real time computation. The computations 
performed ahead of time for each real time digital signature are referred 
to as "off-line" computations. There is a one-to-one correspondence 
between a set of "off-line" computations and a real time digital 
signature. In contrast, there is no one-to-one correspondence between 
"off--off" line computations and a real time operation. Rather, the 
results of an "off--off line" computation can be used in many subsequent 
real time operations. The use of "off--off line" operations is a unique 
feature of the present invention. It is a significant advantage of the 
invention, that a certificate of a public key P.sub.i can be computed 
"off--off line". 
The certificate is obtained as follows. A candidate certificate 
f(P.sub.i,0.sup..gamma.) is blinded by computing Z.tbd.x.sup.ec f(P.sub.i, 
0.sup..gamma.) mod N.sub.c, where x is a random number, e.sub.c is the 
public RSA exponent key of a trusted certificate authority, and N.sub.c is 
a public modulus of the certificate authority. The quantity Z is then 
transmitted from the user i to the certificate authority. 
The user i then proves to the certificate authority that P.sub.i has been 
properly formatted, i.e., that the secret key S.sub.i in the exponent of 
P.sub.i includes the user identity I.sub.i. This proof can be accomplished 
without revealing P.sub.i to the certificate authority so that the 
certificate authority cannot correlate I.sub.i and P.sub.i for the user i. 
If the certificate authority is able to correlate I.sub.i and P.sub.i, 
then the certificate authority will be able to gain knowledge of all the 
transactions performed by user i using e-cash. In the present invention, 
the identity of the user is exposed only when a coin is double spent. To 
prevent such a correlation, the candidate certificate is blinded before it 
is sent to the certificate authority. One technique which can be used to 
perform the proof is known as a zero-knowledge proof (see Goldreich, 
Micali, and Wigderson Proofs that yield nothing, but their validity, or 
All languages in NP have zero-knowledge proof systems. J. of the ACM, 38: 
691-729, 1991 and Goldwasser, Micali, and Rackoff, The knowledge 
complexity of Interactive proof systems, SIAM J. on Computing, 181, 1989, 
pp. 186-208. A zero knowledge proof can be used here because all of the 
predicates used in the proof are NP (Non-deterministic polynomial time). 
Another proof technique is a "cut-and-choose" technique. The latter 
technique is discussed in detail below. 
Assuming the proof is acceptable to the certificate authority, the 
certificate authority computes Z.sup.dc, where d.sub.c is the secret RSA 
exponent key of the certificate authority. Z.sup.dc is then transmitted 
from the certificate authority to the user i, who then computes the 
certificate cert(i)=Z.sup.dc /x.tbd.(f(P.sub.i, 0.sup..gamma.)).sup.dc mod 
N.sub.c. 
In short, the user i gets a certificate from the certificate authority that 
establishes a linkage between I.sub.i and P.sub.i. However, in contrast to 
ordinary certificates, this linkage is hidden. The user identity I.sub.i 
is embedded in the discrete log of the public key P.sub.i and is only 
exposed when there is double spending of a coin. Note that the certificate 
cert(i) may be periodically refreshed using off--off line computations. 
C. Format of e-coin 
In general, a coin includes a certified linkage between a public key of a 
user and a random element. In accordance with an illustrative embodiment 
of the present invention, a coin of user i is represented by (P.sub.i, u, 
C), and the certified linkage C.tbd.(f(P.sub.i, u, 0.sup..gamma.)).sup.d$ 
mod N.sub.S, where u.tbd..alpha..sup.r mod p, where r is a random element 
and is chosen by i and known only to i, where 30&lt;.gamma.&lt;50, where d.sub.$ 
is a bank's RSA secret exponent for coins of a particular denomination, 
and where N.sub.$ is the RSA modulus of the bank. The key P.sub.i, the 
value u, the modulus N.sub.$, and the public RSA exponent e.sub.$ 
(corresponding to the secret RSA exponent d.sub.$) are known publicly. 
Each coin of user i has a different value of the random element r and a 
corresponding different value of u, but the same P.sub.i is used in many 
coins. 
The following on-line (i.e. real time transactions) can be performed using 
the e-cash of the present invention. 
1. Payment 
The payer i transmits a coin (P.sub.i,u,C), and the certified linkage 
C.tbd.(f(P.sub.i, u, 0.sup..gamma.)).sup.d$ mod N.sub.$ to the payee j. 
The payee j verifies the bank's signature by verifying C.sup.e$ mod 
N.sub.$ .tbd.f(P.sub.i u, 0.sup..gamma.). If the banks' signature is 
correct, the payee j challenges the payer i to sign a random message m. 
The payer i signs m using (P.sub.i, u) embedded in the coin using an El 
Gamal signature or some other signature from the El Gamal family. The 
payer i computes the El Gamal signature s=(u,v) and transmits the 
signature to the payee j. The payee j then verifies the El Gamal 
signature. The payee j now stores the coin. 
In short, in the payment operation the payer sends a coin (certified 
linkage between a public key and a random element) to a payee. The payee 
verifies the certificate which illustratively is a bank's signature. The 
payee then challenges the payer to sign a message m using a signature 
scheme from the El Gamal family and using the public key and random 
element embedded in the coin. The payee then verifies the signature. 
2. Deposit 
Suppose the payee j wants to deposit the coin (P.sub.i,u,C) in the bank. 
The payee j transmits the coin (P.sub.i,u,C) and the El Gamal signature 
s=(u,v) of the payer i to the bank. The message m that was signed by payer 
i is also transmitted to the bank. The bank verifies the coin by verifying 
that 
EQU C.sup.e$ mod N.sub.$ .tbd.f(P.sub.i, u, 0.sup..gamma.). 
The bank maintains a list of deposited coins (p.sup.i, u, C) and 
corresponding El Gamal signatures (u,v) and messages m. 
The bank then compares the coin currently being deposited with the coins in 
the list. If there is a duplicate,using equations (2) and (3) above, r and 
S.sub.i can be determined. From S.sub.i, the identity I.sub.i of the 
double spender is exposed. If there is no duplicate, the coin is added to 
the list and the balance of the payee j is updated. The list of coins will 
not grow endlessly if an expiration date is embedded in the coins. 
In short, in the deposit operation, the payee transmits the received coin 
and the payer's El Gamal family signature to the bank. The bank verifies 
the coin and then compares the coin to a list of previously deposited 
coins to see if the coin was deposited in the past. If the coin was 
deposited in the past, the bank is able to determine the identity of the 
double spender. Specifically, the bank would have received two El Gamal 
family signatures on two different messages but using the same random 
element. 
D. Exchange of Old Money for New 
Instead of the payee j simply depositing the coin received from the payer 
i, the payee j can deposit the coin at the bank and ask for new coins of 
the same total value in return. The deposit routine as described above is 
performed and a verification is made for double spending but no change is 
made to j's balance. The payee j transmits to the bank a non-blinded 
certificate (P.sub.j,0.sup..gamma.).sup.dc mod N.sub.c. The bank then 
verifies the certificate. For each requested coin, the payee also sends to 
the bank u'=.alpha..sup.r' mod p of his choice. The user j gets back from 
the bank the certified linkage C'.tbd.(f(P.sub.j, u, 
0.sup..gamma.)).sup.d$ mod N.sub.$. This is done by an anonymous call by 
the user who does not identify himself to the bank. The exchange 
transaction is a feature of the present invention which is not found in 
prior art e-money systems. 
In short, in the exchange operation, a payee deposits old coins in the bank 
and gets fresh coins in the same total value from the bank. The payee does 
not reveal his/her identity to the bank and hence the linkage (user, coin) 
is not known to the bank. 
Withdrawal 
Another operation which can be performed is a withdrawal operation in which 
the user withdraws a coin of a particular value from the bank. According 
to this operation, the user i establishes communication with the bank and 
authenticates himself/herself with the bank. The user i transmits to the 
bank a candidate blinded linkage w.tbd.x.sup.e$ f(P.sub.i, u, 
0.sup..gamma.)mod N.sub.$ on which it is desired to obtain the banks RSA 
signature. The user also proves to the bank (using a zero knowledge proof, 
or cut-and-choose proof, for example) that P.sub.i is properly structured 
without revealing the key P.sub.i to the bank so that the bank cannot 
correlate the user i with P.sub.i. The bank deducts the value of the coin 
from the user's balance. The bank then returns w.sup.d$ mod N.sub.$, from 
which the user can formulate the desired coin (P.sub.i,u,C), where the 
certified linkage C=f((P.sub.i, u, 0.sup..gamma.)).sup.d$ mod N.sub.$. It 
is expected that the exchange operation will be used more frequently than 
the more complex withdrawal operation. 
In short, in the withdrawal operation, a blinded linkage between a public 
key (e.g. Pi) and a random element (e.g. u) is transmitted to the bank. 
Blinding is used so that the bank does not correlate P.sub.i and I.sub.i. 
The bank verifies that P.sub.i is properly structured (i.e. the user's 
identity I.sub.i is embedded therein). The bank then signs the blinded 
linkage and returns the signed blinded linkage to the user who then 
formulates a coin. 
The inventive e-cash system disclosed above has a number of significant 
advantages. The system is simple from the computation and communication 
point of view. The number of real time operations is limited and the most 
complex operations are performed off--off line. The inventive e-cash 
scheme protects the privacy of the user while permitting exposure of the 
identity of a double spender.

DETAILED DESCRIPTION OF THE INVENTION 
A. The Network Environment 
FIG. 1 schematically illustrates a network 10 in which the e-cash of the 
present invention may be utilized to perform a variety of transactions. 
The network 10 includes a plurality electronic e-coin processing units 
such as money modules belonging to users, one or more banks, and a 
certificate authority. 
Illustratively, the network 10 of FIG. 1 includes a first portable money 
module 12 belonging to the user i and a second portable money module 14 
belonging to the user j. The money module 12 includes a CPU (e.g., a 
microprocessor) 16 and a memory 18. The money module 14 includes a CPU 20 
and a memory 22. The money module 12 may be temporarily connected via a 
line 24 to the public switched telephone network 26. The money module 14 
may also be temporarily connected via a line 28 to the public switched 
telephone network 26. Conventional modems (not shown) connect the money 
modules 12,14 to the lines 24,28. Alternatively, the money modules may be 
connected to the public switched telephone network via wireless radio 
channels. Illustratively, the public switched telephone network 26 is an 
ISDN (Integrated Service Digital Network). The money modules 12 and 14 can 
communicate with each other via the public switched telephone network 26. 
Alternatively, a wireless connection 30 can be established between the 
money modules 12 and 14. The wireless connection 30 may be established in 
a cellular network or rely on a direct radio link through the atmosphere 
between the two money modules. A wireless infrared link may also be 
established between the two money modules. 
It should be noted that the CPU's 16 and 20 of the money module 12 and 14 
have limited processing power. In addition, the memories 18 and 22 of the 
money modules 12 and 14 have limited capacity. Thus, it is desirable for 
the e-cash transactions of the present invention to require only limited 
numbers of real time operations at the money modules. 
The network 10 also includes a certificate authority station 32. The 
certificate authority station 32 includes a server 34 and a memory 36. The 
server 34 is connected to the telephone network 36 by the link 38. 
The network 10 also includes a bank station 40. The bank station comprises 
a server 42 and a memory 44. The server 42 is connected by the link 46 to 
the telephone network 26. 
The network 10 of FIG. 1 is illustrative only. While only two money modules 
12 and 14 belonging to users i and j are shown, a network for using e-cash 
may include a large number of such money modules. In addition, there may 
be more than one bank. 
B. Money Format 
As indicated above, each user i has a public key P.sub.i 
.tbd..alpha..sup.Si mod p where .alpha. and p are universally known and 
S.sub.i is a secret key. The secret key S.sub.i includes the identity 
I.sub.i of user i. Illustratively, S.sub.i =(I.sub.i, R.sub.i), where 
R.sub.i is a random string of bits known only to the user i. In addition, 
the user i has a certificate cert(i) which certifies that P.sub.i has the 
identity I.sub.i contained within the exponent S.sub.i. This format is 
important for the exposure of a double spender of a particular e-coin. 
Illustratively, the certificate cert(i) is the signature of a certificate 
authority on f(P.sub.i, 0.sup..gamma.), where 0.sup..gamma. denotes a run 
of .gamma. zeroes and 30 &lt;.gamma.&lt;50. For example, 
cert(i).tbd.(f(P.sub.i,0.sup..gamma.)).sup.dc mod N.sub.c, where d.sub.c 
is the secret RSA exponent of the certificate authority and N.sub.c is the 
modulus of the certificate authority. A detailed process for obtaining the 
certification is described below in connection with FIG. 6. 
A coin of user i has the form (P.sub.i,u,C) where the certified linkage 
C.tbd.(f(P.sub.i,u,0.sup..gamma.).sup.d$) modN.sub.$, where 
u.tbd..alpha..sup.r mod p and, r is a random element chosen by i 
separately for each coin and known only to i. The exponent d.sub.$ is a 
secret RSA exponent of a bank for a particular coin denomination, and 
N.sub.$ is the bank modulus. The bank also has a public RSA exponent 
e.sub.$ such that (m.sup.d$).sup.e$ mod N.sub.$ .tbd.m, for all m. 
C. Payment Transaction 
One transaction which can be performed using the e-cash of the present 
invention is a payment transaction. The payment transaction involves 
communication between the money module 12 belonging to a payer i and a 
money module 14 belonging to the payee j. These communications take place 
via the telephone network 26 or the wireless link 30. The computations 
required in the payment transaction are performed in the CPU's 18 and 20 
of the money modules 12, 14. 
The payment operation is illustrated in FIG. 2 and comprises the following 
steps: 
1. The payer i transmits a coin (P.sub.i,u,C) where the certified linkage 
C.tbd.(f(P.sub.i,u, 0.sup..gamma.)).sup.d$ modN.sub.$ to the payee j. 
2. The payee j verifies the coin by verifying the banks RSA signature, 
i.e., by verifying that C.sup.e$ mod N.sub.$ .tbd.f(P.sub.i, u, 
0.sup..gamma.). If the verification fails, the payment operation is 
aborted. 
3. If the verification is successful, the payee j picks a random message m. 
4. The random message m is transmitted from the payee j to the payer i. 
5. The payer i generates an El Gamal signature s=(u,v) on the message m 
using P.sub.i, S.sub.i, and u. As indicated, P.sub.i and S.sub.i have the 
form of El Gamal public and secret keys. (Alternatively, an NIST-DSS or 
Schnorr signature or other scheme from the El Gamal family may be used). 
6. The El Gamal signature s is transmitted from the payer i to the payee j. 
7. The payee j verifies the El Gamal signature s=(u,v). If the signature s 
is not verified positively, the payment operation is aborted. If the 
signature is verified positively, the payee j stores the coin 
(P.sub.i,u,C), signature s, and the message m in the memory 22. 
It should be noted that the payee j never learns the identity I.sub.i of 
the payer i because there is no easy way to correlate the public key 
P.sub.i with the identity I.sub.i if p is large enough. Thus, privacy of 
the payer i is maintained. 
D. Deposit Transaction FIG. 3 shows a transaction wherein the payee j 
deposits the coin (P.sub.i,u,C) received from the payer i in the bank 40. 
To carry out the deposit operation, the money module 14 of the payee j and 
the bank 40 communicate via the public switched telephone network 26. The 
steps in the deposit transaction are as follows: 
1. The payee j transmits the coin (P.sub.i, u, C) and the El Gamal 
signature s received from the payer i, as well as the message m, to the 
bank 40. 
2. The bank verifies the coin by verifying that C.sup.e$ mod N.sub.$ 
.tbd.f(P.sub.i, u, 0.sup..gamma.). 
3. The bank maintains a list of deposited coins. For each coin, the list 
includes a message and an El Gamal signature obtained on the message using 
the El Gamal key and value of u inside the coin. This list is stored in 
the memory 44. (An expiration date may be added to the coins to limit the 
size of this list). 
4. Using the server 42, the bank 40 compares the coin (P.sub.i,u,C) to the 
list of already deposited coins stored in the memory 44. If a collision is 
found, double spending is detected. Then the identity I.sub.i of the payer 
i is determined. The identity can be determined because two El Gamal 
signatures on different messages but using the same P.sub.i and u result 
in exposure of the secret key S.sub.i. Because S.sub.i contains I.sub.i, 
then I.sub.i is also exposed. This was proven in connection with equations 
(2) and (3) above. If the coin C is not found in the list, the payer's 
signature s is verified. Then the coin (P.sub.i,u,C) and associated El 
Gamal signature s and message m are added to the list maintained at the 
bank. 
5. The payee j has its balance updated by the bank. 
It should be noted that the deposit operation does not reveal the identity 
I.sub.i of the payer i unless the payer is a double spender. 
E. Exchange Transaction 
Another transaction which can be performed using the e-cash of the present 
invention is an exchange transaction. The exchange transaction involves a 
user depositing old e-coins with the bank and withdrawing new e-coins in 
the same total amount. The purpose of the exchange operation is to refresh 
the used cash of a user. A coin is used only once, hence when a user gets 
a coin as a payee he must exchange it for a new coin before he can use it 
as a payer. Illustratively, the exchange transaction is performed by 
communication between the money module 14 of the user j and the bank 40 
using the public switched telephone network 26. As shown in FIG. 4, the 
steps involved in the exchange operation are as follows: 
1) The user makes an anonymous call to the bank. 
2) The payee j sends to the bank the used coin (P.sub.i,u,C), where the 
certified linkage C.tbd.(f(P.sub.i, u,0.sup..gamma.)).sup.d$ mod N.sub.$, 
received from payer i and the El Gamal signature s received from payer i 
along with the message m. 
3) The bank verifies the coin by verifying C.sup.e$ mod N.sub.$ 
.tbd.f(P.sub.i, u,0.sup..gamma.). 
4) The bank compares the coin (P.sub.i,u,C) to a list of already deposited 
coins stored in the memory 44. If a collision is found, double spending is 
detected. Then the identity of the double spender is determined in the 
same manner as for the deposit transaction discussed above. If the coin C 
is not found in the list, the payer's signatures s is verified and the 
coin C is added to the list maintained by the bank. 
5) A certificate, cert(j).tbd.(f(P.sub.j, 0.sup..gamma.)).sup.dc mod 
N.sub.c and u'.tbd..alpha..sup.r' mod p are transmitted from the payee j 
to the bank. 
6) The bank verifies the certificate and forms a new certified linkage 
C'.tbd.(f(P.sub.j, u', 0.sup..gamma.)).sup.d$ mod N.sub.$ which is 
transmitted to the user j, who then formats a new coin (P.sub.j,u',C'). 
Note: For this operation the bank never learns the identity of the payer i 
or the payee j. Nor can the bank associate the coin (P.sub.j,u',C') with 
any particular user as the coin (P.sub.j, u', C') circulates. The reason 
for this is that the bank has no way to correlate P.sub.i or P.sub.j with 
I.sub.i or I.sub.j and because the call is anonymous. 
The above described three transactions--payment, deposit, exchange--are all 
performed in real time and require a minimum amount of operations at the 
money modules. 
F. Withdrawal Transaction 
Another transaction which can be performed using the e-money of the present 
invention is withdrawal from the bank. Illustratively, the user i uses the 
money module 12 to communicate with the bank 40 via the telephone network 
26 to perform the withdrawal operation. The steps in the withdrawal 
operation are shown in FIG. 5 and described below. 
1) The user i transmits its identification I.sub.i, an account number and a 
value to be withdrawn to the bank. 
2) The bank verifies the identification I.sub.i and checks the account 
balance. 
3) The user i picks a random x and forms a blinded candidate linkage 
W=x.sup.e$ f(P.sub.i,u,0.sup..gamma.) mod N.sub.$ and transmits the 
blinded candidate linkage to the bank. 
4) The user i proves to the bank that P.sub.i .tbd..alpha..sup.Si mod p is 
properly formatted and that S.sub.i includes I.sub.i. This is done using a 
zero knowledge proof, or a cut-and-choose technique, for example, so that 
the bank does not learn P.sub.i. Thus, the bank cannot correlate P.sub.i 
and the identity of i. Therefore, the privacy of user i is preserved. 
5) If the bank rejects the proof, the operation is halted. Otherwise the 
bank forms W.sup.d$ .tbd.x(f(P.sub.i,u,0.sup..gamma.)).sup.d$ mod N.sub.$ 
and transmits this quantity to the user. 
6) The user then forms the coin (P.sub.i,u,C) using the 
linkage.tbd.W.sup.d$ /x.tbd.(f(P.sub.i,u,0.sup..gamma.)).sup.d$ mod 
N.sub.$ 
It should be noted that the withdrawal operation is more complex than the 
exchange operation because the user i must prove that P.sub.i as 
incorporated in the blinded candidate linkage is properly formatted 
without revealing P.sub.i. It is expected that the withdrawal operation 
may be avoided most of the time. The reason that the withdrawal operation 
can be avoided is that e-coins can be traded for traceable e-money such as 
e-checks and then the exchange operation can be utilized. 
G. Certification Operation 
As indicated above, the e-money system of the present invention makes use 
of a certification of the key P.sub.i. The certification is carried out 
off--off line by the certificate authority. The money module of a user i 
communicates with the certificate authority 32 via the telephone network 
26. The steps in the certification process of P.sub.i are illustrated in 
FIG. 6 and are as follows: 
1. The user picks a random x and forms the blinded candidate certificate 
Z.tbd.x.sup.ec f(P.sub.i, 0.sup..gamma.) mod N.sub.c. The blinded 
candidate certificate Z is then transmitted to the certificate authority 
along with an identifying I.sub.i. 
2. The user, then proves to the certificate authority that P.sub.i is 
formatted correctly using for example a zero knowledge proof or 
cut-and-choose technique so that the certificate authority does not learn 
P.sub.i and therefore cannot correlate P.sub.i and I.sub.i. 
3. If the proof is rejected, the certificate operation is halted. 
Otherwise, the certificate authority computes Z.sup.dc and transmits 
Z.sup.dc to the user i. 
4. The user i then computes cert (i).tbd.Z.sup.dc /x.tbd.(f(P.sub.i, 
0.sup..gamma.)).sup.dc mod N.sub.c. 
Using this certification process, the certificate authority does not learn 
P.sub.i and, therefore, cannot correlate P.sub.i and I.sub.i. This 
prevents the certificate authority from learning about the e-cash 
transactions performed by the user i, thereby protecting the privacy of 
the user i. 
H. Refresh Operation 
Because it is possible that the correspondence between P.sub.i and I.sub.i 
will leak out (e.g. by means external to cryptography), it is desirable to 
refresh the P.sub.i and cert(i) periodically. The refresh operation is 
illustrated in FIG. 7 and the steps may be described as follows: 
1) The user picks a random x. 
2) The user selects a new key 
P.sub.i '.tbd.mod p, S.sub.i '=(I.sub.i, R.sub.i '), where R.sub.i ' is a 
fresh string of random bits selected by the user i. Using the key P.sub.i 
', a new candidate certificate f(P.sub.i ', 0.sup..gamma.) is selected. 
The new candidate certificate is blinded by computing Y.tbd.x.sup.ec 
f(P.sub.i,0.sup..gamma.). Y and the old certificate cert(i) are 
transmitted to the certificate authority. 
3) The user i proves to the certificate authority that P.sub.i and P.sub.i 
' contain the same I.sub.i, using for an example, a zero knowledge proof 
or cut and choose technique so that the certificate authority cannot 
correlate P.sub.i or P.sub.i ' with I.sub.i. 
4) If the certificate authority rejects the proof the operation is halted. 
Otherwise the certificate authority computes (Y).sup.dc and transmits this 
value to the user i. 
5) The user i then computes a new certificate cert.sub.2 (i).tbd.(Y).sup.dc 
/x.tbd.(f(P.sub.i, 0.sup..gamma.)).sup.dc mod N.sub.$. 
I. Cut and Choose Technique for Proving P.sub.i has the Correct Structure 
An illustrative technique for proving the P.sub.i has the proper structure 
is now discussed. This technique is known as a cut-and-choose technique 
(see e.g. D. Chaum, A. Fiat, M. Naor Untracable Electronic Cash. Proc. 
Crypto 1988; M. O. Rabin, Digitalized Signatures in Foundations of Secure 
Computation, Academic Press, No.1., 1978). 
This technique involves the use of more than one copy of the user 
identification (I.D.). I.sub.i in the exponent of the public key P.sub.i. 
The exponent has k+2 fields. The k left most of these fields are of a size 
.gamma.=log2Y(I.sub.i) bits. These k fields are known as I-fields. 
Normally, (i.e., if nobody cheats) each field holds the correct I.D. When 
the exponent of a double spender of a coin is computed, if there was 
cheating in the initial certificate, and the exponent contains a few 
distinct candidate identifications, then it may happen that more than one 
of them needs to be examined (e.g., up to k, k=40, is needed for a one in 
a million fraud success probability). 
Various policies are possible regarding a mixed exponent. One example of a 
policy for handling a mixed exponent is the following: On double spending, 
incriminate the user whose ID appears a majority of time in the exposed 
exponent. This policy implies that the best strategy for a cheater is to 
try to consistently incriminate some other real user (say j, whose 
indentificatoin is I.sub.j) by placing the other user's ID in at least k/2 
of the I-fields. In this case, the cheating success probability is 
0(2.sup.-k/2). 
The following notation is used in the description cut-and-choose technique 
for verifying that P.sub.i is properly structured. 
As before, variables with subscripts $, c are associated with Bank and 
Certification Authority respectively. Let I.sub.i denote user i's unique 
ID. All ID's are of size .nu. bits, and all random variables R.sub.ij are 
of size .rho. bits, and are drawn with uniform distribution over 
{0,1}.sup..rho.. 
Let 
##EQU1## 
(here (q) is another index, not exponent), i.e. 
##EQU2## 
P.sub.ij .tbd..alpha..sup.sij mod p, .sigma.=log.sub.2 
(s.sub.ij).gtoreq.(1+.nu.).multidot.k+.rho., log.sub.2 p&gt;.sigma.. All 
random variables x.sub.ij are of size log.sub.2 N (whichever N is 
relevant, i.e. N.sub.c in Initial-certificate and Refresh-certificate, and 
N.sub.$ in Withdrawal-from-account, and Exchange), and are drawn with 
uniform distribution over {0,1}.sup.log.sbsp.2.sup.N. L denotes the run of 
.gamma. zeroes. 
The cut-and-choose technique is used for Initial certificate, Withdrawal 
and Exchange and Refresh Certificate. 
"Cut and Choose" Initial Certificate 
The use of the cut-and-choose technique to obtain the Initial certificate 
is illustrated in FIG. 8. The technique is divided into two phases, phase 
I and phase II. 
Phase I 
1. User i authenticates herself to Certificate Authority (CA), and presents 
k blinded pairs 
##EQU3## 
where 
##EQU4## 
2. CA picks with uniform distribution a binary vector of length k (denoted 
subsequently in short as e .epsilon..sub.R {0,1}.sup.k), and sends it to 
user i. Let e=(e.sub.1. . . e.sub.k). (FIG. 8, Step 3). 
3. For j=1 . . . ,k, user i transmits 
##EQU5## 
to the Certificate Authority (CA) which verifies consistency with 
##EQU6## 
as indicated in step 4 and step 5 of FIG. 8 (this is total exposure and 
total verification). 
4. CA computes 
##EQU7## 
(e.sub.j means the binary complement of e.sub.j) then signs its, i.e., 
computes 
EQU C.sub.i .tbd.B.sub.i.sup.dc c mod N.sub.c, 
and transmits Ci to user i. (step 6 and 7 of FIG. 8) 
5. User i un-blinds C.sub.i, to produce 
##EQU8## 
D.sub.i is not revealed to CA at this point. (step 8 of FIG. 8) Phase II 
It should be noted that phase II takes place at an uncorrelated time after 
the completion of phase I. 
1. User i makes anonymous call to CA, and presents D.sub.i, and the 
corresponding 
##EQU9## 
CA verifies his signature on D.sub.i, and consistency of the given 
components (partial structure verification). (FIG. i, steps 9, 10, 11) 
2. For each 
##EQU10## 
user i proves to CA that all the i-fields, except the j'th, are zeroes, 
using gradual verifiable unordered release of zeroes of Dicrete Log (DL) 
(This is discussed below.) (FIG. 8, step 12.) 
3. CA computes 
##EQU11## 
This is i's initial certificate. It is known to CA, however the linkage 
between this certificate and i is not known. 
Analysis 
If i was honest then the exponent of 
##EQU12## 
contains k copies of I.sub.i. 
Step 2, of phase II guarantees that with probability 1-2.sup.-n the DL of 
each component used in the construction of the certificate is structured 
correctly, with respect to the nullified fields. The only other way that 
user i can cheat is to use false ID's (in the right places). The 
probability of each component not to be caught is 1/2 (step (3) of Phase 
I). Hence the probability that no S.sub.ij is correct is O(2-k). 
Similarly, the probability to have .left brkt-top.k/2.right brkt-top. 
corrupt entries (the best cheating strategy is to introduce .left 
brkt-top.k/2.right brkt-top.+1 consistent wrong entries, I.sub.i, thus 
incriminating some user with that ID) without getting caught is 
O(2.sup.-k/2). This is also the total cheating probability for n=k. 
Withdrawal from Account 
This is done like in Initial-certificate, where the bank plays the role of 
CA, and in phase II the user presents to the bank, in addition, an element 
u.tbd..alpha..sup.r mod p, for which the user knows r. The user gets from 
the bank a blinded coin x.multidot.(f(P.sub.i,u,L)).sup.d$ mod N.sub.$, 
where log.sub.2 (N.sub.$),=l(p.sup.2), and she un-blinds it. 
Refresh Certificate 
The main idea is to prove that the old and new components of the 
certificate have the same ID, I.sub.i, in the exponents by dividing them. 
If the claim is true then those IDs cancel out. This does not explicitly 
reveal their values. The result is a shorter exponent. This fact is proved 
using a technique described below. The primed and unprimed variable denote 
old and new certificates (and the other corresponding variables), 
respectively. The refresh certificate is obtained using the following 
steps: 
1. User i makes anonymous call to CA, and presents an old certificate 
E.sub.i ', and its components, P.sub.ij ', 1.ltoreq.j.ltoreq.k, and CA 
verifies them (structure and signature). These are partial exposure and 
verification. (FIG. 9, steps 1 and 2.) 
2. User i presents to the bank k pair candidates 
##EQU13## 
q=0,1; 1.ltoreq.j.ltoreq.k, for a new certificate. (FIG. 9, step 3.) 3. 
CA picks with homogeneous distribution e .epsilon..sub.R {0,1}.sub.k, and 
sends to user i. 
4. For j=1 . . . k, user i sends 
##EQU14## 
(but, unlike in Initial-certificate, not 
##EQU15## 
and CA verifies structure consistency (partial exposure and 
verification). (FIG. 9, step 3.) 
5. Let 
##EQU16## 
Both CA and user i compute 
##EQU17## 
and user i proves to CA that this is congruent modulo p to 
.alpha..sup..delta., where .delta. is short (i.e., log.sub.2 .delta.=p+k). 
This is done using the technique described below, without revealing the 
actual exponents (i.e., the p+k least significant bits of the exponent 
remain secret). (FIG. 9, steps 7 and 8.) 
6. If the check passes positively for all pairs in step (5) CA proceeds as 
in Initial-certificate (phase I, step 4, etc.). 
Now E.sub.i is the refreshed certificate. 
If a user is caught cheating even once on "Refresh", his old certificate is 
revoked. It is true that if an old certificate contains undetected false 
I-fields, then a user can replicate them in the new 2xk matrix of 
candidate components 
##EQU18## 
(contaminate the corresponding column likewise). This implies that with 
probability 1/2 a cheater can successfully sneak in a new contamination. 
However, the cheater must successfully sneak in k/2 consistent false 
entries, and this may happen (even if the cheater does it one at a time, 
but consecutively) with probability of only O(2.sup.-k). 
To sum up, cheating probability is O(2.sup.-k +2.sup.-n). The first 
component comes from the cut and choose portion of phase-I (like in 
"Initial certificate"), and the second component comes from the technique 
for proving certain fields of a discrete-log discussed below. So, for k=n 
(a reasonable choice) we get cheating probability 0(2.sup.-k). 
Efficient Method for Proving the Value of Certain Fields of a Discrete-log 
without Exposing the Rest 
A prior art technique for solving this problem is disclosed E. F. Brickell 
et al. "Gradual and Verifiable Release of a Secret" Proc. Crypto 87. While 
in 2! bits are released in order most significant first, we can release 
any segment. In our method, as well as in that of the reference the 
release is not total. In the inventive method there is a residual 
uncertainty of 1 bit, and similarly in the reference, if the DL is in the 
interval a, a+B), then the prover can prove that it is in a-B,a+2B!. 
There is first explained a simplified version that releases only zero 
segments (which is all that is needed for the e-money system of the 
present invention), and then generalize to release any value. 
The technique is as follows: 
Given P.sub.ij .tbd..alpha..sup.Sij mod p, the goal is to prove that 
S.sub.ij has the above structure, without exposing it. 
The goal is accomplished by repeating the following process n times: 
1. Prover picks random .beta..sub.1 and .beta..sub.2 of sizes log.sub.2 
.beta..sub.1 =.nu., and log.sub.2 .beta.=p, and creates a vector v of the 
same structure as S.sub.ij, namely, v=(0,0 . . . .beta..sub.1,0, . . . 
0,0.sup.k,.beta..sub.2), where .beta..sub.1 occupies the j.sub.th I-field. 
The prover then computes .alpha..sup..nu. mod p and sends it to the 
verifier. 
2. The verifier challenges the prover at random to either 
(a) Expose v, or 
(b) Expose S.sub.ij +v (ordinary addition, when the two components are 
viewed as integers). 
3. The prover responds to the challenges accordingly, and the verifier 
checks that 
(a) v is of the right structure, and is consistent with the committed 
.alpha..sup.v mod p, or, 
(b) S.sub.ij +v is of the right structure (has zeroes where expected, with 
at most one bit overflow allowed from each non-zero field), and that 
.alpha..sup.Sij+v .tbd.P.sub.ij .multidot..alpha..sup.v mod p, 
respectively. 
The prover is committed to v and S.sub.ij, hence if the prover can respond 
to the two challenges correctly then S.sub.ij is of the right structure, 
With probability 1/2, v is of the right structure (when asking to expose 
S.sub.ij +v), and the verifier sees that S.sub.ij +v looks rights, hence 
so does S.sub.ij. Repeating the above n times, and aborting if even in one 
case the response is incorrect, will reduce error probability to 
O(2.sup.-n). 
To release any value, x, of a segment, proceed with v as before (i.e. v has 
zeroes in that segment). The verifier checks that v indeed has zeroes 
there, or that s.sub.ij +v has value x there, with one bit overflow 
allowed. So, this method reduces the entropy of a segment of length .eta. 
bits exponentially fast from .eta. bits to 1 (bit). 
Conclusion 
In short, a unique electronic cash system has been disclosed. The 
electronic cash system of the present invention protects the privacy of 
users in legitimate transactions, while at the same time permitting the 
identity of a double spender of a particular electronic coin to be 
revealed. These highly beneficial results are achieved through the use of 
the El Gamal signature scheme and other public key cryptographic 
techniques. 
It should be noted that while certain operations utilized in connection 
with the invention have been described herein through use of the RSA 
public key cryptographic technique, other public key cryptographic 
techniques such as Rabin modular square roots may be used in place of RSA. 
Finally, the above described embodiments of the invention are intended to 
be illustrative only. Numerous alternative embodiments may be devised by 
those skilled in the art without departing from the spirit and scope of 
the following claims.