1.3 Divisibility Rulesmr. Mac's Page

Posted : admin | On 19-04-2021



Anonymous: Fried, Frank got NSA's permission to make this report available.They have offered to make copies available by contacting them at<21stCen@ffhsj.com> or (202) 639-7200. See:http://www.ffhsj.com/bancmail/21starch/961017.htm

Received October 31, 1996

Which is a perfect number. As a second example, 1 + 2 + 4 + 8 + 16 = 31 which is prime. Then 31 × 16 = 496 which is a perfect number. Now Euclid gives a rigorous proof of the Proposition and we have the first significant result on perfect numbers. The divisibility rule for is add the outside digits and if the sum matches the sum then it is divisible. The divisibility rule for is if the digits have a sum divisible by, then it is. All even numbers are composite numbers with the exception of. So with these analyses, answer is. 4.2 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. Why Does the Divisibility Rule for 3 Work? The divisibility rule for 3 works because the number represented by each digit can be written as a multiple of 9 plus that digit. 9 is divisible by 3 so if the sum of the digits is divisible by 3, the number itself is too. Here is the proof that 3174 is divisible by 3.

Divisibility rules, or divisibility tests, have a wide range of applications in mathematics (finding factors, determining prime vs. Composite, simplifying fractions, probability, etc.), but are often underemphasized in the classroom or not explored in enough detail for students to retain and use the.

With the Compliments of Thomas P. Vartanian

Fried, Frank, Harris, Schriver & Jacobson

1001 Pennsylvania Avenue, N.W.

Washington, D.C. 20004-2505

Telephone: (202) 639-7200

Laurie Law, Susan Sabett, Jerry Solinas

National Security Agency Office of Information Security Research and Technology

Cryptology Division

18 June 1996

CONTENTS

1.1 Electronic Payment

1.2 Security of Electronic Payments

1.3 Electronic Cash

1.4 Multiple Spending

2.1 Public-Key Cryptographic Tools

2.2 A Simplified Electronic Cash Protocol

2.3 Untraceable Electronic Payments

2.4 A Basic Electronic Cash Protocol

3.1 Including Identifying Information

3.2 Authentication and Signature Techniques

3.3 Summary of Proposed Implementations

4. 1 Transferability

4.2 Divisibility

5.1 Multiple Spending Prevention

5.2 Wallet Observers

5.3 Security Failures

5.4 Restoring Traceability

INTRODUCTION

With the onset of the Information Age, our nation is becoming increasinglydependent upon network communications. Computer-based technology is significantlyimpacting our ability to access, store, and distribute information. Amongthe most important uses of this technology is electronic commerce:performing financial transactions via electronic information exchanged overtelecommunications lines. A key requirement for electronic commerce is thedevelopment of secure and efficient electronic payment systems. The needfor security is highlighted by the rise of the Internet, which promises tobe a leading medium for future electronic commerce.

Electronic payment systems come in many forms including digital checks,debit cards, credit cards, and stored value cards. The usual security featuresfor such systems are privacy (protection from eavesdropping),authenticity (provides user identification and message integrity),and nonrepudiation (prevention of later denying having performed atransaction) .

The type of electronic payment system focused on in this paper is electroniccash. As the name implies, electronic cash is an attempt to constructan electronic payment system modelled after our paper cash system. Papercash has such features as being: portable (easily carried), recognizable(as legal tender) hence readily acceptable, transferable (without involvementof the financial network), untraceable (no record of where money is spent),anonymous (no record of who spent the money) and has the ability to make'change.' The designers of electronic cash focused on preserving the featuresof untraceability and anonymity. Thus, electronic cash is defined to be anelectronic payment system that provides, in addition to the above securityfeatures, the properties of user anonymity and payment untraceability..

In general, electronic cash schemes achieve these security goals via digitalsignatures. They can be considered the digital analog to a handwrittensignature. Digital signatures are based on public key cryptography.In such a cryptosystem, each user has a secret key and a public key. Thesecret key is used to create a digital signature and the public key is neededto verify the digital signature. To tell who has signed the information (alsocalled the message), one must be certain one knows who owns a given publickey. This is the problem of key management, and its solution requires somekind of authentication infrastructure. In addition, the system must haveadequate network and physical security to safeguard the secrecy of the secretkeys.

This report has surveyed the academic literature for cryptographic techniquesfor implementing secure electronic cash systems. Several innovative paymentschemes providing user anonymity and payment untraceability have been found.Although no particular payment system has been thoroughly analyzed, thecryptography itself appears to be sound and to deliver the promised anonymity.

These schemes are far less satisfactory, however, from a law enforcementpoint of view. In particular, the dangers of money laundering and counterfeitingare potentially far more serious than with paper cash. These problems existin any electronic payment system, but they are made much worse by the presenceof anonymity. Indeed, the widespread use of electronic cash would increasethe vulnerability of the national financial system to Information Warfareattacks. We discuss measures to manage these risks; these steps, however,would have the effect of limiting the users' anonymity.

This report is organized in the following manner. Chapter 1 defines the basicconcepts surrounding electronic payment systems and electronic cash. Chapter2 provides the reader with a high level cryptographic description of electroniccash protocols in terms of basic authentication mechanisms. Chapter 3 technicallydescribes specific implementations that have been proposed in the academicliterature. In Chapter 4, the optional features of transferability anddivisibility for off-line electronic cash are presented. Finally, in Chapter5 the security issues associated with electronic cash are discussed.

The authors of this paper wish to acknowledge the following people for theircontribution to this research effort through numerous discussions and reviewof this paper: Kevin Igoe, John Petro, Steve Neal, and Mel Currie.

1. WHAT IS ELECTRONIC CASH?

We begin by carefully defining 'electronic cash.' This term is often appliedto any electronic payment scheme that superficially resembles cash to theuser. In fact, however, electronic cash is a specific kind of electronicpayment scheme, defined by certain cryptographic properties. We now focuson these properties.

1.1 Electronic Payment

The term electronic commerce refers to any financial transaction involvingthe electronic transmission of information. The packets of information beingtransmitted are commonly called electronic tokens. One should notconfuse the token, which is a sequence of bits, with the physical media usedto store and transmit the information.

We will refer to the storage medium as a card since it commonly takesthe form of a wallet-sized card made of plastic or cardboard. (Two obviousexamples are credit cards and ATM cards.) However, the 'card' could alsobe, e.g., a computer memory.

A particular kind of electronic commerce is that of electronic payment.An electronic payment protocol is a series of transactions, at the end ofwhich a payment has been made, using a token issued by a third party. Themost common example is that of credit cards when an electronic approval processis used. Note that our definition implies that neither payer nor payee issuesthe token.l

The electronic payment scenario assumes three kinds of players:2

  • a payer or consumer, whom we will name Alice.
  • a payee, such as a merchant. We will name the payee Bob.
  • a financial network with whom both Alice and Bob have accounts. We will informally refer to the financial network as the Bank.

__________

1 In this sense, electronic payment differs from such systemsas prepaid phone cards and subway fare cards, where the token is issued bythe payee.

2 In 4.1, we will generalize this scenario when we discuss transfers.

1.2 Security of Electronic Payments

