«Payment Systems (Ch. 17 of Course Material “Security”) Birgit Pfitzmann Dept. of Computer Science Saarland University pfitzmann ...»
For each unit to pay, the payer simply sends the next preimage in the chain to the merchant. Hence the payer keeps a counter i initialized with 0, and in the i-the micropayment he sends sigi := fx–i(sk).
To avoid having to recompute this from sk in each micropayment, he may either store the complete chain or make a time-memory tradeoff, e.g., by storing every 10th value initially, and then always recomputing chains of length 10.
The recipient always has to store the previous value sigi–1 he got, and he verifies the next value sigi via “is f(sigi) = sigi–1.
Version 23. März 2000 17 Payment Systems 16 17.3 Anonymous Online Systems The best-known subclass of anonymous online systems is what is now called ecash-like systems, see Section 17.3.3. They are also called coin-like online cash systems. However, we will first look at a weaker form of anonymity, anonymous accounts, and then at another system that achieves a rather similar form of anonymity with fewer cryptographic tricks.
17.3.1 Anonymous Accounts Anonymous accounts are just like non-anonymous accounts, except that they are not linked to a real identity, and that the bank will not allow the balance on such accounts to drop below zero.
Account opening: To open an anonymous account, a person simply generates a key pair of a signature scheme, (sk, pk) ← gensig(l), and sends pk to the bank; pk is called a pseudonym. No prior certificates are needed for the key pair.
The bank assigns an account number N and certifies this fact, e.g., with sign(skBank, (“Account opened”, N, pk)).
Payment between anonymous accounts: The recipient R tells the payer his account number NR. Now any of the non-anonymous message flows is possible. For instance, the payer can send the
bank a signed transfer order with a sequence number:
sign(sk, (“transfer”, N, NR, seq_no, amount)).
Money can be paid into such an account with any normal cheque, cash or transfer order. To take it out again, a signature with sk is needed, similar to the one above.
Relative to the person’s normal account, such a system is prepaid: There are withdrawal and deposit transactions. However, the bank could pay interest for money on anonymous accounts. If one only considered anonymous accounts, the system would count as pay-now. The loss-tolerance problem of prepaid systems exists in a minimal form: If one loses the secret key sk, one loses access to the account, and one cannot prove ownership in another way unless one has taken specific precautions.
The degree of anonymity is low, because all transactions on one account are linkable. On the other hand, both payers and recipients are anonymous. Note that an anonymous “Geldkarte” can be seen as a symmetric analog of this scheme.
17.3.2 Anonymously Transferable Standard Values The scheme in this section is from [BüPf_89], Section 4.4. It was reinvented in [Simo_96] and patented by Microsoft, but the patent must be invalid given the older publication. A standard value is like a “one-time” account whose ownership is transferred with its value, to avoid the linkability of the scheme in Section 17.3.1.
We will immediately look at a payment, assuming the payer already has a standard value v (where v is a number, like a banknote number).
Version 23. März 2000 17 Payment Systems 17
1. The recipient chooses a new key pair (skR, pkR ) ← gen sig(l). We call pkR a pseudonym. He sends the payer a message like “I want to receive standard value v for purpose Z under the pseudonym pkR” and signs it with a key that is already known to the payer. (This is a precaution for later disputes whether the recipient got the money.)
2. The payer sends a transfer order to the bank, e.g., sign(skP, (“transfer standard value”, v, “to”, pkR)).
The secret key skP used is from the key pair the payer chose when receiving v, i.e., from Step 1 of the previous transfer.
3. The bank looks v up in a database and retrieves the public key pkP of the current owner. It verifies that the transfer order is correct and signed with respect to this key. If moves pkP to a list of former owners of v and stores the transfer order (again as a precaution for later disputes). Finally, it enters pkR as the public key of the current owner.
The bank signs a transfer confirmation, e.g., sign(skBank, (“new owner of”, v, “is”, pkR)), and sends it to the payer, who forwards it to the recipient.
If the recipient does not obtain this confirmation, he contacts the bank himself to see if the transfer of v to his pseudonym went through.
4. Receipt: In a correct protocol execution, the recipient R confirms the payment under the pseudonym or name under which P knows him. However, if R refuses, P can use the bank’s confirmation from Step 3 together with the recipient’s message from Step 1 to prove that he transferred the money to a pseudonym of the correct recipient.
Depositing a standard value to a normal account is done with a similar message as in Step 2.
Withdrawing a standard value from the bank for normal money can be realized as a payment from the bank, who entered itself as the initial owner of v, to the first real owner.
In this scheme, both payers and recipients are anonymous, and payments of the same person are not linkable. However, there is a certain link between all the payments with the same standard value v, just like with current banknote numbers.
17.3.3 Schemes with Blind Signatures This class contains the best-known anonymous payment schemes, those which are typically called coin schemes. However, the “coin” terminology is unclear. One could almost better call a standard value from Section 17.3.2 a coin. (For example, both schemes are online in contrast to real coins, and the standard values are transferable and anonymous for both parties like real coins.) The really distinctive concept in this section is that of blind signatures.
A well-known product in this class is e-cash (from the former company DigiCash), which realizes the scheme with payer anonymity and non-anonymous accounts as described in Subsections A and B below. Several banks, among them Deutsche Bank, made a field trial with it. Most of the ideas in this section are from [Chau_83, Cha8_85, Chau_89] (a first sketch, a well-known overview, and the full Version 23. März 2000 17 Payment Systems 18 paper). The coin keys and general dispute security, and the scheme with maximum anonymity are from [PWP_87].
The scheme was originally invented for shop scenarios and thus anonymous communication was no problem; e-cash, however, is for an Internet scenario.
The basic concept is shown in Figure 17.4: A bank somehow gives a coin, which is a signed message, to a payer, and the payer can somehow transform the coin before giving it to a recipient.
The recipient then deposits it. Because of the transformation, the bank cannot link which deposited coin corresponds to which withdrawn coin. Thus it cannot find out who paid to whom.
Figure 17.4 Basic concept of an online system with blind signatures A.
Basic System in Abstract Form Now we show the basic version of this system in more detail, but still in abstract form. This basic version is prepaid and deposit-now, and it provides
• payer anonymity with unlinkability,
• no recipient anonymity, and
• no security in disputes.
An overview is given in Figure 17.5.
• Setup: Some parameters have to be distributed initially by the bank.
1. The payer generates a coin coin with an operation gencoin (probabilistic and based on parameters from the setup). This is the form later used in the payment (striped in the figure).
2. He transforms it with an operation blind. We call the result blindcoin (white in the figure).
3. He sends the blinded coin to the bank together with a withdrawal order stating what amount he wants, e.g., 1 Euro, and from which account.
4. The bank subtracts the amount from the account and signs blindcoin with a special key belonging to this amount.
5. The bank sends the resulting signature, sigblind, back to the payer, who tests it.
Version 23. März 2000 17 Payment Systems 19
• Payment with deposit:
6. The payer uses an operation unblind on the signature so that the result sig fits the original (striped) coin. He needs stored parameters from blind for this.
7. He sends (coin, sig) to the recipient.
8. The recipient simply forwards this to the bank to make an on-line verification against doublespending. (He could verify the signature, but it makes no difference.)
9. The bank verifies the signature and checks in a database that this coin was not deposited before. If all is ok, it enters the coin there and adds the amount to the recipient’s account.
10. The bank tells the recipient the result of the tests.
11. If it was ok, the recipient typically signs a receipt or gives the payer goods.
Figure 17.5 Abstract representation of basic blind RSA signatures Note where the inputs and outputs from Figure 17.
2 occur: withdraw triggers Step 1; allow is needed in Step 4, and subtract also occurs there. Later, pay triggers Step 6, and if the recipient has to enter receive, it is needed in Step 8. Then add occurs in Step 9, and ok to the recipient in Step 10. An ok to the payer at the end is not provided in the basic system, because the receipts are already an extension.
(Without receipts, this ok would come in Step 6 when the device finds that it indeed has a coin.)
Two non-cryptographic issues are important for real-life anonymity:
• Payers should typically wait some time before using a withdrawn coin. Otherwise the bank can link withdrawals and deposits simply by their relation in time.
Version 23. März 2000 17 Payment Systems 20
• There should not be too many different amounts, because anyone paying with a certain coin is only anonymous among all people who have withdrawn coins of the same amount at the same bank.
The coins would typically have a limited validity (some months or years) to limit the problems if signature forgery becomes easier, and to limit the size of the coin database. This database is large, but not infeasible. In other payment systems, there is one record per payment, and here one per coin used in a payment, i.e., about a factor of 5 more.
Passive attacks: Let us first consider only passive attacks, in particular the bank carries out its protocols correctly. Then each signature sig or blindsig is uniquely determined by coin or blindcoin, respectively, and hence we only need to consider the coins. (The signatures give no additional information.) Consider any values blindcoin and coin. They can belong together if there exists r such that eB blindcoin = coin • r mod n.
e d This is equivalent to r B = blindcoin / coin, and thus r = (blindcoin / coin) B. Hence there is precisely one such r for every pair, except if coin has no inverse mod n, which happens only with exponentially small probability. The result corresponds to the sufficient criterion for the generic
secrecy formula in Section 6.1.1B:
1. The “key”, here the blinding factor r, is random and uniformly distributed.
2. For every possible secret, here the blinded coin, and every observation, here the unblinded coin, there exists exactly one key r such that they can belong together.
Active attacks: Now let us consider active attacks. They can only come from the bank, which could choose a wrong n and e B and give wrong signatures. We show that if it does, this can almost certainly be detected soon.9 First we can see that as long as gcd(eB, φ(n)) = 1, exponentiation with eB is still a permutation (similar to the proof for correct RSA keys). In this case, the test in Step 5 of the withdrawal still guarantees that signatures are unique, and we still only need to consider the coins. The rest of the proof is also still valid, except that if n has more prime factors, the probability that coin is not invertible may increase. Here a test of gcd(n, coin) could be inserted, or someone could run trial division and try to find small factors of n.
If g := gcd(eB, φ(n)) ≠ 1, the payers cannot notice this directly (except if 2|eB, which we can e exclude). However, one can then see that every value x B has g roots (similar to the proof that squares have two roots in Section 6.6.4), and thus at most 1/g of all values coin have an eB-th root. If one assumes that these values were uniformly distributed (which is not quite true because of the hash function), this means that the bank will in more than half the cases not be able to sign a coin, which will be noticed very fast.
Unforgeability? A minimum requirement is that the bank does not lose money in a payment system. For example, if someone could existentially forge RSA signatures with the given redundancy predicate in a passive attack, this would not be fulfilled. As such security is not proven for RSA under a normal assumption, the entire security of this payment system is certainly not provable at the moment.
What one would need to prove is so called “one-more unforgeability”. This means that no probabilistic polynomial-time attacker who carries out k blind signing protocols (withdrawals) with the signer (bank) can afterwards present k + 1 valid signatures with significant probability. This has not been proven for any efficient scheme under a normal assumption yet. A very inefficient provable
scheme was presented in [PfWa2_92], a rather efficient scheme provable in the so-called randomoracle model (which is a heuristic, but better than nothing) in [Poin_98].
C. Adding Security in Disputes Now we want to provide secure for disputes between the bank and a payer or recipient. Such disputes can in particular occur if the clients say that their statements of account are not correct, i.e., either a withdrawal (the output subtract) appears there but they did not get the corresponding coin, or a recipient misses a deposit (the output add). Another possibility is that the bank refuses to accept a coin in Step 9, but the payer claims that he never spent that coin before.