ABSTRACT

Coming along with the tremendous development of computer-based technology, electronic payment systems introduce such a hot research topic involving many researchers as well as the industry people. The main idea of electronic payment systems is to perform financial transactions via electronic information exchanged over telecommunications media.

There are many forms of Electronic Payment Systems such as digital checks, debit cards, credit cards, and store value cards. This paper is intended to survey aspects of Electronic cash, or Digital Cash, which we will call E-cash from now on. Moreover, we shall cover many related issues arising in the design and implementation of such systems.

There are three main issues arising with E-cash systems. The first one is security issue. It's desirable for such systems to ensure privacy (protection from eavesdropping), authenticity (provides users identification and message integrity), and non-repudiation (prevention of later denying having performed a transaction).

Secondly, as the name said it all, E-cash is an attempt to construct and electronic payment system modeled after our paper cash system. Thus, a E-cash system should be able to ensure the same properties as what paper cash has : portability, recognizability and hence readily acceptable, transferable (without involvement of the financial network), more importantly and more difficultly, untraceability (no record of where the money is spent), anonymity (no-one knows who has spent the money).

Finally, electronic payment systems are likely to present some of the most complex challenges to lawyers, policy makers and more general, the governments. Although, it's a bit soon to tell which if any of these E-cash products will become widely used. Whatever projects persist, national governments are likely to be concerned about E-cash because they will fear that it facilitates illicit transactions, and makes money laundering easy. The main conflict is between data profilers and privacy-seekers.

This report is organized as follows. Section I gives the basic definition E-cash and the advantages of having it. Section II is an overview of cryptographic knowledge needed to understand the details of those schemes. Section III describes various desirable characteristics of E-cash, and some of the proposed schemes to achieve them. Section IV is a trial to summarize the proposed practical systems that are being developed around the world. Section V represents many social issues related to E-cash. And section VI gives us a brief conclusion.

I. What is E-cash? Why E-cash ?

E-cash is money that moves along multiple channels mostly outside the established network of banks, checks, and paper currency overseen by the Federal Reserve (or any other central bank). These channels enable consumers and businesses to send money to each other more cheaply, conveniently, and quickly than through the banking system. In its simplest form it is a replacement for the cash and checks that consumers use to perform ordinary, daily transactions. The reality of E-cash will transform the way the public perceives money, It will change consumer habits, create new business opportunities, and could even drastically change global finance.

The benefits of E-cash are numerous. It is more convenient and more flexible. Consumers will no longer have to carry cash. Businesses can conduct transactions outside of a bank system and will be able to reach more consumers easier. Banks will reduce expenses related to the current paper money system. Privacy of transactions is enhanced as compared to current credit card systems. Because E-cash is basically software it can be programmed as "smart E-cash", able to be used only for specific types of transactions.

But E-cash doesn't come for free. Protecting it from hackers and criminals is the biggest issue. Money laundering and tax evasion could mushroom. Counterfeiters could create their own cash. Uncontrolled growth could undermine bank and government controlled money systems.

II. Some cryptographic background knowledge :

2.1 Public key cryptosystems :

The idea behind public key cryptosystem is that it might be possible to find a cryptosystem where it is computationally infeasible to determine d_K (the key used for decryption) given e_K. If so, then the encryption rule e_K could be made public by publishing it in a directory.

The idea of a public-key system was due to Diffie and Hellman in 1976. The first well-known public key system was RSA cryptosystem by Rivest, Shamir and Adleman.

Since then, several public-key systems have been proposed. Of these, the most important are the followings:

• RSA, whose security is based on the difficulty of factoring large integers. This system will be talked about in more details shortly, because many schemes represented in this paper are based on RSA.

• Merkle-Hellman Knapsack, which is based on the difficulty of subset sum, a NP-complete problem.

• McEliece, which is based on the problem of decoding a linear code, which is also NP-complete.

• ElGamal is based on the difficulty of discrete log problem for finite field.

• Chor-Rivest is one type of knapsack systems.

• Elliptic Curve systems are modifications of other systems ,such as the AlGammal Cryptosystem, that work in the domain of elliptic curves rather than finite fields. One important property is Elliptic Curve Cryptosystems is that it appears to remain secure for smaller keys than other public key systems.

It is helpful conceptually to think of a public-key cryptosystem in terms of an abstraction called a trapdoor one-way function, which is a correspondence between 2 sets which can be computed efficiently in one direction but not the other. In addition, a one-way function is a trapdoor one-way function if it is easy to invert with the knowledge of a certain trapdoor.

The RSA public key cryptosystem :

Let n = pq, where p and q are large primes. Let a and b be integers in Z*_n such that ab = 1 (mod phi(n)).
Note that phi(n) = (p-1)(q-1). We define the followings.

e_K(x) = x^b mod n

and

d_K(x) = y^a mod n.

The important point to notice here is that d_K(e_K(x)) = x and vice versa. The values n and b are public, and the values p, q, a are secret. The security of RSA is based on the hope that the encryption function e_K(x) = x^b mod n is one-way.

• Digital Signature Schemes are the methods of signing a message stored in electronic form. As such, a signed message can be transmitted over a computer network. Here are some of the most well-known schemes : RSA signature, ElGamal Signature, One-time Signature, Undeniable Signature, Fail-stop signature. The brief description of RSA signature is as follows.

• RSA signature scheme

  Let n, p, q, a, b are the numbers defined as in RSA public key scheme. Define

  sig_K(M) = M^a mod n

  and

  ver_K(M, y) = true <=> M = y^b (mod n).

  Here M is the message, y is the signature of M signed by Alice.

• Identification Schemes are the method for Alice to identify herself to Bob, say, in such a way that someone tapping the communication line between Alice and Bob should not subsequently be able to misrepresent herself as Alice. Furthermore, we also try to guard against the possibility that Bob himself might try to impersonate Alice after she has identified herself to him. In other words, by using some identification scheme, Alice wants to be able to prove her identity electronically without "giving away" her identifying information.

2.3 Cut-and-choose protocol and Zero-knowledge proof :

• Cut-and-choose protocols, also called interactive proof or challenge-and-response protocols are the protocols in that the Prover wants to prove that she knows some certain fact to the Verifier, and she achieve that by response to one or more challenge given by the Verifier.

