Anonymous e-cash ================ Recall: electronic check scheme is secure, but bank can correlate serial numbers want e-cash scheme where bank doesn't know where the "coin" came from blind signatures let bank sign a message it doesn't know big problem: have to deposit right away; can't track down double-spenders Idea: make payments anonymous _except_ if the user double-spends withdraw: bank generates blind signature on a coin, somehow embeds Alice's ID Alice knows some secret about the coin payment: payment protocol involves revealing some info about secret paying once isn't enough to identify Alice paying twice reveals Alice's identity (e.g. recall threshold crypto) deposit: merchant gives bank whatever he learned from the payment step bank checks if the same coin was already deposited if so, combine information from two payment steps to reveal Alice Zero-knowledge proofs of identity Can Alice convince Bob she knows a secret, without revealing anything else? Intuitively, public-key cryptosystems are close, but not quite there A signature convinces others the signer knew SK, without revealing SK But recipient learns a signature using SK, which he didn't know before Why? We want Bob to be convinced, but he shouldn't convince others he knows Schnorr's protocol p: large prime q: divides p-1, q prime g: generator of order q G_q = , subgroup of order q generated by g Alice has secret x \in Z_q = {0, 1, .., q-1} Alice computes public key y = g^x (mod p) Alice Bob choose random k in Z_q let a = g^k (mod p) a = g^k (mod p) ----------------------------------> choose random c in Z_q c <---------------------------------- let r = k + cx (mod q) r = k + cx (mod q) ----------------------------------> check a*y^c = g^r (mod p) Need to prove 3 theorems: completeness, zero-knowledge, validity Thm: Completeness: if Alice knows x, Bob will accept Proof: Bob computes LHS: a*y^c = (g^k) * (g^x)^c = g^(k+cx) RHS: g^r = g^(k+cx) Thm: Zero-knowledge: Bob learns nothing about x Proof: Bob learns only the transcript (a, c, r) Can think of the entire transcript as a random variable By participating in protocol, Bob learns sample of this random var Bob can generate such random transcripts on his own, without Alice! choose random c in Z_q choose random r in Z_q let a = g^r / y^c [ the reason Bob doesn't need Alice is he picks a after c ] Such generated transcripts will have the right distributions of a, c, r One assumption: Bob was well-behaved, and picked c randomly if Bob picked c based on a, zero-knowledge proof doesn't hold can approximate ZK against adversarial Bob using commitments Alice chooses a, reveals H(a) in step 1, sends a & k in step 3 Thus, Bob learns nothing new from the interaction (other than Alice can play game without knowing c before picking a) Thm: Validity: If Alice doesn't know x, cannot play game <=> If Alice can play game, Alice knows x Proof: By assumption, Alice can produce suitable s for any (or almost any) c Let's fix a = g^k in all rounds of the protocol Suppose Alice succeeds for c and c' Then: r = k + c *x r' = k + c'*x --------------------- r - r' = (c - c') * x x = (k - k') / (c - c') (mod q), if c-c' != 0 mod q By playing game twice with same k, Alice can learn x (even if Alice didn't "know" x before, whatever that means) Key insight: participating in this protocol twice (with same k) reveals x But, how do we both encode something into Alice's secret, and blind it? Recall: DLP problem Given: prime p=2q+1, q prime generator g of G_q = squares in Z_p^* |G_q| = q value y in G_q Find x \in Z_q, such that g^x = y (mod p) DLP assumption: DLP is hard Representation (Rep) problem: Given: prime p=2q+1, q prime generators g_1, g_2 of G_q = squares in Z_p^* value y in G_q Find x_1, x_2, such that g_1^{x_1} * g_2^{x_2} = y (mod p) Rep assumption: Rep is hard Theorem: if discrete log of g_2 base g_1 is unknown (+ DLP assumption), then hard to come up with two reps for any y Proof: Suppose y = g_1^{x_1} g_2^{x_2} = g_1^{x_1'} g_2^{x_2'} (mod p) Then, g2 = g_1^{(x_1-x_1')/(x_2'-x_2)} (mod p) Thus, discrete log of g_2 base g_1 = (x_1-x_1') / (x_2'-x_2) (mod q) Two-rep proof-of-knowledge p=2q+1, q prime g1, g2 generators of G_q; discrete log of g2 base g1 unknown Alice knows x_1, x_2 such that y=g_1^{x_1} g_2^{x_2} (mod p) Can prove to Bob that she knows x_1, x_2 Alice Bob k1, k2 random in Z_q a = g_1^{k_1} g_2^{k_2} --------------------------------------------> c random in Z_q c <-------------------------------------------- r_1 = c x_1 + k_1 r_2 = c x_2 + k_2 --------------------------------------------> Check a*y^c = g_1^{r_1} g_2^{r_2} If Alice answers twice with the same a, but different c': r_1' = c'x_1 + k_1 r_2' = c'x_2 + k_2 Can solve for x_1 = (r_1-r_1') / (c-c') x_2 = (r_2-r_2') / (c-c') x_1/x_2 = (r_1-r_1') / (r_2-r_2') We will build a scheme where x_1/x_2 is Alice's ID. Because we are going to have the bank perform blind signatures, x_1 and x_2 on their own will be randomly-distributed, but we can build a blind signature scheme where x_1/x_2 is fixed! Anonymous E-cash (Stefan Brands) [Keep setup variables on the board] Plan: use two generators to represent a coin Setup: public: p=2q+1, p and q prime public: g, g_1, g_2, generators of G_q (unknown pairwise DLs) Bank: private key: x \in Z_q public key: g_1^x, g_2^x, g^x (denote h=g^x) User: private key: i \in Z_q public key: I = g_1^i z = (I g_2)^x = g_1^(ix) g_2^x Coin: { A, B, Sign(A, B) } A = (I g_2)^s s is the blinding factor picked by user B = g_1^{x_1} g_2^{x_2} Sign(A, B) is bank's blind signature (with key x); described later Payment step Alice Merchant { A, B, Sign(A, B) } --------------------------------------> d = Hash(A, B, M, date/time) <-------------------------------------- r_1 = d*(is) + x_1 r_2 = d*s + x_2 --------------------------------------> Verify Sign(A, B) g_1^{r_1} g_2^{r_2} = A^d B Effectively, Alice convinces M that it knows rep. of A, using B as the "random" first-step value in knowledge protocol. Because B is fixed (signed by bank), reuse is required. So, in case of double-spending: r_1' = d'*(is) + x_1 r_2' = d'*s + x_2 i = (r_1-r_1')/(r_2-r_2') I = g^i, bank knows this is Alice's public key Deposit step Merchant forward to the Bank: { A, B, Sign(A, B) }, r_1, r_2, date/time What checks does the bank perform? verify the payment step again, using supplied date/time, and M's name this ensures legal coin, merchant really did receive the coin from user How to tell if the user double-spent? if the coin already exists in database with different r_1/r_2 If the merchant double-deposited? if the coin already exists in database with same r_1/r_2 Withdrawal step (almost) define a signature as follows: [keep on board] Sign(A, B) == (z, a, b, r) \in G_q x G_q x G_q x Z_q, such that if we let c denote H(A,B,z,a,b), then g^r = a*h^c, and A_r = b*z^c Alice Bank random w in Z_q a = g^w b = (I g_2)^w <--------------------------------------------------- choose random x_1, x_2 in Z_q A <- (I g_2) B <- g_1^{x_1} g_2^{x_2} c <- H(A,B,z,a,b) c ---------------------------------------------------> r = cx + w <--------------------------------------------------- Check that (z, a, b, r) is a valid signature for coin (A, B): g^r = a*h^c A^r = b*z^c Blind withdrawal step To construct a valid signature on a coin that the bank can't identify, Alice will compute c in a different way: choose random s in Z_q^* choose random u, v in Z_q A' <- A^s z' <- z^s a' <- a^u g^v b' <- b^{su} A'^v c' <- H(A', B, z', a', b') c <- c'/u (mod q) Then, after bank returns r=cx+w: r' <- ru+v (mod q) Thm: coin (A', B) is indistinguishable by bank from other coins. Proof: bank never saw B A' is uniformly-distributed because s is random if rep. problem is hard, can't figure out exponents from A' Thm: Alice is still identifiable from the rep. of A'. Proof: A = g_1^i g_2 A' = (g_1^i g_2)^s = g_1^{is} g_2^s ratio of exponent of g_1 to exponent of g_2 is still i Thm: (z', a', b', r') is a valid signature for coin (A', B). Proof: g^r' =? a'*h^c' A'^r' =? b'*z^c' Proof that signature is unforgeable, and that all blindings necessarily result in the right ratio of exponents, is omitted for space. See the tech report by Brands for more details.