by Ari Kermaier

There are several fundamental properties of physical cash that we would like to replicate (or improve) using digital cash:

• Cash must be difficult to counterfeit. Banknotes and coins are technically difficult to copy but, once duplicated, are relatively easily spent. Digital cash is just electronic data which is easily copied, so secure schemes must aim to make it difficult to successfully spend the duplicates.

• Anonymity is one of the most attractive features of cash. Once cash has changed hands, it is impossible to identify the payer or the payee, or even what the amount of the transaction was, unless someone is recording serial numbers and social security numbers for every transaction. Since, at a fundamental level, digital cash consists of information, considerable effort is needed to ensure that tracking codes are not included in that information.

• That cash is off-line spendable is important. If every little transaction needed verification by a bank, there would be a terrible bottleneck at the bank’s database system.

• Physical cash is transferable along an indefinitely long chain of users. Most digital cash schemes forgo this difficult-to-achieve property, opting instead for a payment system that allows only one transaction per digital banknote.

An ideal digital cash system is one that works in the complete absence of trust between the parties involved. For the purpose of this discussion we will assume the following general structure of a digital cash system:

Under these conditions, several security features must be implemented:

• For anonymity to hold, it must be impossible for the bank to identify which user spent the cash in a given transaction. It must also be impossible to link transactions as having been conducted by the same user.

• To prevent counterfeiting, a user must be prevented from copying cash and spending it twice.

• To prevent cheating, a merchant must be prevented from depositing the same payment twice with the bank.

In order to construct a good digital cash system methods from all areas of cryptography come together:

• Public key and private key cryptography, including digital signatures and certificates, and one-way functions are used to ensure authenticity.

• Blind signatures and cut-and-choose techniques are used to ensure anonymity.

• Secret splitting, bit commitment and random selector strings are used to prevent cheating.

To illustrate how cryptographic techniques can be used to construct a good digital cash system, I will consider a combination of elements from two proposed schemes. DigiCash, a European company, has developed a scheme, based on the work of David Chaum, called ecash. Another scheme with similar characteristics is described by Stefan Brands.

For this example I will use the following symbols:

When the user wants to withdraw a certain amount of cash from the account, the following protocol can be used. The user constructs a withdrawal request consisting of the amount and the account number, and digitally signs it using the user’s secret key (of a public/secret key pair). The bank verifies the signature and debits the user’s account by the amount. The bank then calculates a one-way hash of the amount and the tamper-resistant device’s secret key. The user’s TRD verifies the expected hash value and increments it’s stored balance counter by the withdrawn amount.

In this scenario, the user can cheat using a replay attack against the TRD. To foil this, the bank can use ¦ ( SK_T, amount, sequence) and the TRD can be programmed to reject any sequence number not larger than the last one.

In order to spend the amount of cash stored in the TRD, the user must also have certificates from the bank that will be used in transactions with the merchant. These certificates (essentially signed public keys) can each be used only once, but for any amount up to the balance stored in the TRD. (Alternatively, some schemes use the certificates themselves as fixed-value digital coins, eliminating the need for the TRD to store a balance, but reducing flexibility.)

The certificate withdrawal protocol can be performed as follows. The user generates a number of (e.g. 100) secret/public key pairs, and blinds the public keys using an equal number of randomly generated blinding factors. The bank executes a cut-and-choose blind signature, and the user unblinds the signed public key. This is repeated until the desired number of certificates have been created.

To make a purchase, the user constructs a transaction string consisting of the amount, the date and time and the merchant’s ID, and signs it using the secret key that matches one of the public keys certified by the bank. This information, along with the corresponding certified public key, is transmitted to the merchant. The merchant, using the universally know public key of the bank, obtains the certified public key, and uses that to verify the user’s signature on the transaction string.

This protocol is too simple, however, as it provides no protection against double-spending by the user or double-depositing by the merchant. To achieve this type of security, we must modify both the certificate withdrawal protocol and the purchase protocol:

For each blinded public key generated by the user, the user would need to include some identifying information. This could consist of an identifier string, split into two halves, with both sides blinded using a number of (e.g. 100) random blinding factors (with bit commitment). When the bank performs its cut-and-choose selection of a public key, a set of 100 split, blinded identifiers would be chosen as well, and signed with the bank’s secret key along with the certified public key.

At the time of the purchase transaction, the user transmits the bank-certified 100 split/blinded identifiers with the bank-certified public key, along with the unsigned identifiers and public key, to the merchant. The merchant verifies the signatures using the bank’s public key. Then the merchant generates a random, 100-bit selector string and transmits it to the user. The user then unblinds either the left or the right half of each of the blinded identifiers, based on the bits of the selector string. These half-unblinded identifiers, along with the transaction string, are then signed using the secret key corresponding to the certified public key, and transmitted to the merchant.

At suitable intervals (e.g. at the end of the day), the merchant deposits receipts at the bank. The merchant transmits the purchase transcript to the bank, along with the corresponding bank-certified public key. The bank adds this information to its database of spent cash and performs a check. If the certified public key PK_C is already in the database, then there is a problem of one of the following types:

If the entire purchase transcript is identical to the one already in the database, then the merchant is a stupid cheater - he’s trying to get away with double-reporting the entire purchase transaction.

If the half-unblinded set of identifiers ID_U is identical to the set already in the database, then the merchant is attempting to cheat by double-depositing the digital cash, with a new (possibly fabricated) purchase transcript.

If the two sets of half-unblinded identifiers are different, then the user must have cheated by double-spending the same digital cash certificate. To catch the criminal, the bank can XOR the two sets together and, with very high probability, at least one matching pair of unblinded identifier halves with combine to reveal the users identity.

Stefan Brands, "Electronic Cash on the Internet", 1994

http://www.cwi.nl/ftp/brands/e-cash.ps

Berry Schoenmakers, "Basic Security of the ecash Payment System", 1997

http://www.digicash.com/ecash/docs/cosic.pdf

David Chaum, "Security Without Identification"

http://www.digicash.com/new/archive/bigbro.html

David Chaum, "Achieving Electronic Privacy"

http://www.digicash.com/new/archive/sciam.html

David Chaum, "Digital Signatures and Smart Cards"

http://www.digicash.com/new/archive/digbig.html

DigiCash

http://www.digicash.com/

Roy Davies digital cash links

http://www.ex.ac.uk/~RDavies/arian/emoney.html