• Zero-knowledge proof systems allow one person to convince another person of some fact without revealing any information about the proof.

III. Proposed schemes to achieve desirable features of E-cash

3.1 Basic definitions :

• Privacy : protection against eavesdropping on one's communication line. However, this definition of privacy is not strict enough. Users in general want two more features that are followed.

• Anonymity or unlinkability: The issue of anonymity involves a spectrum of positions that will be represented in the social issues part of this paper. Basically, anonymity means that nobody knows who has spent the money.

• Untraceability : this ensures that the bank can not link a specific deposit transaction with another specific withdrawal transaction like it does with credit card.

• User identification : a user must know to whom she is dealing with.

• Message integrity : protection against tampering or substitution.

• Non-repudiation : protection against later denial of a transaction.

  Moreover, here are the features that a E-cash system must ensure to protect users from counterfeiting, which can be the followings :

• Token forgery : creating a valid looking coin without making a corresponding Bank withdrawal.

• Multiple spending, or re-spending, double-spending, repeat-spending ..., which means use the same coin over again. A coin is basically a bit-stream, it's really easy to make an identical copy of a valid coin.

  Finally, E-cash is desirable to have the following properties, which in fact effect the performance of the system quite a lot, and more importantly, those properties have a certain impact on the complexity of the system.

• Transferability : like paper cash, which can be transfer from one person to another without bothering the Bank.

• Divisibility : is very desirable. If the value of a coin is, say, 20$, but Alice want to purchase a online magazine for just 26 cents or so, it's very unlikely that Bob have enough small value coins to give the change back to Alice.

3.2 Basic protocols :

1. The electronic payment scenario assumes three kinds of players :
   • a payer or consumer, whom we'll name Alice
   • a payee such as a merchant, whom we'll name Bob.
   • a financial network with whom both Alice and Bob have accounts. We'll refer the the financial network as the bank.

2. Typically, there are three types of transactions in a electronic baking system :
   • Alice withdraw some of her money from the Bank by means of electronic tokens or electronic coins.
   • Alice want to buy goods from Bob, the merchant, she give the coins to Bob.
   • The last type of transactions is deposit. Bob deposit the coins he has gotten from Alice back to the Bank.

   E-cash protocols can be divided roughly into two types, which are on-line protocols and off-line protocols.

   On-line protocol requires that every transaction between Bob and Alice be cleared through the bank at the time of the transaction.

   Off-line protocol means that Bob submits Alice's coin for verification and deposit sometime after the payment transaction is completed.