With the rise of telecommunications and the Internet, it is increasinglythe case that electronic commerce takes place using a transmission mediumnot under the control of the financial system. It is therefore necessaryto take steps to insure the security of the messages sent along such a medium.

The necessary security properties are:

  • Privacy, or protection against eavesdropping. This is obviously of importance for transactions involving, e.g., credit card numbers sent on the Internet.
  • User identification, or protection against impersonation. Clearly, any scheme for electronic commerce must require that a user knows with whom she is dealing (if only as an alias or credit card number).
  • Message integrity, or protection against tampering or substitution. One must know that the recipient's copy of the message is the same as what was sent.
  • Nonrepudiation, or protection against later denial of a transaction. This is clearly necessary for electronic commerce, for such things as digital receipts and payments.

The last three properties are collectively referred to asauthenticity.

These security features can be achieved in several ways. The technique thatis gaining widespread use is to employ an authentication infrastructure.In such a setup, privacy is attained by enciphering each message, using aprivate key known only to the sender and recipient. The authenticity featuresare attained via key management, e.g., the system of generating,distributing and storing the users' keys.

Key management is carried out using a certification authority, ora trusted agent who is responsible for confirming a user's identity. Thisis done for each user (including banks) who is issued a digital identitycertificate. The certificate can be used whenever the user wishes toidentify herself to another user. In addition, the certificates make it possibleto set up a private key between users in a secure and authenticated way.This private key is then used to encrypt subsequent messages. This techniquecan be implemented to provide any or all of the above security features.

Although the authentication infrastructure may be separate from theelectronic-commerce setup, its security is an essential component of thesecurity of the electronic-commerce system. Without a trusted certificationauthority and a secure infrastructure, the above four security features cannotbe achieved, and electronic commerce becomes impossible over an untrustedtransmission medium.

We will assume throughout the remainder of this paper that some authenticationinfrastructure is in place, providing the four security features.

1.3 Electronic Cash

We have defined privacy as protection against eavesdropping on one'scommunications. Some privacy advocates such as David Chaum (see [2],[3]),however, define the term far more expansively. To them, genuine 'privacy'implies that one's history of purchases not be available for inspection bybanks and credit card companies (and by extension the government). To achievethis, one needs not just privacy but anonymity. In particular, oneneeds

  • payer anonymity during payment,
  • payment untraceability so that the Bank cannot tell whose money is used in a particular payment.

These features are not available with credit cards. Indeed, the only conventionalpayment system offering it is cash. Thus Chaum and others have introducedelectronic cash (or digital cash), an electronic payment systemwhich offers both features. The sequence of events in an electronic cashpayment is as follows:

  • withdrawal, in which Alice transfers some of her wealth from her Bank account to her card.
  • payment, in which Alice transfers money from her card to Bob's.
  • deposit, in which Bob transfers the money he has received to his Bank account.

(See Figure 1.)

Figure 1. The three types of transactions in a basic electroniccash model.

These procedures can be implemented in either of two ways:

  • On-line payment means that Bob calls the Bank and verifies the validity of Alice's token3 before accepting her payment and delivering his merchandise. (This resembles many of today's credit card transactions.)
  • Off-line payment means that Bob submits Alice's electronic coin for verification and deposit sometime after the payment transaction is completed. (This method resembles how we make small purchases today by personal check.)

Note that with an on-line system, the payment and deposit are not separatesteps. We will refer to on-line cash and off-line cash schemes,omitting the word 'electronic' since there is no danger of confusion withpaper cash.

__________

3 In the context of electronic cash, the token is usually calledan electronic coin.

1.4 Counterfeiting

As in any payment system, there is the potential here for criminal abuse,with the intention either of cheating the financial system or using the paymentmechanism to facilitate some other crime. We will discuss some of these problemsin 5. However, the issue of counterfeiting must be considered here,since the payment protocols contain built-in protections against it.

There are two abuses of an electronic cash system analogous to counterfeitingof physical cash:

  • Token forgery, or creating a valid-looking coin without making a corresponding Bank withdrawal.
  • Multiple spending, or using the same token over again. Since an electronic coin consists of digital information, it is as valid-looking after it has been spent as it was before. (Multiple spending is also commonly called re-spending, double spending, and repeat spending.)

One can deal with counterfeiting by trying to prevent it from happening,or by trying to detect it after the fact in a way that identifiesthe culprit. Prevention clearly is preferable, all other things being equal.

Although it is tempting to imagine electronic cash systems in which thetransmission and storage media are secure, there will certainly be applicationswhere this is not the case. (An obvious example is the Internet, whose usersare notoriously vulnerable to viruses and eavesdropping.) Thus we need techniquesof dealing with counterfeiting other than physical security.

  • To protect against token forgery, one relies on the usual authenticity functions of user identification and message integrity. (Note that the 'user' being identified from the coin is the issuing Bank, not the anonymous spender.)
  • To protect against multiple spending, the Bank maintains a database of spent electronic coins. Coins already in the database are to be rejected for deposit. If the payments are on-line, this will prevent multiple spending. If off-line, the best we can do is to detect when multiple spending has occurred. To protect the payee, it is then necessary to identify the payer. Thus it is necessary to disable the anonymity mechanism in the case of multiple spending.

The features of authenticity, anonymity, and multiple-spender exposure areachieved most conveniently using public-key cryptography. We will discusshow this is done in the next two chapters.

2. A CRYPTOGRAPHIC DESCRIPTION

In this chapter, we give a high-level description of electronic cash protocolsin terms of basic authentication mechanisms. We begin by describing thesemechanisms, which are based on public-key cryptography. We then build upthe protocol gradually for ease of exposition. We start with a simplifiedscheme which provides no anonymity. We then incorporate the paymentuntraceability feature, and finally the payment anonymity property. The resultwill be a complete electronic cash protocol.

2.1 Public-Key Cryptographic Tools

Page

We begin by discussing the basic public-key cryptographic techniques uponwhich the electronic cash implementations are based.

One-Way Functions. A one-way function is a correspondence betweentwo sets which can be computed efficiently in one direction but not the other.In other words, the function phi is one-way if, given s inthe domain of phi, it is easy to compute t = phi(s),but given only t, it is hard to find s. (The elements are typicallynumbers, but could also be, e.g., points on an elliptic curve; see[10].)

Key Pairs. If phi is a one-way function, then a key pairis a pair s, t related in some way via phi. We calls the secret key and t the public key. As thenames imply, each user keeps his secret key to himself and makes his publickey available to all. The secret key remains secret even when the publickey is known, because the one-way property of phi insures thatt cannot be computed from s.

All public-key protocols use key pairs. For this reason, public-key cryptographyis often called asymmetric cryptography. Conventional cryptographyis often called symmetric cryptography, since one can both encryptand decrypt with the private key but do neither without it.

Signature and Identification. In a public key system, a user identifiesherself by proving that she knows her secret key without revealing it. Thisis done by performing some operation using the secret key which anyone cancheck or undo using the public key. This is called identification.If one uses a message as well as one's secret key, one is performing adigital signature on the message. The digital signature plays thesame role as a handwritten signature: identifying the author of the messagein a way which cannot be repudiated, and confirming the integrity of themessage.

