Customer ---------------------> Merchant
\ /
\ Before / After
\ /
\ /
\ /
------- Bank --------
Customer and bank interact before transactions, i.e. establish a credit card account. Bank and merchant interact during/after transaction to make sure that account is legit.
Cash
- Pros: hard to trace, instantaneous, no bank involvement
- Cons: Can get lost or stolen, can�t get it back, forgeable, bulky, can only be used in person.
Storing cash as bits:
- Obvious approach: �Pay the bearer $1,� signed Bank => �digital coin�
- This is copyable
Improvement: give each coin a serial number.
- Can detect whether coins are copies
- Only after the fact (after something is copied)
- Can�t tell who did the copying
- Don�t have privacy�coins can be traced to where you spent it.
Method
- Customer generates a serial number and the bank signs.
- Customer generates random R, computes (R^e mod N).
- (e, N) = RSA public key of the bank
- Customer gives bank (C * R^e mod N) to sign. C is the coin.
- After signing, give the coin back to the customer: [(C * R^e)^d mod N], d is private key
- Expands to [C^d * R^(ed) mod N] = C^d * R mod N (because R^(ed) means R encrypted, then decrypted, which is just R).
- Customer divides by R to get C^d mod N. This is the bank�s signature.
- This is a blind signature, the bank doesn�t see what it�s signing (1 dollar or 1 million)
To prevent customer from lying about value of coin:
- Different signing key for each denomination
- OR customer makes 100 proposed coins. Bank challenges 99 of those coins at random. Customer �unblinds� the challenged coins. Customer caught cheating with 99% probability.
So at this point, we�ve solved the anonymity problem, but we still have to deal with the copying problem.
Bank can�t pinpoint anything (can't tell denomination or serial number)
X = C1 * R1^e
= C2 * R2^e
= Ci * Ri^e [All R�s are equally likely. So you can�t pick apart Ci from Ri.]
Chaum-style e-cash.
- Customer is anonymous unless he spends the same coin twice.
- Can tell whether coin was copied before or after it was spent.
This is great because the customer is anonymous unless he cheats!
Key trick:
- Customer takes his identity, splits it into 2 halves
- Halves are (R, I XOR R). R is random, I is his identity
- Create a bit commitment for each half. (def: A variant of digital signatures, used to commit an object, such as a promise or prediction, without revealing that object until later. It is impossible to unobservably violate the protocol, or to modify the object after it has been comitted.)
- Seal each half so that customer can unwrap each half
- But unwrapping gives back original sealed value
Coin consists of (denomination, serial number, commitments)
- Customer prepares 100 coins (blinded)
- Bank challenges 99 of them
- Bank blindly signs the last coin, customer unblinds
- Example: ($20, serial, C1, C2), signed Bank
Spending:
- Merchant flips a coin, picks C1 or C2 randomly.
- Customer unseals the chosen Ci.
- Deposit by merchant: send the bank the coin value, unsealed Ci, and serial #
- If the customer double-spends, a 50% probability of unsealing BOTH halves of identity and getting caught
- What if 2 merchants deposit the same coin, with the same identity-half unsealed? Can�t tell between double spending or foul play.
Solution: final system
- Require each merchant to flip 100 coins
- Customer puts 100 split-identities into coin
- Odds of coin flips being the same is infinitesimal (1 in 2^100)
- Banks algorithm:
- Suppose 2 merchants deposit same coin
- M1 gives coin flips b1, b2, bN with identity halves unwrapped
- M2 gives coin flips c1, c2, cN with identity halves unwrapped
- If both merchants claim to have a matching sequence, blame the merchants
- Else, blame the customer, and recover the customer�s identity
What about passing coins from customer to customer?
Hmm... you'd have to find a way to reissue the coin. Have the bank resign it? Or hold the original giver accountable? Does not seem right. Put a digital signature on TOP of existing one?