3. Basic on-line cash and off-line cash models

   The basic E-cash model is fairly simple: the Bank issues the user a very large, probabilistically unique, random number (the "serial number" of the coin) signed with the Bank's private key. When Alice wants to spend the coin, she sends it to Bob, who turns it in to the bank either on line, or after the fact (off-line). The bank checks the serial number against its list of spent coins and, if the coin has not previously been spent, either credits Bob's account or issues him a new coin with a new serial number. So long as the bank is honest, Alice and Bob both have the proof they need that the transaction, and the payment, occurred.

   These basic models are also computationally simple to implement. Each coin requires a long, unique, random number, but the bank can re-use the same private-public key pair to sign every coin of a given denomination.

   However, this basic model have the following undesirable problems.

   • It does not ensure untraceability and anonymity , which means that the customers have no privacy at all. Since the serial numbers of the coins are issued by the bank, after Bob deposits the coin, the bank can tell exactly who has spent the coin (Alice) and where the coin has been spent (Bob's place).
   • If the verification phase is on-line, the overhead is just not tolerable in general. Even Alice wants to send a small amount of money, for instance, 10 cents to read a page of an online magazine, she and Bob still have to bother the Bank to verify the validity of the coin. That make the on-line cash protocol somewhat impractical, due to the delay, expense it introduces. It is, however, easier to avoid double spending using on-line cash protocol because the bank can check against its spent coin database to see if the coin is already spent.
   • If the verification phase is off-line, which means that Bob will defer depositing the coin at some later time, we face another severe problem, how to prevent double spending. Because the merchant can defer the deposit phase to do later, if the payer multiple spends the electronic coin (or electronic token in general), it is really difficult to avoid such a fraud.

3.3 Achieving privacy with blind RSA signature :

Every time we buy something using credit cards, or checks, etc. , we have to reveal some information about us that would help the merchant to identify us. All of that information can be linked together to have a perfect record telling when, where and what we have bought, and even reveals the amount of money we spent in each of the transaction. The idea of Blind RSA Signature was first proposed by Chaum. We will outline the basic idea of how it works.

Blind RSA signature

Let n, p, q, a , b be the 5-tuple in RSA public key system. Suppose Alice wants the Bank to produce a blind signature of the message M, She generate a random number r and sends

r^bM (mod N)

to the Bank to sign. After signing, the message becomes

(r^bM)^a = r.M^a (mod N)

Alice then removes the blind factor r by divide this result by r. The result is exactly the signature of the Bank on message M, which is M^a, even though the Bank has never seen M

Untraceable Off-line-electronic payment protocol :

Withdrawal :

Alice creates an electronic coin and blinds it.
Alice sends the binded coin to the Bank with a withdrawal request.
Bank digitally signs the blinded coin.
Bank sends the signed blinded coin to Alice and debits her account
Alice unblinds the signed coin.

Payment :

Alice gives Bob the coin
Bob verifies the Bank's signature (optional) Bob gives Alice the merchandise.

Deposit :

Bob sends coin to the Bank
Bank verifies the Bank's signature. Bank verifies that the coin has not already been spent. Bank enters coin in spent coin database.

3.4 Proposed E-cash schemes

From the academic literature, there are three main off-line cash schemes proposed, which are those of Chaum-Fiat-Naor [9], Stefan Brands [10], and Niels Ferguson [11]. Here is a brief introduction about those three schemes :

• Chaum-Fiat-Naor : This was the first E-cash scheme and is the simplest conceptually. They used Cut-and-choose protocol during withdrawal step, so this scheme is not quite efficient. But, it is important in the sense that it gives us the first view of how to achieve privacy and also prevent double-spending. We are going to go through details of this scheme shortly.

• Brands in his paper introduced a scheme which is based on Schnorr's Algorithm. This scheme is considered to be the best of the three for several reasons. First, it doesn't use inefficient cut and choose protocol. Secondly, it can be used with elliptic curve because it is not RSA based.

• Ferguson scheme is RSA based like CFN but it uses the principle two point on a line like Brands'. Moreover, this scheme uses a variant of digital signature called randomized blind RSA signature, which was introduced by Chaum. The ordinary signature has one disadvantage which is that the Bank has no idea if the serial number of the coin produced by Alice was actually be chosen randomly or not. By using randomized blind signature, the Bank contributes to the process of producing that random serial number. Now, it still doesn't know what it is signing but it can be sure that the serial number is random. This scheme is the most complicated of the three.

3.5 Chaum-Fiat-Naor scheme

Chaum, Fiat and Naor from the Crypto 88 proceedings introduced a protocol not only to achieve privacy but also to detect multiple spender.

The idea is to require Alice to have, in addition to her electronic coin, some sort of identifying information which she is to share with Bob. The important point here is that if she spends the coin only once than her privacy can be ensured; otherwise, if she tries to multiple-spend the coin, her identity will be revealed.

This information is created during the withdrawal step. The withdrawal protocol includes a step in which the Bank verifies that the information is there and corresponds to Alice and to the particular coin being created. (To preserve payer anonymity, the Bank will not actually see the information, only verify that it is there.) Alice carries the information along with the coin until she spends it.

At the payment step, Alice must reveal one piece of this information to Bob. (Thus only Alice can spend the coin, since only she knows the information.) This revealing is done using a challenge-response protocol. In such a protocol, Bob sends Alice a random "challenge" quantity and, in response, Alice returns a piece of identifying information. (The challenge quantity determines which piece she sends.) At the deposit step, the revealed piece is sent to the Bank along with the coin. If all goes as it should, the identifying information will never point to Alice. However, should she spend the coin twice, the Bank will eventually obtain two copies of the same coin, each with a piece of identifying information. Because of the randomness in the challenge-response protocol, these two pieces will be different. Thus the Bank will be able to identify her as the multiple spender. Since only she can dispense identifying information, we know that her coin was not copied and re-spent by someone else.

The protocol :

Withdrawal:

Alice creates an electronic coin, including identifying information.

Alice blinds the coin.

Alice sends the blinded coin to the Bank with a withdrawal request.

Bank verifies that the identifying information is present.

Bank digitally signs the blinded coin.

Bank sends the signed blinded coin to Alice and debits her account.

Alice unblinds the signed coin.

Payment:

Alice gives Bob the coin.

Bob verifies the Bank's digital signature.

Bob sends Alice a challenge.

Alice sends Bob a response (revealing one piece of identifying info).

Bob verifies the response.

Bob gives Alice the merchandise.

Deposit:

Bob sends coin, challenge, and response to the Bank.

Bank verifies the Bank's digital signature.

Bank verifies that coin has not already been spent.

Bank enters coin, challenge, and response in spent-coin database.

Bank credits Bob's account.

Note that, in this protocol, Bob must verify the Bank's signature before giving Alice the merchandise. In this way, Bob can be sure that either he will be paid or he will learn Alice's identity as a multiple spender.

Cryptographic details :

The bank initially publishes RSA modulus n whose factorization is kept secret and for which phi(n) has no small odd factors. The bank also sets some security parameter k.

Let f(x,y) and g(x,y) be two-argument collision-free functions; That is, for any particular such function, it is infeasible to find 2 inputs that map to the same point. Today, there are several suitable choices for one-way functions, the most common being the MD4 and MD5 algorithms from RSA. Alice has a bank account numbered u and the bank keeps a counter v associated with it. Denote || as the concatenation.

Withdrawal step :

To get an electronic coin, Alice conducts the following protocol with the bank :

1. Alice chooses a_i, c_i and r_i, 1 <= i <= k, independently and uniformly at random from the residues (mod n)
2. Alice forms and sends to the bank k blinded candidates (called B for mnemonic purposes).

   B_i = r_i³.f(x_i,y_i) mod n

   for 1 <= i <= k,

   where

   x_i = g(a_i, c_i)
   y_i = g(a_i xor "info", d_i)

   for "info" = (u || (v + i))

3. The bank chooses a random subset of k/2 blinded candidate indices R = {i_j} 1 <= i_j <= k for 1 <= j <= k/2 and transmits it to Alice.
4. Alice displays the r_i, a_i, c_i, and d_i values for all i in R and the Bank checks them. Note that "info" is known to the bank. To simplify the notation, we assume that R is the set {k/2 + 1, .... k}, which is the set of the upper half of numbers from 1 to k.
5. The Bank gives Alice the product of all B_i^1/3 where i is not in R , that means that i belongs to { 1, 2, ... k/2 }, and then charges her account one dollar. The bank also increments Alice's counter v by k.
6. Alice can then easily extract or unblinds the electronic coin C

Payment and deposit protocol

To pay Bob one dollar, Alice and Bob proceed as follows:

1. Alice sends C to Bob.
2. Bob chooses a random binary string z₁, z₂, ... z_k/2
3. Alice responds as follows, for all 1 <= i <= k/2 :

   a. If z_i = 1, then Alice sends Bob a_i, c_i and y_i
   b. If z_i = 0, then Alice sends Bob x_i, a_i xor "info" and d_i.

4. Bob verifies that C is of the proper form and that Alice's responses fit C
5. Bob later sends C and Alice's responses to the bank, which verifies their correctness and credits his account.

   The Bank must store C, the binary string z_i and the values a_i (for z_i = 1) and a_i xor "info" (for z_i = 0)

First of all, at the withdrawal step, why are there too many a_i, r_i, c_i, etc. ? Well, there are several points we need to notice here. Firstly, Alice needs to blind the coin before sending it to the bank. She does so by multiply all the f(x_i, y_i) by r_i³. This is just like what we have seen with the RSA blind signature protocol above to ensure privacy. Secondly, when the bank signs those B_i, the bank needs to know to whom it is dealing with, so by a challenge and respond protocol, the bank tests Alice's identity on half of those B_i, where i is in R, which cardinality is k/2. This is how it checks :

• For all i in R, Alice have to provide the Bank all the a_i, r_i, c_i, and d_i, so the Bank can easily check to see if the appropriate B_i are valid. Note that the Bank knows the "info" when it checks the validity of B_i. It simply just unblinds those f(x_i, y_i) and does the same thing as Alice does.

• If Alice wants to cheat by putting Hung instead of Alice into the "info" field, she will be caught with high probability because the Bank checks half of them.

• If Alice only puts Hung in a very small number of those "info", then as we'll see, she will be caught with very high probability if she tries to double spend the coin later on.

One more point to notice here is that this is a cut-and-choose protocol, so it is not quite efficient.

Next, the cash is the product of k/2 numbers, where k is a "security parameter" that affects the chance of a cheater getting away with it. It is more difficult for the criminals to forge cash when the bank use different values of k's. Although, we already have one level of security when the Bank signs the cash. The assumption is that nobody can forge the Bank's signature on the cash. Each number in the cash is of the form f(x_i,y_i)^1/3 , where f is a two-argument one-way function. (The "x_i", "y_i", "a_i", etc. here are separate values for each i from 0 to k/2.). x_i and y_i are like this: x_i = g(a_i, c_i), where a_i and c_i are random, and g is another one-way function. y_i is kind of complicated. It is basically g(a_i xor "info", d_i). d_i is another random number, and "info", the key to this whole operation, is identifying information about Alice's account! It is her account number concatenated with a serial number for the cash.

The main point is that if you could find out both a_i and (a_i xor "info"), for some i, you would know Alice's identity. (Xor'ing them would produce "info" back) When Alice double-spends, both a_i and (a_i xor "info") will be revealed with very high probability. Why do we need those one way function ? Because, we want to bury the "info" deeply into the coin.