Secure Hashing. A hash function is a map from all possiblestrings of bits of any length to a bit string of fixed length. Such functionsare often required to be collision-free: that is, it must becomputationally difficult to find two inputs that hash to the same value.If a hash function is both one-way and collision-free, it is said to be asecure hash.

The most common use of secure hash functions is in digital signatures. Messagesmight come in any size, but a given public-key algorithm requires workingin a set of fixed size. Thus one hashes the message and signs the securehash rather than the message itself. The hash is required to be one-way toprevent signature forgery, i.e., constructing a valid-lookingsignature of a message without using the secret key.4 The hashmust be collision-free to prevent repudiation, i.e., denyinghaving signed one message by producing another message with the same hash.

__________

4 Note that token forgery is not the same thing assignature forgery. Forging the Bank's digital signature without knowingits secret key is one way of committing token forgery, but not the only way.A bank employee or hacker, for instance, could 'borrow' the Bank's secretkey and validly sign a token. This key compromise scenario is discussedin 5.3.

2.2 A Simplified Electronic Cash Protocol

We now present a simplified electronic cash system, without the anonymityfeatures.

PROTOCOL 1:On-line electronic payment.

Withdrawal:

Alice sends a withdrawal request to the Bank.

Bank prepares an electronic coin and digitally signsit.

Bank sends coin to Alice and debits her account.

Payment/Deposit:

Alice gives Bob the coin.

Bob contacts Bank5 and sends coin.

Bank verifies the Bank's digital signature.

Bank verifies that coin has not already been spent.

Bank consults its withdrawal records to confirm Alice'swithdrawal. (optional)

Bank enters coin in spent-coin database.

Bank credits Bob's account and informs Bob.

Bob gives Alice the merchandise.

__________

5 One should keep in mind that the term 'Bank' refers to the financialsystem that issues and clears the coins. For example, the Bank might be acredit card company, or the overall banking system. In the latter case, Aliceand Bob might have separate banks. If that is so, then the 'deposit' procedureis a little more complicated: Bob's bank contacts Alice's bank, 'cashes in'the coin, and puts the money in Bob's account.

PROTOCOL 2:Off-line electronic payment.

Withdrawal:

Alice sends a withdrawal request to the Bank.

Bank prepares an electronic coin and digitally signsit.

Bank sends coin to Alice and debits her account.

Payment:

Alice gives Bob the coin.

Bob verifies the Bank's digital signature.(optional)

Bob gives Alice the merchandise.

Deposit:

Bob sends coin to the Bank.

Bank verifies the Bank's digital signature.

Bank verifies that coin has not already been spent.

Bank consults its withdrawal records to confirm Alice'swithdrawal. (optional)

Bank enters coin in spent-coin database.

Bank credits Bob's account.

The above protocols use digital signatures to achieve authenticity. Theauthenticity features could have been achieved in other ways, but we needto use digital signatures to allow for the anonymity mechanisms we are aboutto add.

2.3 Untraceable Electronic Payments

In this section, we modify the above protocols to include payment untraceability.For this, it is necessary that the Bank not be able to link a specific withdrawalwith a specific deposit.6 This is accomplished using a specialkind of digital signature called a blind signature.

We will give examples of blind signatures in 3.2, but for now we give onlya high-level description. In the withdrawal step, the user changes the messageto be signed using a random quantity. This step is called 'blinding' thecoin, and the random quantity is called the blinding factor. The Banksigns this random-looking text, and the user removes the blinding factor.The user now has a legitimate electronic coin signed by the Bank. The Bankwill see this coin when it is submitted for deposit, but will not know whowithdrew it since the random blinding factors are unknown to the Bank.(Obviously, it will no longer be possible to do the checking of the withdrawalrecords that was an optional step in the first two protocols.)

Note that the Bank does not know what it is signing in the withdrawal step.This introduces the possibility that the Bank might be signing somethingother than what it is intending to sign. To prevent this, we specify thata Bank's digital signature by a given secret key is valid only as authorizinga withdrawal of a fixed amount. For example, the Bank could have one keyfor a $10 withdrawal, another for a $50 withdrawal, and so on.7

_________

6 In order to achieve either anonymity feature, it is of coursenecessary that the pool of electronic coins be a large one.

7 0ne could also broaden the concept of 'blind signature' to includeinteractive protocols where both parties contribute random elements to themessage to be signed. An example of this is the 'randomized blind signature'occurring in the Ferguson scheme discussed in 3.3.

PROTOCOL 3: Untraceable On-line electronic payment.

Withdrawal:

Alice creates an electronic coin and blinds it.

Alice sends the blinded coin to the Bank with a withdrawalrequest.

Bank digitally signs the blinded coin.

Bank sends the signed blinded coin to Alice and debitsher account.

Alice unblinds the signed coin.

Payment/Deposit:

Alice gives Bob the coin.

Bob contacts Bank and sends coin.

Bank verifies the Bank's digital signature.

Bank verifies that coin has not already been spent.

Bank enters coin in spent-coin database.

Bank credits Bob's account and informs Bob.

Bob gives Alice the merchandise.

PROTOCOL 4:Untraceable Off-line electronic payment.

Withdrawal:

Alice creates an electronic coin and blinds it.

Alice sends the blinded coin to the Bank with a withdrawalrequest.

Bank digitally signs the blinded coin.

Bank sends the signed blinded coin to Alice and debitsher account.

Alice unblinds the signed coin.

Payment:

Alice gives Bob the coin.

Bob verifies the Bank's digital signature.(optional)

Bob gives Alice the merchandise.

Deposit:

Bob sends coin to the Bank.

Bank verifies the Bank's digital signature.

Bank verifies that coin has not already been spent.

Bank enters coin in spent-coin database.

Bank credits Bob's account.

2.4 A Basic Electronic Cash Protocol

We now take the final step and modify our protocols to achieve payment anonymity.The ideal situation (from the point of view of privacy advocates) is thatneither payer nor payee should know the identity of the other. This makesremote transactions using electronic cash totally anonymous: no one knowswhere Alice spends her money and who pays her.

It turns out that this is too much to ask: there is no way in such a scenariofor the consumer to obtain a signed receipt. Thus we are forced to settlefor payer anonymity.

If the payment is to be on-line, we can use Protocol 3 (implemented, of course,to allow for payer anonymity). In the off-line case, however, a new problemarises. If a merchant tries to deposit a previously spent coin, he will beturned down by the Bank, but neither will know who the multiple spender wassince she was anonymous. Thus it is necessary for the Bank to be able toidentify a multiple spender. This feature, however, should preserve anonymityfor law-abiding users.

The solution is for the payment step to require the payer to have, in additionto her electronic coin, some sort of identifying information whichshe is to share with the payee. This information is split in such a way thatany one piece reveals nothing about Alice's identity, but any two piecesare sufficient to fully identify her.

