CSci 4554 Lab 5. Digital Cash

Due Monday, Dec 9 at 11:59pm (by e-mail)

40 points total


This lab is done in groups of 2. The goal of the lab is to implement implement a zero-knowledge identity proof and digital cash. You will also get practice detecting dishonest participants.

All exchanges are done via google docs shared with the appropriate group and myself. No one else should be included.

Tasks for the lab:

Your task is to implement digital cash, as described in this overview. Different groups will be assigned different roles. The goal is to be able to distinguish a legitimate transaction from an attempt to cheat. The roles and tasks will be as follows:

More specifically:

  1. The bank generates RSA modulus in which p, q are at least 100 bits (note that we will use it to encrypt the result of SHA-1 which is 160 bits). To follow the the suggested scheme, use e = 3. Note that 1/3 in the description refers to d (the inverse of e mod (p-1)(q-1)).
  2. All parties need to use a seeded random number generator. Each group needs to pick a large (at least 5 digits) seed. This guarantees (hopefully) that all the seeds are different.
  3. Account numbers for customers are 10-digit binary numbers. They are set by the bank.
  4. The customer group creates digital cash (say, in $100 bills) for each customer as defined in the protocol. Assume k = 40. The parameters are as follows:
  5. Keep a_i, y_i, and x_i and the blinding factor for each element of each bill. Keep track of which elements have been opened by the bank and discarded.
  6. After all a_i, x_i, and y_i are created, "Alice" (the customer) concatenates x_i and y_i and computes SHA-1 of the result (this is the g(x_i, y_i) part of the protocol). The concatenation is treated as a string. Then follow the example on how to pass it to SHA-1. The result of SHA-1 is represented as a BigInteger created by passing the result of SHA-1 (the byte array) to BigInteger constructor.
  7. Then she generates a "blinding factor" r_i for each g(x_i, y_i) and sends all of them (blinded) to the bank for a blind signature. Recall that "Alice" needs to prepare the blinding factors so that she can easily compute a signature for the bill. Note that at least one of the customers is expected to be cheating at this point.
  8. The bank send each customer ("Alice") a request to open randomly chosen 20 bills. The customer sends the blinding factor to unblind those. If the bank detects cheating, the customer repeats the procedure.
  9. After the bank verifies the bills, it signs the product of the remaining k/2 numbers mod N (as an RSA signature).
  10. The customer unblinds the signed cash by dividing it by the product of the unblinding factors of the 20 remaining elements.
  11. The customer pays some of the merchants with the signed bills by sending the bill (the product) and its signature. The merchant verifies the bank signature (if it's not a proper signature, the transaction gets canceled). In the process he sends the customer a randomly chosen sequence of k/2 0s and 1s and the customer sends the corresponding elements: Then for each i "Bob" can find x_i and y_i, compute SHA-1 of their concatenation, and verify the bank's signature on their product. "Alice" has to try to cheat at this point by providing a bill that hasn't been properly signed.
  12. When the money is deposited (with the customer responses to 0/1 challenges), the bank checks the cash value and verifies that the cash has not been double-spent. If it has been, the bank uses the 0/1 challenges to find out who is the cheater. "Alice" group has to double-spend at least one bill, the bank has to detect it.

What to submit (by e-mail to me, CC your partner)

  1. All your program code (well-documented) and instructions for running it.
  2. All your computations with explanations.
  3. Detailed explanations of what you were doing and why.

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.