What happens when Alice spends the coin is this. For each i from 0 to k/2 Bob chooses 0 or 1 at random. If he chooses 1 he gets told a_i (and some other stuff). If he chooses 0 he gets told a_i xor (and other stuff). The other things he gets told are sufficient to let him confirm that the money is of the proper form. Now, if Bob does this, he'll know a bunch of a_i's, and he'll know a bunch of (a_i xor "info")'s, but they are for different i's. He doesn't know both a_i and (a_i xor "info") for any one i. So he can't break Alice's anonymity. When Bob deposits the money at the bank, he passes along the information he got from Alice regarding the a_i's and such.

Now, suppose Alice cheats. She spends the money again somewhere else, at Charlie's. Charlie goes through the same procedure as Bob, choosing 0 or 1 at random for each value of i. Here is the catch. Since he is choosing at random, it would be very unlikely that he will choose exactly the same 0's and 1's that Bob chose. (Here is where the size of k matters - making it bigger makes it less likely that Charlie and Bob will choose the same pattern of 0's and 1's. But it makes the calculations take longer.) That means for one or more values of i, Charlie will probably choose a 0 where Bob chose a 1, or vice versa. Because of this, if Bob got a_i for that i, Charlie will get (a_i xor "info". Or if Bob got a_i xor "info", Charlie will get a_i. Either way, when Charlie sends his record of this information to the bank, the bank will put Bob's and Charlie's information together and get both a_i and a_i xor . Xor'ing these together reveals , and Alice is caught! As mentioned earlier, if Alice tries to cheat at the withdrawal phase by putting Hung in the coin for a few value of B_i, then here we can see that she will be caught double spending with very high probability.

All the other things, the c_i's and d_i's and such, are there so that Bob can confirm that the money is of the proper form. For each value of i Alice has to give him enough information to calculate x_i and y_i. If Bob chooses a 1, she gives him a_i, c_i, and y_i. Given a_i and c_i Bob can calculate x_i ( = g(a_i,c_i)), and with this and y_i he can calculate f(x_i,y_i). If Bob chooses a 0, she gives him (a_i xor "info"), as described before, and also d_i and x_i. Given (a_i xor "info") and d_i, Bob calculates y_i ( = g(a_i xor "info", d_i)), and with this and x_i he can calculate f(x_i,y_i).

So for each i, whether Bob gives a 0 or a 1 he gets enough information to calculate f(x_i,y_i). He multiplies these all together and confirms that they are equal to Alice's original "money" value when it is taken to the 3rd power (recall the money was product of f(x_i,y_i)^1/3 for all i). Only the bank could have produced a signature on this one-way function f whose arguments take this special form.

One more important point no notice here is that there can be a collusion between Alice and a second shopkeeper Charlie. After the transaction with Bob, Alice describes the z's to Charlie, and both Bob and Charlie send the bank the same information; The Bank knows that with very high probability (1 - 1/2^k) that one of them is lying, but has no way of telling which one, and cannot trace the coin to Alice's account.

To solve this problem, we can fix Bob's challenge to Alice. Every shopkeeper has a fixed query string, and every two strings have Hamming distance at least ck for some constant c. However, to prevent Alice from reusing the same coin at the same shop, part of the challenge should still be random, or the shopkeeper should maintain his own list.

Disadvantages of Chaum-Fiat-Naor

This was the first electronic cash scheme, and is simplest conceptually of all the known schemes so far. The other two are Brands' scheme and Ferguson's scheme.

• The first disadvantage is that the coin has to contain twice as much as the information which is really used.

• Secondly, the prevention of multiple spending is accomplished by the cut-and-choose method, thus, this scheme is relatively inefficient.

• Thirdly, as stated above, to prevent collusion of Alice and Charlie, we have to force each merchant to have a fix challenge which is difficult to implement in an wide area.

• Finally, multiple spending can be prevented only after the fact. This is a very severe problem for the Bank, because Alice can spend a large amount of money and then disappear. Even we can avoid the loss by only grant a small amount of money in each denomination of cash, this is still undesirable. The only way that we can use to limit double spending before the fact is to have some sort of physical security devices, such as a card, which can only be broken by a national laboratory. That type of security is presented by Brands.

3.5 Brands scheme : Electronic Wallet with Observers

As mentioned earlier, it is really desirable to detect double-spending problem before the fact. It turns out that it (almost) impossible to do that without a tamper-resistant device, which can be broken only be a huge laboratory at national level. Here, we attempt to summarize the idea due to Brands introduced in his paper [10].