This information is created during the withdrawal step. The withdrawal protocolincludes a step in which the Bank verifies that the information is thereand corresponds to Alice and to the particular coin being created. (To preservepayer anonymity, the Bank will not actually see the information, only verifythat it is there.) Alice carries the information along with the coin untilshe 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 sucha protocol, Bob sends Alice a random 'challenge' quantity and, in response,Alice returns a piece of identifying information. (The challenge quantitydetermines which piece she sends.) At the deposit step, the revealed pieceis sent to the Bank along with the coin. If all goes as it should, theidentifying information will never point to Alice. However, should she spendthe coin twice, the Bank will eventually obtain two copies of the same coin,each with a piece of identifying information. Because of the randomness inthe challenge-response protocol, these two pieces will be different. Thusthe Bank will be able to identify her as the multiple spender. Since onlyshe can dispense identifying information, we know that her coin was not copiedand re-spent by someone else.

PROTOCOL 5:Off-line cash.

Withdrawal:

Alice creates an electronic coin, includingidentifying information.

Alice blinds the coin.

Alice sends the blinded coin to the Bank with a withdrawalrequest.

Bank verifies that the identifying information is present.

Bank digitally signs the blinded coin.

Bank sends the signed blinded coin to Alice and debitsher 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 ofidentifying 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-coindatabase.

Bank credits Bob's account.

1.3 Divisibility Rulesmr. Mac

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

3. PROPOSED OFF-LINE IMPLEMENTATIONS

Having described electronic cash in a high-level way, we now wish to describethe specific implementations that have been proposed in the literature. Suchimplementations are for the off-line case; the on-line protocols are justsimplifications of them. The first step is to discuss the various implementationsof the public-key cryptographic tools we have described earlier.

3.1 Including Identifying Information

We must first be more specific about how to include (and access when necessary)the identifying information meant to catch multiple spenders. There are twoways of doing it: the cut-and-choose method and zero-knowledgeproofs.

Cut and Choose. When Alice wishes to make a withdrawal, she firstconstructs and blinds a message consisting of K pairs of numbers,where K is large enough that an event with probability2-K will never happen in practice. These numbers have theproperty that one can identify Alice given both pieces of a pair, but unmatchedpieces are useless. She then obtains signature of this blinded message fromthe Bank. (This is done in such a way that the Bank can check that theK pairs of numbers are present and have the required properties, despitethe blinding.)

When Alice spends her coins with Bob, his challenge to her is a string ofK random bits. For each bit, Alice sends the appropriate piece ofthe corresponding pair. For example, if the bit string starts 0110. . .,then Alice sends the first piece of the first pair, the second piece of thesecond pair, the second piece of the third pair, the first piece of the fourthpair, etc. When Bob deposits the coin at the Bank, he sends on these Kpieces.

If Alice re-spends her coin, she is challenged a second time. Since eachchallenge is a random bit string, the new challenge is bound to disagreewith the old one in at least one bit. Thus Alice will have to reveal theother piece of the corresponding pair. When the Bank receives the coin asecond time, it takes the two pieces and combines them to reveal Alice'sidentity.

Although conceptually simple, this scheme is not very efficient, since eachcoin must be accompanied by 2K large numbers.

Zero-Knowledge Proofs. The term zero-knowledge proof refersto any protocol in public-key cryptography that proves knowledge of somequantity without revealing it (or making it any easier to find it). In thiscase, Alice creates a key pair such that the secret key points to her identity.(This is done in such a way the Bank can check via the public key that thesecret key in fact reveals her identity, despite the blinding.) Inthe payment protocol, she gives Bob the public key as part of the electroniccoin. She then proves to Bob via a zero-knowledge proof that she possessesthe corresponding secret key. If she responds to two distinct challenges,the identifying information can be put together to reveal the secret keyand so her identity.

3.2 Authentication and Signature Techniques

Our next step is to describe the digital signatures that have been used inthe implementations of the above protocols, and the techniques that havebeen used to include identifying information.

There are two kinds of digital signatures, and both kinds appear in electroniccash protocols. Suppose the signer has a key pair and a message Mto be signed.

  • Digital Signature with Message Recovery. For this kind of signature, we have a signing function SSK using the secret key SK, and a verifying function VPK using the public key PK. These functions are inverses, so that

(*) VPK(SSK (M)) = M

  • The function VPK is easy to implement, while SSK is easy if one knows SK and difficult otherwise. Thus SSK is said to have a trapdoor, or secret quantity that makes it possible to perform a cryptographic computation which is otherwise infeasible. The function VPK is called a trapdoor one-way function, since it is a one-way function to anyone who does not know the trapdoor.
  • In this kind of scheme, the verifier receives the signed message SSK (M) but not the original message text. The verifier then applies the verification function VPK. This step both verifies the identity of the signer and, by (*), recovers the message text.
  • Digital Signature with Appendix. In this kind of signature, the signer performs an operation on the message using his own secret key. The result is taken to be the signature of the message; it is sent along as an appendix to the message text. The verifier checks an equation involving the message, the appendix, and the signer's public key. If the equation checks, the verifier knows that the signer's secret key was used in generating the signature.

We now give specific algorithms.

RSA Signatures. The most well-known signature with message recoveryis the RSA signature. Let N be a hard-to-factor integer. The secretsignature key s and the public verification key v are exponentswith the property that

Msv = M (mod N)

for all messages M. Given v, it is easy to find s ifone knows the factors of N but difficult otherwise. Thus the'vth power (mod N)' map is a trapdoor one-way function.The signature of M is

1.3 Divisibility Rulesmr. Mac's Page Printable

C := Ms (mod N);

to recover the message (and verify the signature), one computes

M := Cv (mod N).

Blind RSA Signatures. The above scheme is easily blinded. Supposethat Alice wants the Bank to produce a blind signature of the messageM. She generates a random number r and sends

rv . M (mod N)

to the Bank to sign. The Bank does so, returning

r . Ms (mod N)

Alice then divides this result by r. The result isMs (mod N), the Bank's signature of M, eventhough the Bank has never seen M.

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

gq = 1 (mod p).

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

phi : s -> gs (mod p).

The inverse operation is called the discrete logarithm function andis denoted

loggt <- t.

If p and q are properly chosen, then modular exponentiationis a one-way function. That is, it is computationally infeasible to finda discrete logarithm.

Rulesmr.

Now suppose we have a line

(**) y = mx + b

over the field of integers (mod q). A line can be described by givingits slope m and intercept b, but we will 'hide' it as follows.Let

c = gb (mod p),

n = gm (mod p).

Then c and n give us the 'shadow' of the line under phi.Knowing c and n doesn't give us the slope or intercept of theline, 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 satisfythe relation

(***) gy = nx . c(mod p).

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

The basic Schnorr protocol is a zero-knowledge proof that one possesses agiven secret quantity m. Let n be the corresponding publicquantity. Suppose one user (the 'prover') wants to convince another (the'verifier') that she knows m without revealing it. She does this by constructinga line (**) and sending its shadow to the verifier. The slope of the lineis taken to be secret quantity m, and the prover chooses the interceptat random, differently for each execution of the protocol. The protocol thenproceeds as follows.

Schnorr proof of possession:

1. Alice sends c (and n if necessary) toBob.

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 theline.

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

An important feature of this protocol is that it can be performed only onceper line. For if he knows any two points (xo,yo) and (x1, y1) onthe line, the verifier can compute the slope of the line using the familiar'rise over the run' formula

