«Payment Systems (Ch. 17 of Course Material “Security”) Birgit Pfitzmann Dept. of Computer Science Saarland University pfitzmann ...»
Bank setup. The bank generates keys for the Chaum-Pedersen blind signature scheme, i.e., p, q, g, x, and h = g x where x is secret and the rest is published. More precisely, for different denominations it would use the same p, q, and g, but different values xj and hj, but we will omit the index j in the following. Moreover, expiration dates may be associated with these keys, i.e., coins signed with those keys are only valid for a certain time.
The bank also generates two further random generators g1 and g2. Everybody has to trust that even the bank cannot compute discrete logarithms with respect to g1. In practice, one might believe that this is true even if the bank chooses p, q and g1 arbitrarily. However, one can also guarantee their randomness by using an arbitrary trusted random string r (typically taken from old tables of random numbers) and generating the desired values from r using a standardized deterministic procedure. In particular, g1 is then chosen as r1(p–1)/q where r1 is a substring of r interpreted as an element of Z p*.
Z Opening an account. This protocol is executed once for each new payer. “Opening an account” is the usual name, but in reality one would probably use a normal bank account, and this is just a specific registration phase for this payment system.
0. For secure electronic withdrawals, we have to assume that the payer has a key pair (skP, pkP) of an arbitrary signature scheme with which he can authorize actions regarding his bank account.
This pk P may also be registered at this moment or may already exist, e.g., from a standard homebanking protocol.
1. The payer chooses a secret random number id mod q and gives h1:= g1id to the bank. We call id the identity proof of this payer. If another payer already uses h1, the bank asks the current payer to repeat his choice.
2. The payer proves to the bank that he knows id with h 1= g 1id. For this, they use the Schnorr identification protocol; see Figure 17.6.
3. The payer signs (using skP) that m = h1g2 will be used for his withdrawals. If the bank can later show the value id with g1idg2 = m, this will count as a proof that a coin from this payer was spent twice.
Registering as a recipient. As mentioned in Section 17.5.2A, each recipient must use a different challenge. Thus it is useful if he registers under a specific digital identity IdRecipient. However, recipients do not need keys for this system.
Withdrawal. For one payer, the bank always blindly signs the same message m which was agreed upon above. The protocol is that from Figure 17.8 with the following addition:14
• The payer generates two additional secret numbers y1, y2 mod q.
Together with (x1, x2) they are the four secret variables about which each payment will reveal two linear equations. At the same time, one can see (x1, x2, y1, y2) as a secret coin key skcoin with which the payer, as the anonymous owner of this coin, can later sign to whom he wants to pay it. (Compare the measures for secure disputes about deposits in Section 17.3.3.) y y He sets pkcoin := g1 1g2 2.
• xx Recall that also m’ = g1 1g2 2. Together, the values (m, pkcoin) can be seen as the public coin key corresponding to skcoin.
• To fix which pkcoin belongs to which coin, this value is included in the hashing process in Figure 17.8, i.e., the challenge is actually computed as c’ := hash(m’, pkcoin, z’, a’, b’).
For security in disputes about a withdrawal, the payer should sign (using skP) a withdrawal order including the desired denomination of the coin and the value c’ for which he wants a response. This withdrawal order must be sent together with Step 2 of the blind signature protocol.
We call the result of a withdrawal coin’ = (m’, pkcoin, σ’) with σ’ = (z’, a’, b’, c’, r’).
Here m’ is called the coin identifier and σ’ the coin signature.
Payment. First the payer sends coin’, whose components are named as above, and the recipient verifies that it is correctly signed with a Chaum-Pedersen signature. The rest of the payment protocol follows the ideas described in Section 17.5.2, in particular that each response reveals two linear
The resulting protocol is shown in Figure 17.10.Here, hash’ is another hash function. The value nonce stands for any freshness measure that guarantees to this recipient that he won’t accept that same coin twice with the same challenge.
Figure 17.10 Brands’ payment protocol Deposit and Doublespender Identification.
In a deposit, the recipient forwards all his information from a payment, including IdRecipient and nonce.
1. The bank first verifies the validity of the coin just as the recipient did in Steps 1 and 3 of the payment.
2. Secondly, it detects double-spending or double-depositing by entering the coin into a data structure cointable, say a hash table, for comparison with previous deposits by other recipients.
This can be done offline. Coins stay in this table until they expire.
• If the coin is already there, the bank checks whether the recipient and nonce were the same or not. If yes, the recipient double-deposited and has to pay back.
• If not, and unless someone found a collision of the function hash’, the two challenges C and C* are also different. If the coin is already in the table, the bank retrieves the corresponding responses R and R*, computes the identity proof as id = (sig1 – sig*1)/(sig2 – sig*2) and looks up to which payer m = g1idg2 belongs.
Version 23. März 2000 17 Payment Systems 39
• On punishment: Note that you cannot find out how many coins where doublespent. This could be changed by using a different id for each coin, but still one could not prove how often a coin was spent so one cannot exactly prove how much damage the payer caused. (One could check how many different signatures with this coin key exist, but once that payer made two such signatures, the secret coin key can be found out and thus the recipients could also take the opportunity and make additional payments with this coin.)
• On proofs: Given the restrictiveness assumption and assumptions that protocols using hash functions instead of random challenges are still proofs of knowledge, it should be possible to prove higher-level properties of the protocol, but we don’t do this now.
• On implementations: A system that was essentially based on Brands’ payment system was implemented in the project CAFE [BBCM1_94].
Version 23. März 2000 Literature 40 Literature AASW_98 Jose. L. Abad-Peiro, N. Asokan, Michael Steiner, Michael Waidner: Designing a generic payment service; IBM Systems Journal 37/1 (1998) 72-88.
AJSW_97 N. Asokan, Phillipe A. Janson, Michael Steiner, Michael Waidner: The State of the Art in Electronic Payment Systems; Computer 30/9 (1997) 28-35.
BBCM1_94 Jean-Paul Boly, Antoon Bosselaers, Ronald Cramer, Rolf Michelsen, Stig Mjølsnes, Frank Muller, Torben Pedersen, Birgit Pfitzmann, Peter de Rooij, Berry Schoenmakers, Matthias Schunter, Luc Vallée, Michael Waidner: The ESPRIT Project CAFE — High Security Digital Payment Systems; ESORICS 94 (Third European Symposium on Research in Computer Security), LNCS 875, Springer-Verlag, Berlin 1994, 217-230.
BüPf_89 Holger Bürk, Andreas Pfitzmann: Digital Payment Systems Enabling Security and Unobservability; Computers & Security 8/5 (1989) 399-416.
BüPf_90 Holger Bürk, Andreas Pfitzmann: Value Exchange Systems Enabling Security and Unobservability; Computers & Security 9/8 (1990) 715-721.
Cha8_85 David Chaum: Security without Identification: Transaction Systems to make Big Brother Obsolete; Communications of the ACM 28/10 (1985) 1030-1044.
Chau_81 David Chaum: Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms;
Communications of the ACM 24/2 (1981) 84-88.
Chau_83 David Chaum: Blind Signatures for untraceable payments; Crypto '82, Plenum Press, New York 1983, 199-203.
Chau_89 David Chaum: Privacy Protected Payments – Unconditional Payer and/or Payee Untraceability; SMART CARD 2000: The Future of IC Cards, IFIP WG 11.6 International Conference, Laxenburg (Austria) 1987, North-Holland, Amsterdam 1989, 69-93.
ChEG_88 D. Chaum, J.-H. Evertse, J. van de Graaf: An improved protocol for demonstrating possession of discrete logarithms and some generalizations; Eurocrypt '87, LNCS 304, Springer-Verlag, Berlin 1988, 127-141.
ChFN_90 David Chaum, Amos Fiat, Moni Naor: Untraceable Electronic Cash; Crypto '88, LNCS 403, Springer-Verlag, Berlin 1990, 319-327.
ChPe1_93 David Chaum, Torben Pryds Pedersen: Wallet Databases with Observers; Crypto '92, LNCS 740, Springer-Verlag, Berlin 1993, 89-105.
EvGY_83 Shimon Even, Oded Goldreich, Yacov Yacobi: Electronic wallet; Crypto '83, Plenum Press, New York 1984, 383-386.
FiSh_87 Amos Fiat, Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems; Crypto '86, LNCS 263, Springer-Verlag, Berlin 1987, 186-194.
FrYu_93 Matthew Franklin, Moti Yung: Secure and Efficient Off-Line Digital Money; 20th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 700, Springer-Verlag, Berlin 1993, 265-276.
HBCI_99 Homebanking Computer Interface - HBCI (Version 2.1); Zentraler Kreditausschuß, March 1999 (http://www.siz.de/siz/hbcispec_e/hbcisp_e.htm).
Pede_97 Torben P. Pedersen: Electronic Payments of Small Amounts; Security Protocols 1996, LNCS 1189, Springer-Verlag, Berlin 1997, 59-68.
PfWa_96 Birgit Pfitzmann, Michael Waidner: Properties of Payment Systems: General Definition Sketch and Classification; IBM Research Report RZ 2823 (#90126) 05/06/96, IBM Research Division, Zurich, May 1996.
Version 23. März 2000 Literature 41 PfWa2_92 Birgit Pfitzmann, Michael Waidner: How to Break and Repair a "Provably Secure" Untraceable Payment System; Crypto '91, LNCS 576, Springer-Verlag, Berlin 1992, 338-350.
Poin_98 David Pointcheval: Strengthened security for blind signatures; Eurocrypt '98, LNCS 1403, Springer-Verlag, Berlin 1998, 391-405.
PWP_87 Birgit Pfitzmann, Michael Waidner, Andreas Pfitzmann: Rechtssicherheit trotz Anonymität in offenen digitalen Systemen; Computer und Recht 3/10,11,12 (1987) 712Überarbeitung und Erweiterung erschien in zwei Teilen in Datenschutz und Datensicherung DuD 14/5-6 (1990) 243-253, 305-315.
Simo_96 Daniel Simon: Anonymous Communication and Anonymous Cash; Crypto '96, LNCS 1109, Springer-Verlag, Berlin 1996, 61-73.
Version 23. März 2000 Index 42