The idea of having an observer is that it can be incorporated in the wallet (a card granted to each user's account by the bank) in such a way that no user-module can do a transaction on its own: in order for any transaction protocol to be executed by the wallet, it needs help (secret information) from the observer. In effect, the observer authorizes the transaction. For the double-spending problem, this would simply mean that the observer takes part in the payment protocol, an would register information that is used in a payment. When a user wants to spend the same information a second time, the observer simply does not authorize the transaction. In order to be able to double-spend, users therefore are faced with the problem of having to break the tamper resistance of the observer: the user can then find out the secret information of the observer, and have the user-module simulate the part of the observer in the payment protocol. A secure off-line cash system must therefore definitely be such that even in that case, the same security as achievable in the setting with user-modules only is guaranteed, i.e, the double-spender is identified after the fact. Not minding about additional properties for the moment, an efficient system provably accomplishes this can be qualified as being close to the ideal off-line electronic cash system.

So far, so good. However, it seems that we have actually arrived at an impasses : how is the privacy of the users to be guaranteed if they carry a tamper-resistant module with them which takes part in all the protocols, and has to inform the shop whether a certain action of the user is legitimate ? It seems that the observer can always be programmed (by an adversarial provider) such that it can lead information related to the identity of its accompanying user-module, and hence the person to whom the wallet belongs. If users would recognize such an attempt, it would not be much of a problem since they would complain about it (and the system would be stopped). However, any unnoticeable information that flows from the observer to e.g the shop (or vice versa) that is not specified by the protocol can greatly compromise the user's privacy, in fact to such an extent that there is no benefit over using a system with temper-resistant user-modules (i.e., no privacy guarantee) in the first place. An example of such information is a random challenge that the shop sends to the wallet: if the observer gets to know it, the shop can encode compromising information in it (using an encoding recognizable by the observers) without the user being aware of it (inflow). Vice versa, the observer could try to secretly encode the identity of its owner into the information sent to e.g the shop (outflow), which usually will be an even more serious threat to the privacy of the users.

It may be somewhat of a revelation that there is no impasse at all. As a necessary (but not sufficient) requirement, the observer must thereto obviously be incorporated in the user-module in such a way that any message it sends to the outside world has to pass through the user module, thereby enabling the user-module to verify (and moderate) these messages. In this way, the user-module can recognize attempts of the observer to leak information (outflow), and vice versa. However, it should not be able to moderate to such an extent that it can authorize transactions by itself. Using special cryptographic protocols, all the requirements concerning security can be satisfied, as well as those related to privacy. In particular, protocols can be constructed such that there is no (undetectable by the user-module) inflow and outflow. This implies for example that all random numbers chosen in the protocol by the observer or the outside party (i.e. the shop) are moderated by the user-module before they are sent through.

One more important point to notice here is that an observer could also be used to trace the users transactions at a later time, since it can keep a record of all transactions in which it participates. However, this requires that the Bank (or whoever is doing the tracing) must be able to obtain the observer and analyze it. Also, not all types of observers can by used to trace transaction. In fact, Brands and Ferguson both claimed that they can incorporate observers into their schemes and still retain untraceability of the users' transactions, even if the observer used in the transactions has been obtained and can be analyzed.

3.6 Transferability :

There is another feature of paper cash that is difficult to implement which is transferability. A system is called transferable if users can transfer the coins to other users to use without the need of intervention from the Bank.

Those kind of systems have received little attention in academic literature or probably because it is difficult to devise a good scheme. Any transferable system must have the property that the coins will grow in size because each time a user transfers a coin to another user, the coin must be added some more information about the new user while still has to keep the old information. Thus, it is impossible to have unlimited number of transfers like paper cash has.

The more important point is that it is really difficult to prevent the impact of double spending in the system because multiple spending will not be discovered until the last person who owns that coin actually goes to the bank and deposits the coin.

Moreover, until the coin is deposited, the only information available to the Bank is the identity of the individual who originally withdrew the coin. Any other transactions involving that withdrawal can only be reconstructed with the cooperation of each consecutive spender of that coin. In fact, this scenario is exactly like paper cash in the sense of money laundering and tax evasion : no records of the transactions are available.

3.7 Divisibility

Suppose that Alice is enrolled in a non-transferable, off-line cash system, and she wants to purchase an item from Bob that costs, say, $4.99. If she happens to have electronic coins whose values add up to exactly $4.99 then she simply spends these coins. However, unless Alice has stored a large reserve of coins of each possible denomination, it is unlikely that she will have the exact change for most purchases. She may not wish to keep such a large reserve of coins on hand for the some of the same reasons that one doesn't carry around a large amount of cash: loss of interest and fear of the cash being stolen or lost. Another option is for Alice to withdraw a coin of the exact amount for each payment, but that requires interaction with the Bank, making the payment on-line from her point of view. A third option is for Bob to pay Alice the difference between her payment and the $4.99 purchase price. This puts the burden of having an exact payment on Bob, and also requires Alice to contact the Bank to deposit the "change."

A solution to Alice's dilemma is to use divisible coins: coins that can be "divided" into pieces whose total value is equal to the value of the original coin. This allows exact off-line payments to be made without the need to store a supply of coins of different denominations. Paper cash is obviously not divisible, but lack of divisibility is not as much of an inconvenience with paper cash because it is transferable. Coins that are received in one payment can be used again in the next payment, so the supply of different denominations is partially replenished with each transaction. (Imagine how quickly a cashier would run out of change if paper cash were not transferable and each payment was put in a separate bin set aside for the next bank deposit!)

Three divisible off-line cash schemes have been proposed, but at a cost of a longer transaction time and additional storage. Eng and Okamoto's divisible scheme is based on the "cut and choose" method. Okamoto is much more efficient and is based on Brands' scheme but will also work on Ferguson's scheme. Okamoto and Ohta is the most efficient of the three, but also the most complicated. It relies on the difficulty of factoring and on the difficulty of computing discrete logarithms.

Before going through a bit more detail about one of these protocol, we need to introduce the Schnorr Algorithms and how it is applied to various aspects of E-cash.

The Schnorr Algorithms

The Schnorr family of algorithms includes an identification procedure and a signature with appendix. These algorithms are based on a zero-knowledge proof of possession of a secret key. Let p and q be large prime numbers with q dividing p - 1. Let g be a generator; that is, an integer between 1 and p such that

If s is an integer (mod q), then the modular exponentiation operation on s is

The inverse operation is called the discrete logarithm function and is denoted

If p and q are properly chosen, then modular exponentiation is a one-way function.

Now suppose we have a line y = mx + b (*) over the field of integers (mod q). A line can be described by giving its slope m and intercept b, but we will "hide" it as follows. Let

Then c and n give us the shadow of the line under f. Knowing c and n doesn't give us the slope or intercept of the line, but it does enable us to determine whether a given point (x, y) is on the line. For if (x, y) satisfies (*), then it must also satisfy the relation

Conversely, any point (x, y) satisfying (**) must be on the line. The relationship (**) can be checked by anyone, since it involves only public quantities. Thus anyone can check whether a given point is on the line, but points on the line can only be generated by someone who knows the secret information.

The basic Schnorr protocol is a zero-knowledge proof that one possesses a given secret quantity m. Let n be the corresponding public quantity. Suppose the prover wants to convince the verifier that she knows m without revealing it. She does this by constructing a line (*) and sending its shadow to the verifier. The slope of the line is taken to be secret quantity m, and the prover chooses the intercept at random, differently for each execution of the protocol. The protocol then proceeds as follows.

Schnorr proof of possession:

1. Alice sends c (and n if necessary) to Bob.
2. Bob sends Alice a "challenge" value of x.
3. Alice responds with the value of y such that (x, y) is on the line.
4. Bob verifies via (**) that (x, y) is on the line.

Bob now knows that he is speaking with someone who can generate points on the line. Thus this party must know the slope of the line, which is the secret quantity m.

An important feature of this protocol is that it can be performed only once per line. For if he knows any two points (x0, y0) and (x_i, y₁) on the line, the verifier can compute the slope of the line using the familiar "rise over the run" formula

and this slope is the secret quantity m. That is why a new intercept must be generated each time. We call this the two-points-on-a-line principle. This feature will be useful for electronic cash protocols, since we want to define a spending procedure which reveals nothing of a secret key if used once per coin, but reveals the key if a coin is spent twice.

Divisible schemes :

All three of the schemes mentioned above are based on one common principle. Each coin of worth w is associated with a tree of (1 + log w) levels and w leaves. The tree can be thought of as a collection of w paths of length (1 + log w), each originating from the root and terminating in a leaf. We call these routes

Each node of the tree represents a certain denomination. The root node is assigned a monetary value of w, and the value of all other nodes is found by halving the value of the node's parent. With this tree, we will show that for a single coin of worth w, it will be possible for a customer to engage in several transactions, such that the sum total of the amounts of each transaction is less than of equal to w.

We can think of each mode as being represented by a line, in such a way so that the consumer's identity is encoded in the line's parameters, and the lines of nodes belonging to the same route are related in some way. A node becomes used when the consumer reveals a point on the node's corresponding line and some information about the line's ancestor nodes. During each payment, a subset of nodes (actually, the forest of the tree) will become used; in particular, a set of previously unused/unspent nodes whose values sum up to the denomination being spent. After several transactions have occurred, in which parts of the same coin are spent, a collection of these used nodes will result.

Divisibility can then be implemented under the following invariant :

There is at most one "used" node on any route

Having at most one used node on any route implies that the set of transactions involving the coin so far is legitimate and vice versa. Violation of spending rules will result in violation of this invariant. If the invariant is not upheld, then there are at least two used nodes along some route, and the defining line equation of one of these nodes can be recovered. Note that in our scheme, this also includes the case when the same node has been spent twice (as we will make use of distinct challenges to obtain two distinct points). Here, detection as well as identification of the perpetrator, will ensue.

More specifically, in the Eng/Okamoto and Okamoto schemes, each user has a secret value, s, which is linked to their identity (uncovering s will uncover their identity, but not vice-versa.) Each node i is assigned a secret value, t_i. Hence, each node i corresponds to a line

When a payment is made using a particular node n, t_i will be revealed for all nodes i that are ancestors of node n. Then the payee sends a challenge x_i and the payer responds with

If someone tries to over-spend a coin, then two nodes in the same path will be used. Suppose that nodes n and m are in the same path, and node n is farther from the root on this path. Spending node n will reveal t_m, since node m is an ancestor of node n. Now if node m is also spent, then the response to a challenge x_i will be y₁ = s.x_i + t_m. But t_m was revealed when t_n was spent, so s.x_i and hence s will be revealed. Therefore, spending two nodes in the same path will reveal the identity of the over-spender. The Okamoto/Ohta divisible scheme also uses a binary tree with the same rules for using nodes to prevent multiple and over-spending, but when nodes are used improperly, a different technique is used to determine the identity of the spender. Instead of hiding the user's identifying secret in a line for which a point is revealed when a coin is spent, the user's identifying secret is hidden in the factorization of an RSA modulus. Spending the same node twice, or spending two nodes on the same path will provide enough information for the Bank to factor the modulus (which is part of the coin) and then compute the user's secret identifying information.

Although these three divisible schemes are untraceable, payments made from the same initial coin may be "linked" to each other, meaning that it is possible to tell if two payments came from the same coin and hence the same person. This does not reveal the payer's identity if both payments are valid (follow the rules above), but revealing the payer's identity for one purchase would reveal that payer's identity for all other purchases made from the same initial coin.

These are three examples of off-line cash schemes that have divisible coins. Although providing divisibility complicates the protocol, it can be accomplished without forfeiting untraceability or the ability to detect improper spenders. The most efficient divisible scheme has a transaction time and required memory per coin proportional to the logarithm of N, where N is the total coin value divided by the value of the minimum divisible unit. More improvements in the efficiency of divisible schemes are expected, since the most recent improvement was just presented in 1995.

VI. Practical Ecash systems being developed

4.1.1 SET

Currently there are no standards for the security of digital payments. The well-known SET (Secure Electronic Transaction) standard for credit cards does not apply to the electronic cash. On June 2^nd, 1997, MasterCard International and Visa International announced the publication of SET 1.0, an open industry protocol similar to the existing SET, that details how payment card transactions on the Internet and other open networks will be secured using encryption technology and digital identification. SET 1.0 is the result of almost a year of continuous testing and user feedback of the specification published by the two companies in June 1996. The SET specification requires the providers of electronic cash to use public key cryptography from RSA Data Security, which may contradict the antimonopoly laws.

Participants in the SET development effort along with Visa and MasterCard include: CertCo, GlobeSet, GTE, IBM, Microsoft, Netscape Communications Corp., RSA Data Security, SAIC, SPYRUS, Terisa Systems, VeriSign and VeriFone.

American Express, Diners Club, JCB and NOVUS Services strongly support the release of the SET 1.0 specification, and intend to offer SET-compliant solutions in the future.

4.1.2 Regulation E

The only regulation currently applicable to e-cash is Regulation E. Regulation E is the rule governing electronic funds transfers. It is intended as a consumer protection rule to help guard consumers against losing money from errors or fraud in electronic funds transfers. It requires written advance authorization for arrangements to move money electronically, written receipts for every transfer, a written periodic statement, giving the consumer the right to challenge any electronic funds transfer for a period of 30 days from when they get their statement. Financial institutions offering EFT have a duty to investigate any challenges and respond within a short time (usually 10 days).

4.2 Players in the game.

DigiCash:

DigiCash is the recognized leader in the field of anonymous transactions, founded by David Chaum. The use of the "blinding coin" technique developed and patented by Chaum allows the payer to acquire digital cash with a unique serial number from a bank without allowing the bank to create a record of the coin's serial number. Despite the bank's ignorance of the serial number, the number's uniqueness helps ensure that Alice cannot spend it twice. Unlike the methods currently used by other companies, however, a bank issuing a blinded coin does not know the true serial number of the coin at the time the bank issues it by affixing its digital signature to the "blinded" number. All that the bank knows is the denomination of the coin. The payer stays completely anonymous, as long as there is a sufficiently large volume of coins in circulation such that purchase and use of the coins by any particular individual does not stand out.

On October 23, 1995, Mark Twain Bank of St. Louis, Missouri licensed the DigiCash software and became the world's first financial institution to issue blinded digital coins backed by value. Ecash is also supported by EUnet of Finland, Deutsche Bank, Advance Bank in Australia and Nomura Research Institute in Japan.

CyberCash:

CyberCash, one of the main providers of the electronic money, is headed by a team of people quite known in the area of cryptography and electronic transactions. The two most prominent figures are Bill Melton, president, the inventor of the Verifone system that handles the credit card transactions between merchants and banks and Jim Bidzos (principle), president of RSA.

CyberCash introduced the Internet analogies of credit and debit card payments over the last two years. These schemes use the RSA encryption to send the customer's credit (or debit) card number over http to merchant, who forwards it then to the CyberCash server for decryption. The CyberCash server must link the buyer and the seller, so no parties in the transaction preserve their anonymity.

The most recent program introduced by CyberCash is CyberCoin, introduced March 1997, which is still much closer to a debit card then to electronic money. CyberCoin introduces a limit of $20 per transaction, and a customer can use up to $80 per month. Typical purchases will initially include business research, newspaper articles, pay-to-view or pay-to-play transactions. To receive cash, you have to be a merchant and pay a per-transaction fee to the bank.

The CyberCoin scheme uses 768 - 1024-bit public-private key RSA encryption with 56 bit Digital Electronic Signatures. As in the other schemes by CyberCash, the bank is informed of the buyer's and seller's identity.

NetCash by NetBank:

NetCash operates through e-mail. After receiving customers money, the bank issues a coin of corresponding denomination and sends it to the customer. The coin itself is a plain text 15 letter alphanumeric word. The customer then can send the coin to the merchant, again through e-mail, and the merchant then verifies it with the bank. If the coin is in the list of outstanding coins and the denomination of the coin corresponds to the sum of money requested by the merchant, bank approves the transaction and credits the merchant's account. The bank encourages it's customers to use PGP.

Since the bank can keep records on who the coin was issued to, this scheme does not guarantee the payer's anonymity. Other then that, NetCash is a complete analogue of the usual cash: it does not bear any information about the owner, it cannot be recovered if lost and it can be transferable (if merchant trusts the customer and chooses not to verify the coin with the bank).

First Virtual:

Although considered to be a "digital money" provider, First Virtual actually works as a third party trusted to charge the credit card of the user. This way, credit card number is not transferred over the Internet, and the seller knows the buyer's PIN, but does not know the credit card number. Also, the merchant is informed of the buyer's name as it appears on the FV application by the First Virtual for practically no reason. This system can be hardly considered secure, since all confirmations are done by e-mail without using any encryption and the buyer's PIN is transferred over the http unencrypted. Since e-mail can be very easily forged and http packets can be intercepted, the only thing stopping mass fraud in FV scheme is that the only entity sold by it's companies is information, and it is sold quite cheaply.

V. Social issues related to E-Cash

5.1 The potential for illicit activities.

The ways digital money can be used for the illicit activities are innumerable: it may facilitate money laundering, tax evasion, and may allow international transactions prohibited otherwise. The advantage of digital money over the paper money for these purposes are quite obvious: currently hurdling a suitcase of dollar bills over the border is a risky task. However, with digital cash the same thing can be done almost instantaneously with a use of an old 386 computer and a phone plug.

So, we would like to be able to have some records of the financial activity in digital cash.

5.2 The potential for collecting dossiers on individuals.

Currently, there is already a lot of information available for profiling on any individual's buying habits: full information on our credit card purchases is available to credit card companies, and all our checking account transactions are known to our banks. In fact, this information is already used for making profiles on individuals: many banks send you the advertisements of there services based on the information they have on your financial situation and credit cards send you advertisements on providers of goods and services similar to the ones you buy. Also, banks and credit card companies use profiles of their customers to prevent fraudulent activities.

If digital money will be used for transactions that would normally be credit card transactions or check transactions, the amount of information available for profiling would not change. If it will take place of the cash transactions, the amount of the information on individual's buying habits will be somewhat increased, and, in fact, almost complete.

At this point, it looks like anonymous e-cash will certainly take place in some transactions that are cash transactions today just because of the disadvantages of hard cash. Cash is bulky and hard to handle. It has been estimated that moving hard cash around costs US money handlers ~$60 million dollars a year.

The main threat, however, is that by the nature of the Internet, and, particularly, WWW, we can expect that the vast majority of the goods purchased would be information, from news articles to opinion pieces to professional information. The possibility of creating detailed dossiers on individual's informational preferences would be unprecedented, and totally unacceptable.

5.3 Meeting both goals

The nature of these two requirements is completely contradictory. There is a possible compromise between them.

The reality is that all financial institutions in the world, and especially banks, already are subjects to very strict government regulations and are very easy targets for more regulations. Thus, in order to prevent collecting detailed information on people using digital cash, we need to consider only the schemes where the identity of the payer is unknown to the bank.

Luckily, this requirement does not contradict the need to prevent illicit financial activities. If the payer is anonymous, but payee (Bob) is not, the bank knows who Bob is and how much money and when he has received, and it has enough information to comply with the regulations prohibiting money laundering and tax evasion.

This, in fact, means that in order for e-cash to be safe while keeping the anonymity of the payer, we would need to sacrifice the transferability of digital money. For example, let's consider the possibilities for money laundering if the digital money is transferable and the payer is anonymous.

Let's consider a typical money laundering situation as it would happen in the digital money world. Let's say that Trudy, a drug dealer, received some income from illegal sources in electronic cash. Just as with paper money, Trudy cannot go to the bank and deposit the money, since in most countries banks must notify the authorities upon receiving a deposits of large sums in cash. Trudy cannot afford this to happen, since she cannot justify this income, and she is forced to use the money launder, Bob. The thing is that Bob has a big Internet shop with a large money flow, and he can justify receiving large sums of money in cash as an income from his shop. He would be willing to take Trudy's "dirty" money, declare it as an income from his shop, making it "clean", and return the "clean" money (minus certain percentage for his services) to Trudy.

If the money were not transferable, Trudy wouldn't be able to give her "dirty" money to Bob without declaring them to the bank first, which would make money laundering impossible. If, however, digital money is transferable, money laundering is not only easier for Bob and Trudy, but it is also much harder for police to stop them. With paper money, police would mark the dirty money and present Bob with the evidence forcing him to tell where he has gotten this money. With digital money, Bob can easily say that he simply has no way to know who gave the money to him, since (remember?) the payer was completely anonymous and he does not even know whether it was a thousand of different customers or just one person.

This is also a good illustration that the digital money offers much more privacy then the paper money. With paper money, the payer has to be present at the time of transaction in person, which, strictly speaking, is not anonymous since most stores today use cameras to record all transactions, the clerk may remember the payer and the money would bear the payer's fingerprints.

VI. Conclusion

This survey has pointed out several aspects that are important about E-cash, which includes the basic definitions, some cryptographical details to help better understanding of the schemes presented later on the survey. Moreover, existing schemes and implementations of real E-cash systems have been discuss. Finally, the social issues related to E-cash were also pointed out.

RSA-public key system is among the most popular techniques used to ensure desirable properties of a E-cash system. This cryptographic system is used to ensure privacy for users of the system, to prevent double spending and token forgery, which are two of the main concerns of the back. Moreover, it can be used for identification shemes. That would help both the bank and the merchant to identify users but still have no idea who the user is as long as the user is honest. There is another algorithm which is applied widely because of its simplicity and efficiency _ Schoor Based algorithm. One of the most popular schemes proposed by Chaum-Fiat-Naor was gone into a bit more details. The reason is that CFN is the first E-cash scheme and quite simple conceptually. CFN motivated many other different schemes. Even if other schemes are not based on RSA, they still have sort of the same idea with CFN. RSA and Schnorr schemes can also be used to achieve more desirable properties of E-cash system such as divisibility.

Token forgery can be prevented in an electronic cash system as long as the cryptography is sound and securely implemented, the secret keys used to sign coins are not compromised, and integrity is maintained on the public keys. However, if there is a security flaw or a key compromise, the anonymity of electronic cash will delay detection of the problem. Even after the existence of a compromise is detected, the Bank will not be able to distinguish its own valid coins from forged ones. Since there is no way to guarantee that the Bank's secret keys will never be compromised, it is important to limit the damage that a compromise could inflict. This could be done by limiting the total value of coins issued with a particular key, but lowering these limits also reduces the anonymity of the system since there is a smaller pool of coins associated with each key.

There is a big trade-off between user's privacy and the detecting of money laundering and tax evasion. If the users are completely anonymous, it is a big concern of the national government on how to prevent those problems. Moreover, privacy makes double spending prevention more difficult, it increases the complexity of system design and the efficiency of (all) the E-cash systems. Another property that we want to have is the transferability of E-cash. But, since electronic coins must grow in size after each transfer, memory requirements and transaction times are also increased. In fact, this feature got little attention from the literature.

In conclusion, the potential risks in electronic commerce are magnified when anonymity is present. Anonymity creates the potential for large sums of counterfeit money to go undetected by preventing identification of forged coins. Anonymity also provides an avenue for laundering money and evading taxes that is difficult to combat without resorting to escrow mechanisms. Anonymity can be provided at varying levels, but increasing the level of anonymity also increases the potential damages. It is necessary to weigh the need for anonymity with these concerns.

References

1. "The Future of Money" ; Business Week, June 12, 1995; page 66
2. "The Competition Heats Up In On-line Banking"; Fortune, June 6, 1995; page 18
3. "Cashless Society Becomes a Reality"; Fortune; June 12, 1995; page 24
4. "How to make a mint: The cryptography of anonymous electronic cash", Cryptology Division, 18, June 1996
5. "Electronic Cash, tokens and Payments in the National Information Infrastructure" 6. "Flood Control on the Information Ocean : Living With Anonymity, Digital Cash, and Distributed Databases", A. Michael Froomkin, Pittsburg Journal of Law and Commerce 395 (1996)
7. "Electronic Cash on the Internet" Stefan Brands, Internet Society Oct 16, 1994
8. "Off-Line Electronic Cash" Based on Secret-Key Certificates.
9. "Untraceable Electronic Cash", by David Chaum, Amos Fiat and Moni Naor, Advances in Cryptology CRYPTO '88, Springer-Verlag, pp. 319-327
10. "Untraceable Off-Line Cash in Wallets with Observers" by Stefan Brands, Advances in Cryptology CRYPTO '93, Springer-Verlag, pp. 302-318 11. "Single Term Off-Line Coins", by Niels Ferguson, Advances in Cryptology-EUROCRYPT '93, Springer-Verlag, pp. 318-328