m = yo - y1 / x1 -x1 (mod q),

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

1.3 Divisibility Rulesmr. Mac's Page Sheet

Schnorr identification. The above protocol can be used for identificationof users in a network. Each user is issued a key pair, and each public keyis advertised as belonging to a given user. To identify herself, a user needsonly prove that she knows her secret key. This can be done using the abovezero-knowledge proof, since her public key is linked with her identity.

Schnorr Signature. It is easy to convert the Schnorr identificationprotocol to produce a digital signature scheme. Rather than receiving a challengefrom an on-line verifier, the signer simply takes x to be a securehash of the message and of the shadow of the line. This proves knowledgeof his secret key in a way that links his key pair to the message.

Blind Schnorr Signature. Suppose that Alice wants to obtain a blindSchnorr signature for her coin, which she will spend with Bob. Alice generatesrandom quantities (mod q) which describe a change of variables. Thischange of variables replaces the Bank's hidden line with another line, andthe point on the Bank's line with a point on the new line. When Bob verifiesthe Bank's signature, he is checking the new point on the new line. The twolines have the same slope, so that the Bank's signature will remain valid.When the Bank receives the coin for deposit, it will see the protocol implementedon the new line, but it will not be able to link the coin with Alice's withdrawalsince only Alice knows the change of variables relating the two lines.

Chaum-Pederson Signature. A variant of Schnorr's signature schemegiven in [6] is used in electronic cash protocols. This modified scheme isa kind of 'double Schnorr' scheme. It involves a single line and point butuses two shadows. This signature scheme can be blinded in a way similar tothe ordinary Schnorr signature.

Implementations of the Schnorr Protocols. We have described the Schnorralgorithms in terms of integers modulo a prime p. The protocols, however,work in any setting in which the analogue of the discrete logarithm problemis difficult. An important example is that of elliptic curves (see[10]). Elliptic curve based protocols are much faster, and require thetransmission of far less data, than non-elliptic protocols giving the samelevel of security.

3.3 Summary of Proposed Implementations

We can now present summaries of the main off-line cash schemes from the academicliterature. There are three: those of Chaum-Fiat-Naor [4], Brands [1], andFerguson [9].

Chaum-Fiat-Naor. This was the first electronic cash scheme, and isthe simplest conceptually. The Bank creates an electronic coin by performinga blind RSA signature to Alice's withdrawal request, after having verifiedinteractively that Alice has included her identifying information on thecoin. The prevention of multiple spending is accomplished by the cut-and-choosemethod. For this reason, this scheme is relatively inefficient.

Brands. Brands' scheme is Schnorr-based.8 Indeed, a Schnorrprotocol is used twice: at withdrawal, the Bank performs a blindChaum-Pederson signature, and then Alice performs a Schnorr possession proofas the challenge-and-response part of the spending protocol.

The withdrawal step produces a coin which contains the Bank's signature,authenticating both Alice's identifying information and the shadow of theline to be used for the possession proof. This commits Alice to using thatparticular line in the spending step. If she re-spends the coin, she mustuse the same line twice, enabling the Bank to identify her.

The Brands scheme is considered by many to be the best of the three, fortwo reasons. First, it avoids the awkward cut-and-choose technique. Second,it is based only on the Schnorr protocols, and so it can be implemented invarious settings such as elliptic curves.

Ferguson. Ferguson's scheme is RSA-based like Chaum-Fiat-Naor, butit uses the 'two-points-on-a-line' principle like Brands. The signature ituses is not the blind RSA signature as described above, but a variant calleda randomized blind RSA signature. The ordinary blind RSA scheme hasthe drawback that the Bank has absolutely no idea what it is signing. Asmentioned above, this is not a problem in the cut-and-choose case, but inthis case it can allow a payer to defeat the mechanism for identifying multiplespenders. The randomized version avoids this problem by having both Aliceand the Bank contribute random data to the message. The Bank still doesn'tknow what it is signing, but it knows that the data was not chosen maliciously.

The rest of the protocol is conceptually similar to Brands' scheme. The messageto be signed by the Bank contains, in addition to the random data, the shadowof a line whose slope and intercept reveal Alice's identity. During payment,Alice reveals a point on this line; if she does so twice, the Bank can identifyher.

Although Ferguson's scheme avoids the cut-and-choose technique, it is themost complicated of the three (due largely to the randomized blind RSAsignature). Moreover, it cannot be implemented over elliptic curves sinceit is RSA-based.

__________

8 For ease of exposition, we give a simplified account of Brands'protocol.

4. OPTIONAL FEATURES OF OFF-LINE CASH

Much of the recent literature on off-line cash has focused on adding featuresto make it more convenient to use. In this chapter we will discuss two ofthese features.

4.1 Transferability

Transferability is a feature of paper cash that allows a user to spend acoin that he has just received in a payment without having to contact theBank in between. We refer to a payment as a transfer if the payeecan use the received coin in a subsequent payment. A payment system istransferable if it allows at least one transfer per coin. Figure 2shows a maximum length path of a coin in a system which allows two transfers.The final payment is not considered a transfer because it must be depositedby the payee. Transferability would be a convenient feature for an off-linecash system because it requires less interaction with the Bank. (A transferableelectronic cash system is off-line by definition, since on-line systems requirecommunication with the Bank during each payment.)

Figure 2. A maximum length path of a coin in a system whichallows 2 transfers per coin.

Transferable systems have received little attention in academic literature.The schemes presented in 3.3 are not transferable because the payee cannotuse a received coin in another payment - his only options are to depositor to exchange it for new coins at the Bank. Any transferable electroniccash system has the property that the coin must 'grow in size' (i.e., accumulatemore bits) each time it is spent. This is because the coin must containinformation about every person who has spent it so that the Bank maintainsthe ability to identify multiple spenders. (See [5].) This growth makes itimpossible to allow an unlimited number of transfers. The maximum numberof transfers allowed in any given system will be limited by the allowablesize of the coin.

There are other concerns with any transferable electronic cash system, evenif the number of transfers per coin is limited, and we remove the anonymityproperty. Until the coin is deposited, the only information available tothe Bank is the identity of the individual who originally withdrew the coin.Any other transactions involving that withdrawal can only be reconstructedwith the cooperation of each consecutive spender of that coin. This posesthe same problems that paper cash poses for detecting money laundering andtax evasion: no records of the transactions are available.

In addition, each transfer delays detection of re-spent or forged coins.Multiple spending will not be noticed until two copies of the same coin areeventually deposited. By then it may be too late to catch the culprit, andmany users may have accepted counterfeit coins. Therefore, detection of multiplespending after the fact may not provide a satisfactory solution for atransferable electronic cash system. A transferable system may need to relyon physical security to prevent multiple spending. (See 5.1.)

4.2 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 shehappens to have electronic coins whose values add up to exactly $4.99 thenshe simply spends these coins. However, unless Alice has stored a large reserveof coins of each possible denomination, it is unlikely that she will havethe exact change for most purchases. She may not wish to keep such a largereserve of coins on hand for the some of the same reasons that one doesn'tcarry around a large amount of cash: loss of interest and fear of the cashbeing stolen or lost. Another option is for Alice to withdraw a coin of theexact 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 forBob to pay Alice the difference between her payment and the $4.99 purchaseprice. This puts the burden of having an exact payment on Bob, and also requiresAlice to contact the Bank to deposit the 'change.'

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

