CPS 214Clearing and SettlingFedwireQuantum CryptographyUsing photon polarizationQuantum Key ExchangeIn the “real world”15-853 Algorithms in the Real World Electronic CashToken vs. Notational MoneyOnline v. Offline SystemsElectronic CashElectronic Cash -- Idea 1Blind SignaturesSlide 14Slide 15eCash (Formerly DigiCash)Minting eCashMinting eCash, cont.Spending eCashDepositing eCashProving an eCash PaymentLost eCashAnonymous Ecash  CrimeOffline Double-SpendingChaum Double-Spending ProtocolProbability Cheating is DetectedChaum ProtocolSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSCPS 214Bank Clearing and SettlementQuantum Key ExchangeElectronic CashELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSClearing and Settling•Clearing: determining the amount that one party owes another•Settling: transfer of funds from one party to the other•Banks clear and settle every day (or at least on those rare days when banks are open)ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSFedwire•Owned and operated by Federal Reserve Banks•7500 participant banks keep accounts with Federal Reserve•Over $2,000,000,000,000 transferred per day•FEDNET proprietary telecommunications network•Physical security mechanisms difficult to uncover!•Now permits some IP or web-based transactionsELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSQuantum Cryptography•In quantum mechanics, there is no way to take a measurement without potentially changing the state. E.g.–Measuring position, spreads out the momentum–Measuring spin horizontally, “spreads out” the spin probability verticallyRelated to Heisenberg’s uncertainty principalELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSUsing photon polarizationdiagonal basisrectilinear basismeasurediagonalmeasurerectilinearMeasuring using one basis changes polarization to that basis!Bennet and Brassard 198410ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSQuantum Key Exchange1. Alice creates each random bit and then randomly encodes it in one of two bases:2. Bob measures photons in random orientationse.g.: x + + x x x + x (orientations used) \ | - \ / / - \ (measured polarizations)and tells Alice in the open what orientations he used, but not what he measured.3. Alice tells Bob in the open which orientations are correct4. Bob and Alice compare a randomly chosen subset of sent/received bits to detect eavesdropper5. Susceptible to a man-in-the-middle attackELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSIn the “real world”•10-node DARPA Quantum Network since 2004•Los Alamos/NIST March 2007, 148kmELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOS15-853Algorithms in the Real WorldElectronic CashMichael I. Shamos, Ph.D., J.D.Co-DirectorELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSToken vs. Notational Money•Token money–Represented by a physical article (e.g. cash, traveler’s check, gift certificate, coupon)–Can be lost–Used for instantaneous value transfer•Notational money (account ledger entries)–Examples: bank accounts, frequent flyer miles–Can’t be lost–Transfer by order to account holder, usually not immediate–Requires “clearance” and “settlement”WHAT IS THE NET EFFECT OF ALL THE ORDERS?(HOW MUCH DOES EACH PARTY HAVE TO PAY?)ACTUAL PAYMENT IN “REAL” MONEYELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSOnline v. Offline Systems•An online system requires access to a server for each transaction.–Example: credit card authorization. Merchant must get code from issuing bank.•An offline system allows transactions with no server.–Example: cash transaction. Merchant inspects money. No communication needed.ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSElectronic Cash•Electronic cash is token money in the form of bits, except unlike token money it can be copied. This creates a host of problems:•A copy of a real bill is a counterfeit.A copy of an ecash string is not counterfeit (it’s a perfect copy)•How is ecash issued? How is it spent? Why would anyone accept it?•Counterfeiting•Loss (it’s token money; it can be lost)•What prevents double spending?•Can it be used offline?ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSElectronic Cash -- Idea 1•Bank issues character strings containing:–denomination–serial number–bank ID + encryption of the above•First person to return string to bank gets the moneyPROBLEMS:•Can’t use offline. Must verify money not yet spent.•Not anonymous. Bank can record serial number.•Sophisticated transaction processing system required with locking to prevent double spending.•Eavesdropping!ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSBlind Signatures•Sometimes useful to have people sign things without seeing what they are signing–notarizing confidential documents–preserving anonymity•Alice wants to have Bob sign message M.(In cryptography, a message is just a number.)•Alice multiplies M by a number -- the blinding factor•Alice sends the blinded message to Bob. He can’t read it — it’s blinded.•Bob signs with his private key, sends it back to Alice.•Alice divides out the blinding factor. She now has M signed by Bob.ELECTRONIC CASH FALL 2000 COPYRIGHT © 2000 MICHAEL I. SHAMOSBlind Signatures•Alice wants to have Bob sign message M.•Bob’s public key is (e, n). Bob’s private key is d.•Alice picks a blinding factor k between 1 and n.•Alice blinds the message M by computingT = M ke (mod n) She sends T to Bob.•Bob signs T by computingTd = (M ke)d (mod n) = Md k (mod n)•Alice unblinds this by dividing out the blinding factor:S = Td/k = Md k (mod n)/k = Md (mod n)•But this is the same as if Bob had just signed M, except Bob was unable to read Te • d = 1 (mod (n))ELECTRONIC CASH FALL 2000