Transcript Document
Digital Cash OUTLINE Properties Scheme Initialization Creating a Coin Spending the Coin Depositing the Coin Fraud Control Anonymity p2. Properties 1. 2. 3. 4. 5. 6. Security The cash can be sent securely through computer network. Can’t be copied and reused Privacy (Untraceability or Anonymity) If the cash is spent legitimately, neither the recipient nor the bank can identify the spender. Offline payment No communication with the bank is needed during the transaction. Transferability The cash can be transferred to others. Dividability A piece of cash can be divided into smaller amounts. p3. T. Okamoto and K. Ohta, "Universal electronic cash," Advances in Cryptology-CRYPTO'91, LNCS 576, Springer-Verlag, pp. 324-337, 1991. (satisfies 1 ~ 6) S. Brands, "Untraceable off-line cash in wallets with observers," Advances in Cryptology-CRYPTO'93, LNCS 773, SpringerVerlag, pp. 302-318, 1994. (satisfies 1 ~ 4) p4. Scheme Bank 1. Withdraw 6. Results 2. Coin 5. Deposit 3. Payment 4. Receipt Spender Merchant p5. Initialization (1/2) Publish: p : a large prime, s.t. q = (p – 1) / 2 is also prime. g : the square of a primitive root mod p. g1 = g a mod p (a and b are secretly chosen and discarded immediately) g2 = g b mod p H : a hash function H : Z Z Z Z Z Zq* H0 : a hash function H0 : Z Z Z Z Zq* p6. Initialization Bank 3. Send I 1. Choose a secret number u 2. Compute I g1u (mod p) (2/2) 1. Choose a secret number x 2. Compute h gx, h1 g1x, h2 g2x (mod p) 3. Publish h, h1, and h2 2. Register M 4. Send z’ (Ig2)x (mod p) 1. Choose an ID number M Merchant Spender p7. Creating a Coin Withdraw Bank Choose a random number w Spender gw gw , (Ig2) w(mod p) Choose a secret random 5-tuple of integers (s, x1, x2, 1, 2), s 0 (mod q) Compute c 11H ( A, B, z, a, b) c1 cx + w (mod q) A ( Ig 2 ) s , B g1x1 g2x2 , z z ' s , a g w1 g 2 , b s1 A2 (mod p ) Compute r 1 c1 + 2 (mod q) C = (A, B, z, a, b, r) p8. Spending the Coin Pay (A, B, z, a, b, r) Merchant Spender Check whether d = H0(A, B, M, Timestamp) r1 dus + x1, r2 ds + x2 (mod q) gr ahH(A, B, z, a, b) (mod p), Ar zH(A, B, z, a, b)b (mod p) Check whether g1r1 g 2r2 Ad B (mod p ) Accept or reject p9. Depositing the Coin Deposit (A, B, z, a, b, r), (r1, r2, d) Merchant Bank Check whether the coin has been previously deposited or not, and gr ahH(A, B, z, a, b) (mod p), Ar zH(A, B, z, a, b)b (mod p), g1r1 g 2r2 Ad B (mod p ) Results p10. Fraud Control (1/7) Case 1: The Spender spends the coin twice. C, (r1, r2, d) Merchant 1 Spender C , (r '1 , r '2 , d ' ) r1 r'1 us(d d ' ) (mod q), Merchant 2 r2 r'2 s(d d ' ) (mod q) u ( r1 r '1 )( r2 r '2 ) 1 (mod q) I g1u (mod p ) p11. Fraud Control (2/7) Case 2: The Merchant tries submitting the coin twice. C, (r1, r2, d) Merchant C , (r '1 , r '2 , d ' ) Bank forged Impossible! Since it is very difficult to produce numbers such that (since the Merchant does not know u). g1r '1 g2r '2 Ad ' B (mod p ) p12. Fraud Control (3/7) Case 3: Someone try to make an unauthorized coin. Impossible! Since this requires finding numbers such that gr ahH(A, B, z, a, b) (mod p), and Ar zH(A, B, z, a, b)b (mod p), p13. Fraud Control Case 4: (4/7) 2. Deposit C, (r1, r2, d) Bank 1. Spend C Spender evil 3. Spend C Merchant 1 Merchant 2 Impossible! The Merchant 2 computes d’ (very likely != d). It is very difficult for the evil merchant to produce numbers such that g1r '1 g2r '2 Ad ' B (mod p ) p14. Fraud Control (5/7) Case 5: Someone working in the Bank tries to forge a coin. It is possible to make a coin satisfied gr ahH(A, B, z, a, b) (mod p), and Ar zH(A, B, z, a, b)b (mod p), but he does not know u , thus unable to produce a suitable r1. So, he cannot spend it. p15. Fraud Control (6/7) Case 6: Someone steal the coin from the Spender and try to spend it. Impossible! The thief does not know u, thus unable to produce r1. p16. Fraud Control (7/7) Case 7: An evil merchant steals the coin and (r1, r2, d) before they are submitted to the Bank, and then deposits them to the Bank. Possible! This is a flaw of ordinary cash, too. p17. Anonymity (1/3) During the entire transaction with the Merchant, the Spender never needs to provide any identification. p18. Anonymity (2/3) Is it possible for the Bank to extract the Spender’s identity from knowledge of the coin (A, B, z, a, b, r) and the triple (r1, r2, d) ? No. A, B, z, a, b look like random numbers to everyone except the Spender. The Bank never sees A, B, z, a, b, r until the coin is deposited. p19. Anonymity (3/3) When creating the coin, the Bank provides only gw and c1, and has seen only c 1–1H(A, B, z, a, b) (mod q). the Bank cannot compute H(A, B, z, a, b) and deduce 1 at that time. The Bank can keep a list of all values c it has received, along with values of H for every coin that is deposited, and then try all combinations to find 1. (impractical for a system of millions of coins) p20.