Three divisible off-line cash schemes have been proposed, but at a cost ofa longer transaction time and additional storage. Eng and Okamoto's divisiblescheme [7] is based on the 'cut and choose' method. Okamoto [11] is muchmore efficient and is based on Brands' scheme but will also work on Ferguson'sscheme. Okamoto and Ohta [12] is the most efficient of the three, but alsothe most complicated. It relies on the difficulty of factoring and on thedifficulty of computing discrete logarithms.

Figure 3. A binary tree for a divisible coin worth $4.00, witha minimum unit of $1.00. A $3.00 payment can be made by spending the shadednodes. Node 1I cannot be used in a subsequent payment because it is an ancestorof nodes 2 and 6. Nodes 4 and 5 cannot be used because they are descendantsof node 2. Node 3 cannot be used because it is an ancestor of node 6. Nodes2 and 6 cannot be used more than once, so node 7 is the only node which canbe spent in a subsequent payment.

All three of these schemes work by associating a binary tree with each coinof value $w. (See Figure 3). Each node is assigned a monetary valueas follows: the unique root node (the node at level 0) has value $w,the two nodes at level 1 each have value $w/2, the four nodes at level2 each have value $w/4, etc. Therefore, if w =21, then the tree has l+ 1 levels, and the nodesat level j each have value $w/2j. Theleaves of the tree are the nodes at level l, and have the minimumunit of value.

To spend the entire amount of value $w, the root node is used. Amountsless than $w can be spent by spending a set of nodes whose valuesadd up to the desired amount.

Initially, any whole dollar amount of up to $w can be spent. Subsequentpayments are made according to the following rules:

1. Once a node is used, all its descendant andancestor9 nodes cannot be used.

2. No node can be used more than once.

These two rules insure that no more than one node is used on any path fromthe root to a leaf. If these two rules are observed, then it will be impossibleto spend more than the original value of the coin. If either of these rulesare broken, then two nodes on the same path are used, and the informationin the two corresponding payments can be combined to reveal the identityof the individual that over-spent in the same way that the identity of amultiple spender is revealed.

More specifically, in the Eng/Okamoto and Okamoto schemes, each user hasa secret value, s, which is linked to their identity (uncoverings will uncover their identity, but not vice-versa.) Each node iis assigned a secret value, ti. Hence, each node icorresponds to a line

y = sx + ti

When a payment is made using a particular node n,ti will be revealed for all nodes ithat areancestors of node n. Then the payee sends a challengexi and the payer responds with

y1 = sx1 + tn .

This reveals a point (x1, y1) on theline y = sx + tn, but does not reveal theline itself. If the same node is spent twice, then responses to two independentchallenges, x1 and x2, will reveal two pointson the same line: (x1, y1) and(x2, y2). Then the secret value scan be recovered using the two-points-on-a-line principle described in 3.2.

If someone tries to overspend a coin, then two nodes in the same path willbe used. Suppose that nodes n and m are in the same path, andnode n is farther from the root on this path. Spending node nwill reveal tm, since node m is an ancestor of noden. Now if node m is also spent, then the response to a challengex1 will be y1 = sx1+ tm. But tm was revealed whentn was spent, so sx1 and hence swill be revealed. Therefore, spending two nodes in the same path will revealthe identity of the over-spender. The Okamoto/Ohta divisible scheme alsouses a binary tree with the same rules for using nodes to prevent multipleand over-spending, but when nodes are used improperly, a different techniqueis used to determine the identity of the spender. Instead of hiding the user'sidentifying secret in a line for which a point is revealed when a coin isspent, the user's identifying secret is hidden in the factorization of anRSA modulus. Spending the same node twice, or spending two nodes on the samepath will provide enough information for the Bank to factor the modulus (whichis part of the coin) and then compute the user's secret identifying information.

Although these three divisible schemes are untraceable, payments made fromthe same initial coin may be 'linked' to each other, meaning that it is possibleto 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 (followRules 1 and 2, above), but revealing the payer's identity for one purchasewould reveal that payer's identity for all other purchases made from thesame initial coin.

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

__________

9 A descendant of a node n is a node on a path fromnode n to a leaf. An ancestor of node n is a node onthe path from node n to the root node.

5. SECURITY ISSUES

In this section we discuss some issues concerning the security of electroniccash. First, we discuss ways to help prevent multiple spending in off-linesystems, and we describe the concept of wallet observers. We also discussthe consequences of an unexpected failure in the system?s security. Finally,we describe a solution to some of the law enforcement problems that are createdby anonymity.

5.1 Multiple Spending Prevention

In 1.3, we explained that multiple spending can be prevented in on-line paymentsby maintaining a database of spent electronic coins, but there is nocryptographic method for preventing an off-line coin from being spent morethan once. Instead, off-line multiple spending is detected when the coinis deposited and compared to a database of spent coins. Even in anonymous,untraceable payment schemes, the identity of the multiple-spender can berevealed when the abuse is detected. Detection after the fact may be enoughto discourage multiple spending in most cases, but it will not solve theproblem. If someone were able to obtain an account under a false identity,or were willing to disappear after re-spending a large sum of money, theycould successfully cheat the system.

One way to minimize the problem of multiple spending in an off-line systemis to set an upper limit on the value of each payment. This would limit thefinancial losses to a given merchant due to accepting coins that have beenpreviously deposited. However, this will not prevent someone from spendingthe same small coin many times in different places.

In order to prevent multiple spending in off-line payments, we need to relyon physical security. A 'tamper-proof' card could prevent multiple spendingby removing or disabling a coin once it is spent. Unfortunately, there isno such thing as a truly 'tamper-proof' card. Instead, we will refer to a'tamper-resistant' card, which is physically constructed so that it is verydifficult to modify its contents. This could be in the form of a smart card,a PC card10, or any storage device containing a tamper-resistantcomputer chip. This will prevent abuse in most cases, since the typical criminalwill not have the resources to modify the card. Even with a tamper-resistantcard, it is still essential to provide cryptographic security to preventcounterfeiting and to detect and identify multiple spenders in case thetamper-protection is somehow defeated. Also, setting limits on the valueof off-line payments would reduce the cost-effectiveness of tampering withthe card.

Tamper-resistant cards can also provide personal security and privacy tothe cardholder by making it difficult for adversaries to read or modify theinformation stored on the card (such as secret keys, algorithms, or records).

__________

10 Formerly PCMCIA, or Personal Computer Memory Card InternationalAssociation.

5.2 Wallet Observers

All of the basic off-line cash schemes presented in 3.3 can cryptographicallydetect the identity of multiple spenders, but the only way to prevent off-linemultiple spending is to use a tamper-resistant device such as a smart card.One drawback of this approach is that the user must put a great deal of trustin this device, since the user loses the ability to monitor information enteringor leaving the card. It is conceivable that the tamper-resistant device couldleak private information about the user without the user's knowledge.

