«Payment Systems (Ch. 17 of Course Material “Security”) Birgit Pfitzmann Dept. of Computer Science Saarland University pfitzmann ...»
17.5.2 Basic Ideas for Systems with Doublespender Identification Now we consider systems that are anonymous but where doublespenders can be identified and punished. As mentioned in Section 17.1.1.D, this could also be combined with tamper resistance so that doublespending becomes hard in the first place.
A. Basic Ideas The systems are based on the coin concept (the anonymous standard values are even more intrinsically an online system). If a simple coin system were used offline, the bank could see afterwards that a coin was spent several times, but how can it react if the coins are anonymous?
The idea in [ChFN_90] was to take cryptographic measures such that doublespenders are no longer anonymous. For this, two payments with the same coin (and the subsequent deposits) must actually give the bank more information than one payment — otherwise it would be impossible that one is anonymous after one payment, but no longer after two. This is done by a challenge-response mechanism: In each payment, the recipient asks a question and the payer has to send a certain answer, see Figure 17.5. With one such answer, the payer is still anonymous, but answers to two different questions identify him.
The answers can only reveal the identity if the identity is somehow encoded into the coin in the first place, i.e., during the withdrawal where the bank can verify this. If we keep the informationtheoretic anonymity, the identity can no longer be present in the transformed coin in a strict sense, because every paid coin should in principle fit to every withdrawal. However, the payer will need to “know” something about a coin for paying (somewhat like the secret coin key in Section 17.3.3).
This knowledge will still be linked to the identity.
Version 23. März 2000 17 Payment Systems 29
Figure 17.5 Basic ideas for doublespender identification B.
On the Challenges One more problem can be considered abstractly: What happens if a payer and two recipients collude and pose the payer the same challenges, i.e., C* = C? The bank can certainly not give the money to both recipients in the deposit. One could say that only the first recipient who deposits gets the money.
But then a payer and Recipient 2 could cheat Recipient 1 by reusing C and depositing faster.
Therefore each challenge will include the recipient’s identity, and deposit will only be possible to the account of this recipient. (This is a special case of the coin key mechanism from Section 17.3.3: The response is at the same time a signature on the recipient’s identity.) C. Realization Ideas for the Responses A first idea what to use as responses would be that the first answer R is a one-time pad k, and the second answer is R* = id ⊕ k. Then obviously each answer alone gives no information about id, but both answers reveal id in full. However, this would only allow two challenges.
The next idea is that a response is a linear equations in two variables, one of which is id, e.g., c1id + c2k. This give al large set of possible challenges (c1, c2). Then one response still leaves every id possible, while two equations determine both variables uniquely (assuming the equations are linearly independent.) This idea is from [FrYu_93]. Essentially, it is also used in Brands’ system, which we describe below. Only there, each response gives two equations in four variables — this allowed Brands to come up with an efficient verification whether the responses are correct.
17.5.3 Brands’ System Brands’ system is the best-known anonymous offline system because it is quite efficient. It is not provable, just like any other of these efficient systems.
It uses a blind signature scheme based on discrete logarithms, an extension of the ChaumPedersen scheme [ChPe1_93], which can be seen as an extension of Schnorr signatures. We already Version 23. März 2000 17 Payment Systems 30 saw Schnorr signatures in Section 6.4.2.E.γ. However, for understanding the following modifications, it is useful to reconsider the Schnorr’s system from another point of view.
A. Schnorr Signatures Revisited Recall that key generation for Schnorr signatures results in a group Gq of order q, say a subgroup of Z p*, a generator g of Gq, a secret key x ∈ Z q, and h = gx as the main part of the public key. The Z Z signature scheme was originally invented as a variant of an identification system. In the identification system, the owner of x simply “proves that he knows x”. (More details on what this means below.) The proof protocol is shown in Figure 17.6.
Figure 17.6 Schnorr identification protocol The idea is the following, and this will be the same in the modified protocols: In Step 1, the owner of the secret, here x, chooses another secret of the same form, here w.
It will more or less serve as a one-time pad for x. He also computes the equivalent of the public value (here h) with w; here this is a = gw.
In Step 2, the verifier sends a challenge c.
In Step 3, the prover has to respond with a linear combination between x and w (his real secret and his one-time secret) determined by c. The verifier can test whether this linear combination is correct by verifying its homomorphic image for the public values: If all was correct, then gr should be gw+cx = gw(gx)c = a hc.
Remark. In an even more basic protocol from [ChEG_88], the challenge c is only one bit, but then one has to repeat the protocol several times. The advantage is that the security is more provable (a stronger property called zero-knowledge then holds instead of the informal Property 2 below).
Security ideas. We would like the identification protocol to have two properties. Both cannot be
defined formally in the available space and time (see the course on higher cryptographic protocols):
1. “Proof of knowledge”: If a prover can successfully pass the verification with significant probability, then he must “know” x.
In our case, the proof idea is the following: Consider a prover that has sent a. Assume that he can answer at least two out of the many possible challenges c that he might now get. Let these challenges be c1 and c2 and the answers that he would send be r1 and r2, respectively. The values x and w are uniquely defined as the discrete logarithms of h and a. By Proposition 1 from Section 5.5.1, r1 and r2 pass the verification only if in fact Version 23. März 2000 17 Payment Systems 31 r1 = w + c1x and r2 = w + c2x (mod q).
Hence, from (c1, c2, r1, r2) one can easily compute x by solving this equation system, i.e., (r1 –r2) = (c1 – c2)x mod q.
This counts as having known x. (This was only a sketch because, e.g., the probabilities were not considered and the question why “being able to compute” is a suitable notion of “knowledge”.)12 2. “No useful knowledge leaks”: Even if the prover carries out many such proofs, this will not make it easier for the recipient to find out x or do other useful things with x. The basic idea here is that for any specific c, the value w is a one-time pad on x in the response r that the attacker gets.
However, this is not a real proof, since w is not completely hidden because a also belongs to the attacker’s view.
Signatures from identification protocols. There is a general trick by Fiat and Shamir to transform 3-step identification protocols where the verifier only sends a random challenge c into a signature scheme [FiSh_87]. However, the quality of the trick is not proven.
The trick is that the signer computes c himself as c = hash(m, a), where m is the message to be signed and hash a hash function that is at least one-way. The hope is that the hash function is somehow pseudorandom, so that the resulting c is as good as the real random c in the identification protocol. However, this is only a heuristic because hash is public (otherwise the signature could not be tested), and thus of course anyone can distinguish it from a real random function.
The signature test is now gr = a hc for c = hash(m, a).
Remark (Comparison with the presentation in Section 6.4.2): Instead of sending a and r and letting the recipient recompute c, one can also send c and r and let the recipient recompute a as hc/gr and then verify the hashing. The version in Section 6.4.2 corresponds to this: The triple (z*, r, s) there is our (w, c, r). The remaining difference is that Schnorr used a “–” instead of a “+” in Step 3.
B. Chaum-Pedersen Signatures Without Blinding As a second step, we consider Chaum-Pedersen signatures without blinding. This protocol is shown in Figure 17.7. The changes with respect to Figure 17.6 are highlighted.
Figure 17.7 Chaum-Pedersen signatures, interactively and without blinding The main novelty is the value z = mx in Step 0.
We call it a signature commitment on m because, like a signature, it can only be computed with the secret key; however the recipient cannot verify its correctness on his own. The rest of the message exchange is intended to convince the recipient that z is correct.
This proof is exactly of the same structure as above: In Step 1, the random variant w of x is chosen. As there is now an additional public value z based on x, there is also a similar value b based on w. In Step 3, the verification is done both for the powers of g (Line 1) and for the powers of m (Line 2).
The security considerations are as before. In particular, if one can answer two challenges for the same a and b, one can again easily compute a value x such that both h = gx and z = mx hold. Thus the protocol proves both that the sender “knows” x and that z is correct.
Finally, one can again replace the random c by a hash value c = hash(m, z, a, b).
The general rule is to use all the values from the previous steps as the inputs to hash.
C. Blind Chaum-Pedersen Signatures Now we add the steps where the recipient transforms the signature. Compared with Figure 17.4, the message m will be the white form of the coin and m’ the striped form. The blind signature is the values that are sent, i.e., σ = (z, a, b, c, r) and the unblinded signature is σ’ = (z’, a’, b’, c’, r’). The idea that makes only the striped form valid for paying is that only in that form, c’ = hash(m’, z’, a’, b’) will hold. Again the changes to the previous protocol are highlighted.
Version 23. März 2000 17 Payment Systems 33
• Security against one-more forgery: Here nothing is really known. We simply have to assume that it is impossible to get more valid signatures than the number of blind signing protocols one executes. The basic idea is that one hopes that although one might be able to manipulate all the other values in different ways, one will not end up with c’ = hash(m’, z’, a’, b’) except by choosing everything exactly in the order as above.
Blindness: Here we show that any message with a valid signature (m’, σ’) fits any view (m, σ) • that the signer gets in a blind signature protocol. This will later mean that any coin could result from any withdrawal protocol. The proof is again by the sufficient criterion for the general secrecy formula, see Section 6.1.1.B: First, the blinding factor quadruples (s, t, u, v), which play the role of the key, are uniformly distributed. Secondly, we show that for each pair ((m’, σ’), (m, σ)) there are exactly q blinding factor quadruples that transform (m, σ) into (m’, σ’).
Figure 17.9 Situation for the blindness proof: A signer has given many blind signatures.
One of them, (m’, σ’) is now shown to another party. We want to prove that it could come from any of the executions of the signing protocols, e.g., that where the signer’s view was (m, σ).
We first show that there are at most q solutions:
• First u can only be c’ /c (see Step 2).
• Then v can only be r’ – ur (see Step 3).
• Now we write m as gα and m’ = gβ. Then m’ = msgt means β ≡ αs + t mod q. This equation has q solutions for (s, t).
In the rest of the proof, we show that each of these tuples (s, t, u, v) indeed leads to exactly the signature σ’. (It is clear by construction that it leads to the same m’.) Fix such a tuple and call the resulting signature σ” (because we must have a name for it as long as we haven’t finished the proof that it equals σ’).
We first show that a, b and z in any protocol run where the recipient accepts are of the correct
form (except with negligible probability) although the signer may be among the attackers:
Version 23. März 2000 17 Payment Systems 35 We can assume that z = mx because the protocol proves this fact. (Actually, here is a gap in the • proof that nobody seems to have noticed before: It was only shown that the protocol proves this fact if hash is random-like. Now, however, we would like a real information-theoretic argument, and this does not seem to be true. Probably a rather weak assumption on hash is sufficient for what we need here, though.) As to a, we simply define w such that a = gw.
• Now let b = gw*. Then indeed w* = w because the recipient verifies gr = ahc and mr = bzc, • which is equivalent to r = w + xc and r = w* + xc mod q.
Given this, the proof of the correctness implies that the signature σ” is constructed like a correct σ starting with the values m’ and w’ = wu + v. Similarly, σ’ was constructed in some withdrawal (probably not the one we currently consider) from the same m’ with a value w’0. Thus, to show that σ” = σ’, it is sufficient to show that w’0 = w’. We have w’ = wu + v = wu + r’ – ur = r’ + u(w – r ) = r’ + (c’/c)(w – w – xc ) = r’ – c’x.
By the correct construction of σ’ from w’0, we therefore obtain w’ = (w’0 + c’x) – c’x = w’0.
• Blindness for t = 0. We easily see in the proof above that among the q solutions, there is always exactly one with t = 0 unless α = 0, i.e., as long as we exclude m = 1. This will be important in Brands’ applications where honest recipients always use t = 0. So we still have information-theoretic anonymity in that case.
E. The Complete System Now we put all the parts together and fill in the actual payment protocol.