CS 161 Compute r SecurityFall 2005 Joseph/Tygar/Vazirani/Wagner Notes 20In this lecture we will explore some issues in implementing a digital form of cash - ecash. We normallythink of cash as paper money or coins issued by the treasury or a central bank. Can the assurances normallyassumed for cash be made to carry over to the digital domain in the form of a sequence of bits? To exploresome of the issues that arise in this context, let us consider a game involving three players: the customer, themerchant and the bank. The outline of the protocol we would like to implement is as follows:The customer, Alice, interacts with the bank to withdraw some cash. She then interacts with the merchant,exchanging the cash for some goods. The merchant, Bob, then interacts with the bank to deposit the cash inhis account.A first attempt at implementing this protocol might look like this:1. The bank sends Alice a digital $1 bill. This might be a message signed with the bank’s RSA private keysaying ”serial number x. This is a $1 bill.”2. Alice sends the cash to Bob in exchange for goods.3. Bob later deposits the cash into his account at the bank.There are several problems with this protocol.• It is not anonymous. The bank gets to keep a record of all of Alice’s spending.• Double spending. Since the cash is digital in nature, Alice can easily duplicate it and spend the same$1 bill again with another merchant, Carol.Blind Signatures:One of the key building blocks to achieve anonymity is a blind signature. Recall that RSA signatures requirethe signer to compute mdmod N, where (d,N) is the private key and (e,N) is the public key.A blind RSA signature is carried out as follows:• Alice sends Bob s = (rem) mod N where r is a random number modN.• Bob computes t = sdmod N and sends the result to Alice.• Alice computes t/r mod N = mdmod N.The point is that t = sd= (rem)d= rmdmod N. A blind signature allows Alice to obtain Bob’s signature ona message of her choice, without Bob having any idea what the message being signed is.Proposal 1:Alice and the bank will use blind signatures to collectively create a $1 bill signed by the bank, but one whichthe bank will not recognize as coming from Alice.In this scheme, a valid $1 bill is a pair (x,y) where y = f(x)dmod N. Here f() is a one-way function (ideallya one-way hash function). (e,N) is the bank’s public key and (d,N) is the private key.CS 161, Fall 2005, Notes 20 1• To withdraw the $1 bill, Alice picks x, computes f(x) and runs the blind signature protocol with thebank on f(x). i.e. Alice picks a random r mod N, sends the bank s = ref(x) mod N. The bank sendsback t = sdmod N, and Alice recovers y = f(x)d= t/r mod N.• To pay Bob $1, Alice sends him (x,y).• When Bob later deposits (x,y), the bank checks that ye= f(x), and that (x,y) is not on its list ofpreviously deposited bills.The main feature of this scheme is that the bank cannot connect the bill (x,y) with Alice, since the blindsignature was performed on a perfectly random string s. The reason for the one-way function f() is toprevent forging. For example if instead a valid $1 bill were (x,y) where y = xdmod N, then Alice couldforge a bill by first picking y mod N and then computing x = yemod N. The one-way function makes surethat forging in this way would require Alice to invert the one-way function.The problem with the scheme is that the bank has to be online at all times to identify bills, and the merchant,Bob, must cash the bill immediately, in case Alice tries to double spend.There is an elegant way to create ecash with several denominations: the bank uses the same composite N,but different encryption exponents e for different denominations: e.g. e = 3 for nickels, e = 5 for dimes,e = 7 for quarters, and e = 11 for dollar bills. One subtle point is that choosing e = 9 for a dollar bill wouldbe a mistake. This is because under this scheme (x,y) is a valid dollar bill whenever y9= f(x) mod N. Now,(x,z = y3) is a valid nickel, since z3= y9= f(x) mod N. Thus choosing e = 0 would allow Alice to forge anextra nickel for every dollar she withdraws from the bank. Choosing the encryption exponents to be primenumbers gets around this potential problem.”Offline ecash:”The basic idea of this scheme is that instead of preventing double spending, it enables the bank to detect it.If the user does not double spend, the bank does not learn her identity. If the user double spends, the bankcan compute her identity, and take suitable action.• Alice generates 2k messages, each consisting of a pair ( f(xi), f(xi⊕ Id)), where xiis selected atrandom. Here Id is identifying information about Alice. She sends all these values for blind signatureto the bank. The point of this construction is that revealing either xior xi⊕ Id reveals nothing aboutAlice, but revealing both completely gives away her identity. The rest of the protocol is designed tocheck that Alice really does encode her true identity in these pairs, and that double spending revealsboth of at least one pair of messages with high probability.• The bank asks Alice to unblind k randomly chosen pairs - by revealing the corresponding xi’s andxi⊕ Id’s and the random number riused in the blinding protocol. The bank checcks the k chosenpairs, and checks that Id really is Alice’s identifying information.• If the k randomly chosen pairs check out, then the bank assumes that most of the remaining pairs mustalso be correctly created, and it signs them.• Alice thus obtains blind signatures on k messages of the form: ( f(xi), f(xi⊕ Id)) (we assume that thef(x)’s are sufficiently small so that the pair can be encoded as a number modulo N).To pay the merchant, Bob, Alice goes through the following protocol with him:CS 161, Fall 2005, Notes 20 2• Alice sends Bob the k signed pairs: ( f(xi), f(xi⊕ Id))dmod N. This is just shorthand for saying takethe number z mod N that is the encoding of the pair ( f(xi), f(xi⊕ Id)) and sign it to get zdmod N).• Bob sends k bits b1,...,bkto Alice.• If bi= 0, Alice sends Bob xiand if bi= 1, she sends him xi⊕ Id.• Bob checks each against the signature, and accepts the bill only if they all check out.To deposit the bill, Bob sends the bank the challenge sequence b1,...,bkand Alice’s messages. If the coinis double spent, the bank also gets a second set of challenges from another merchant. With probability1− 1/2k, the two challenge sequences differ on some bit, say the j − th.
View Full Document
Unlocking...