Chaum and Pedersen [6] proposed the idea of embedding a tamper-resistantdevice into a user-controlled outer module in order to achieve the securitybenefits of a tamper-resistant device without requiring the user to trustthe device. They call this combination an electronic wallet (see Figure 4).The outer module (such as a small hand-held computer or the user's PC) isaccessible to the user. The inner module which cannot be read or modifiedis called the 'observer.' All information which enters or leaves the observermust pass through the outer module, allowing the user to monitor informationthat enters or leaves the card. However, the outer module cannot completea transaction without the cooperation of the observer. This gives the observerthe power to prevent the user from making transactions that it does not approveof, such as spending the same coin more than once.

Figure 4. An electronic wallet.

Brands[1] and Ferguson[8] have both shown how to incorporate observers intotheir respective electronic cash schemes to prevent multiple spending. Brands'scheme incorporates observers in a much simpler and more efficient manner.In Brands' basic scheme, the user's secret key is incorporated into eachof his coins. When a coin is spent, the spender uses his secret to createa valid response to a challenge from the payee. The payee will verify theresponse before accepting the payment. In Brands' scheme with wallet observers,this user secret is shared between the user and his observer. The combinedsecret is a modular sum of the two shares, so one share of the secret revealsno information about the combined secret. Cooperation of the user and theobserver is necessary in order to create a valid response to a challengeduring a payment transaction. This is accomplished without either the useror the observer revealing any information about its share of the secret tothe other. It also prevents the observer from controlling the response; hencethe observer cannot leak any information about the spender.

An observer could also be used to trace the user's transactions at a latertime, 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) mustbe able to obtain the observer and analyze it. Also, not all types of observerscan be used to trace transactions. Brands and Ferguson both claim that theycan incorporate observers into their schemes and still retain untraceabilityof the users' transactions, even if the observer used in the transactionshas been obtained and can be analyzed.

5.3 Security Failures

Types of failures.

In any cryptographic system, there is some risk of a security failure. Asecurity failure in an electronic cash system would result in the abilityto forge or duplicate money. There are a number of different ways in whichan electronic cash system could fail.

One of the most serious types of failure would be that the cryptography (theprotocol or the underlying mathematics) does not provide the intendedsecurity.11 This could enable someone to create valid lookingcoins without knowledge of an authorized bank's secret key, or to obtainvalid secret keys without physical access to them. Anyone who is aware ofthe weakness could create coins that appear to come from a legitimate bankin the system.

Another serious type of failure could occur in a specific implementationof the system. For example, if the bank's random number generator is nota-good one, one may be able to guess the secret random number and use itto compute the secret keys that are used to create electronic money.

Even if the cryptography and the implementation are secure, the securitycould fail because of a physical compromise. If a computer hacker, thief,dishonest bank employee, or a rogue state were to gain access to the bank'ssecret key they could create counterfeit money. If they gain access to auser's secret key they could spend that user's money. If they could modifythe user or bank's software they could destroy the security of the system.

The above failure scenarios apply, not only to the electronic cash system,but also to the underlying authentication infrastructure. Any form of electroniccommerce depends heavily on the ability of users to trust the authenticationmechanisms. So if, for example, an attacker could demonstrate a forgery ofthe certification authority's digital signature, it would undermine the users'trust in their ability to identify each other. Thus the certification authoritiesneed to be secured as thoroughly as do the banks.

Consequences of a failure.

All three of the basic schemes described in this paper are anonymous, whichmakes it impossible for anyone to connect a deposited coin to the originatingbanks withdrawal record of that coin. This property has serious consequencesin the event of a security failure leading to token forgery. When a coinis submitted for deposit, it is impossible to determine if it is forged.Even the originating bank is unable to recognize its own coins, preventingdetection of the compromise. It is conceivable that the compromise will notbe detected until the bank realizes that the total value of deposits of itselectronic cash exceeds the amount that it has created with a particularkey. At this point the losses could be devastating.

After the key compromise is discovered, the bank will still be unable todistinguish valid coins from invalid ones since deposits and withdrawalscannot be linked. The bank would have to change its secret key and invalidateall coins which were signed with the compromised key. The bank can replacecoins that have not yet been spent, but the validity of untraceable coinsthat have already been spent or deposited cannot be determined withoutcooperation of the payer. Payment untraceability prevents the Bank fromdetermining the identity of the payer, and payer anonymity prevents eventhe payee from identifying the payer.

It is possible to minimize this damage by limiting the number of coins affectedby a single compromise. This could be done by changing the Bank's publickey at designated time intervals, or when the total value of coins issuedby a single key exceeds a designated limit. However, this kind ofcompartmentation reduces the anonymity by shrinking the pool of withdrawalsthat could correspond to a particular deposit and vice versa.

__________

11 We are unaware of anything in the literature that would suggestthis type of failure with the protocols discussed in this paper.

5.4 Restoring Traceability

The anonymity properties of electronic cash pose several law enforcementproblems because they prevent withdrawals and deposits from being linkedto each other. We explained in the previous section how this prevents detectionof forged coins. Anonymity also makes it difficult to detect money launderingand tax evasion because there is no way to link the payer and payee. Finally,electronic cash paves the way for new versions of old crimes such as kidnappingand blackmail (see [13]) where money drops can now be carried out safelyfrom the criminal's home computer.12

One way to minimize these concerns is to require large transactions or largenumbers of transactions in a given time period to be traceable. This wouldmake it more difficult to commit crimes involving large sums of cash. However,even a strict limit such as a maximum of $100 a day on withdrawals and depositscan add up quickly, especially if one can open several accounts, each withits own limit. Also, limiting the amount spent in a given time period wouldhave to rely on a tamper-resistant device.

Another way to minimize these concerns is to provide a mechanism to restoretraceability under certain conditions, such as a court order. Traceabilitycan be separated into two types by its direction. For~ard traceability isthe ability to identify a deposit record (and hence the payee), given awithdrawal record (and hence the identity of the payer). In other words,if a search warrant is obtained for Alice, forward tracing will reveal whereAlice has spent her cash. Back~ard traceability is the ability to identifya withdrawal record (and hence the payer), given a deposit record (and hencethe identity of the payee). Backward tracing will reveal who Alice has beenreceiving payments from.

A solution that conditionally restores both forward and backward traceabilityinto the cut-and-choose scheme is presented by Stadler, Piveteau, and Camenischin [14]. In the basic cut-and choose scheme, an identifying number is associatedwith each withdrawal record and a different identifying number is associatedwith each deposit record, although there is no way to link these two recordsto each other. To provide a mechanism for restoring backward traceability,the withdrawal number (along with some other data which cannot be associatedwith the withdrawal) is encrypted with a commonly trusted entity's publickey and incorporated into the coin itself. This encrypted withdrawal numberis passed to the payee as part of the payment protocol, and then will bepassed along to the bank when the coin is deposited by the payee. The payerperforms the encryption during the withdrawal transaction, but the bank caninsure that the encryption was done properly. If the required conditionsfor tracing are met, the payment or deposit can be turned over to the trustedentity holding the secret key to decrypt the withdrawal number. This withdrawalnumber will allow the bank to access its withdrawal records, identifyingthe payer.

To provide a mechanism for restoring forward traceability, the payer mustcommit to a deposit number at the time that the coin is withdrawn. The payerencrypts this deposit number with a commonly trusted entity's public key(along with some other data that cannot be associated with the deposit) andmust send this value to the bank as part of the withdrawal protocol. Thebank is able to determine that the payer has not cheated, although it onlysees the deposit number in encrypted form. If the required conditions fortracing are met, the withdrawal record can be turned over to the trustedentity holding the secret key to decrypt the deposit number. The bank canuse this deposit number to identify the depositor (the payee).

Stadler et al. have shown that it is possible to provide a mechanism forrestoring traceability in either or both directions. This can be used toprovide users with anonymity, while solving many of the law enforcement problemsthat exist in a totally untraceable system. The ability to trace transactionsin either direction can help law enforcement officials catch tax evadersand money launderers by revealing who has paid or has been paid by the suspectedcriminal. Electronic blackmailers can be caught because the deposit numbersof the victim's ill-gotten coins could be decrypted, identifying the blackmailerwhen the money is deposited.

The ability to restore traceability does not solve one very important lawenforcement problem: detecting forged coins. Backwards tracing will helpidentify a forged coin if a particular payment or deposit (or depositor)is under suspicion. In that case, backwards tracing will reveal the withdrawalnumber, allowing the originating bank to locate its withdrawal record andverify the validity of the coin. However, if a forged coin makes its wayinto the system it may not be detected until the bank whose money is beingcounterfeited realizes that the total value of its electronic cash depositsusing a particular key exceeds the values of its withdrawals. The only wayto determine which deposits are genuine and which are forged would requireobtaining permission to decrypt the withdrawal numbers for each and everydeposit of electronic cash using the compromised key. This would violatethe privacy that anonymous cash was designed to protect.

Unfortunately, the scheme of [14] is not efficient because it is based onthe bulky cut-and-choose method. However, it may be possible to apply similarideas to restore traceability in a more efficient electronic cash scheme.

__________

1.3 Divisibility Rulesmr. Mac's Page Shortcut

12 We will not focus on such crimes against individuals, concentratinginstead on crimes against the Government, the banking system, and the nationaleconomy.

CONCLUSION

This report has described several innovative payment schemes which provideuser anonymity and payment untraceability. These electronic cash schemeshave cryptographic mechanisms in place to address the problems of multiplespending and token forgery. However, some serious concerns about the abilityof an electronic cash system to recover from a security failure have beenidentified. Concerns about the impact of anonymity on money laundering andtax evasion have also been discussed.

Because it is simple to make an exact copy of an electronic coin, a secureelectronic cash system must have a way to protect against multiple spending.If the system is implemented on-line, then multiple spending can be preventedby maintaining a database of spent coins and checking this list with eachpayment. If the system is implemented off-line, then there is no way to preventmultiple spending cryptographically, but it can be detected when the coinsare deposited. Detection of multiple spending after-the-fact is only usefulif the identity of the offender is revealed. Cryptographic solutions havebeen proposed that will reveal the identity of the multiple spender whilepreserving user anonymity otherwise.

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

The untraceability property of electronic cash creates problems in detectingmoney laundering and tax evasion because there is no way to link the payerand payee. To counter this problem, it is possible to design a system thathas an option to restore traceability using an escrow mechanism. If certainconditions are met (such as a court order), a deposit or withdrawal recordcan be turned over to a commonly trusted entity who holds a key that candecrypt information connecting the deposit to a withdrawal or vice versa.This will identify the payer or payee in a particular transaction. However,this is not a solution to the token forgery problem because there may beno way to know which deposits are suspect. In that case, identifying forgedcoins would require turning over all of the Bank's deposit records to thetrusted entity to have the withdrawal numbers decrypted.

We have also looked at two optional features of off-line electronic cash:transferability and divisibility. Because the size of an electronic coinmust grow with each transfer, the number of transfers allowed per coin mustbe limited. Also, allowing transfers magnifies the problems of detectingcounterfeit coins, money laundering, and tax evasion. Coins can be made divisiblewithout losing any security or anonymity features, but at the expense ofadditional memory requirements and transaction time.

In conclusion, the potential risks in electronic commerce are magnified whenanonymity is present. Anonymity creates the potential for large sums ofcounterfeit money to go undetected by preventing identification of forgedcoins. Anonymity also provides an avenue for laundering money and evadingtaxes that is difficult to combat without resorting to escrow mechanisms.Anonymity can be provided at varying levels, but increasing the level ofanonymity also increases the potential damages. It is necessary to weighthe need for anonymity with these concerns. It may well be concluded thatthese problems are best avoided by using a secure electronic payment systemthat provides privacy, but not anonymity.

1.3 Divisibility Rulesmr. Mac's Page Key

REFERENCES

1. Stefan Brands, Untraceable Off-Line Cash in Wallets with Observers,Advances in Cryptology CRYPTO '93, Springer-Verlag, pp. 302-318.

2. David Chaum, Achieving Electronic Privacy, Scientific American(August 1992), 96-101.

3. David Chaum, Security without Identification: Transaction Systems tomake Big Brother Obsolete, ACM 28 no. 10 (Oct 1985), 1030-1044.

4. David Chaum, Amos Fiat, and Moni Naor, Untraceable Electronic Cash,Advances in Cryptology CRYPTO '88, Springer-Verlag, pp. 319-327.

5. David Chaum and Torben Pedersen, Transferred Cash Grows in Size,Advances in Cryptology - EUROCRYPT '92, Springer-Verlag, pp. 390-407.

6. David Chaum and Torben Pedersen, Wallet Databases with Observers,Advances in Cryptology CRYPTO '92, Springer-Verlag, pp. 89-105.

7. Tony Eng and Tatsuaki Okamoto, Single-Term Divisible ElectronicCoins, Advances in Cryptology EUROCRYPT '94, Springer-Verlag, pp. 311-323.

8. Niels Ferguson, Extensions of Single-term Coins, Advances in Cryptology- CRYPTO '93, Springer-Verlag, pp. 292-301.

9. Niels Ferguson, Single Term Off-Line Coins, Advances in Cryptology- EUROCRYPT '93, Springer-Verlag, pp. 318-328.

10. Alfred J. Menezes, Elliptic Curve Public Key Cryptosystems, KluwerAcademic Publishers, Boston, 1993.

11. Tatsuaki Okamoto, An Efficient Divisible Electronic Cash Scheme,Advances in Cryptology - CRYPTO '95, Springer-Verlag, pp. 438-451.

12. Tatsuaki Okamoto and Kazuo Ohta, Universal Electronic Cash, Advancesin Cryptology - CRYPTO '91, Springer-Verlag, pp. 324-337.

13. Sebastiaan von Solms and David Naccache, On Blind Signatures and PerfectCrimes, Computers & Security 11 (1992), 581-583.

14. Markus Stadler, Jean-Marc Piveteau, and Jan Camenisch, Fair BlindSignatures, Advances in Cryptology - EUROCRYPT '95, Springer-Verlag,pp. 209-219.

[End]

Thanks to the authors,Thomas Vartanian and anonymous others.

Report any transcription mistakes in equations to <jya@pipeline.com>.Check corrections page for updates.