On Sun, 22 Oct 1995, Bryce wrote:

Now it seems to me that any ecash scheme, whether cleared on-line or off-line, with or without double-spending-detection, will put the payee at risk of identification by a collusion of the payer and the

I can't remember off hand, but isn't blinding transitive? If so, there's an obvious way to get two way anonymity with an on-line system. If Alice wants to pay Bob $10, then Bob could prepare the usual squillion copies of the note, each with a serial number known only to Bob, then blind them and send them to Alice. Alice would then reblind them and send them to Nick, the banker. Nick would then pick one of the notes, and ask Alice for the blinders for the rest. Alice would then ask Bob for his blinders for the rejected notes, and would forward both sets on to Nick, who would check them, and if they're legit, sign the remaning copy, and return it to Alice. Alice cound then remove her blinding factor, and sent the result on to Bob. Bob then removes his blinding factor, and can now spend the coin. Since Alice doesn't know the serial number, she can't reveal it to Nick so that he can find out who deposits the coin. Also, since Nick doesn't know the serial number, he can't collaborate with Bob to find out who Alice is. Does this work, or am I missing something? Simon --- (defun modexpt (x y n) "computes (x^y) mod n" (cond ((= y 0) 1) ((= y 1) (mod x n)) ((evenp y) (mod (expt (modexpt x (/ y 2) n) 2) n)) (t (mod (* x (modexpt x (1- y) n)) n))))

In article <DGxFBL.753@sgi.sgi.com>, Hal <hfinney@shell.portal.com> writes:

"Simon Spero" <ses@tipper.oit.unc.edu> wrote:

...

...

If so, there's an obvious way to get two way anonymity with an on-line system. If Alice wants to pay Bob $10, then Bob could prepare the usual squillion copies of the note, each with a serial number known only to Bob, then blind them and send them to Alice.

Alice would then reblind them and send them to Nick, the banker. Nick would then pick one of the notes, and ask Alice for the blinders for the rest. Alice would then ask Bob for his blinders for the rejected notes, and would forward both sets on to Nick, who would check them, and if they're legit, sign the remaning copy, and return it to Alice. Alice cound then remove her blinding factor, and sent the result on to Bob. Bob then removes his blinding factor, and can now spend the coin.

This is an interesting idea but it is more complicated than necessary, I think. The denomination can be carried in the exponent, in which case there is no need for cut and choose and nobody can cheat the bank. A coin suitable for deposit is a signed number of some special form. To pay Bob, Alice does not withdraw anything ahead of time. Rather, Bob gives her a blinded coin, which she reblinds and gives to the bank. The bank signs it (debiting Alice's account) and gives it back to her. She strips off her blinding and gives it to Bob. He strips off his own blinding and verfifies that he is left with a signed number of the appropriate form.

This system is in some ways the inverse of regular ecash. Instead of Alice withdrawing a coin ahead of time, and Bob checking it with the bank right away, it is Alice who does the bank interaction at payment time, and Bob who waits before interacting with the bank. The computational and communications costs do not seem much worse than ecash.

There is no way Alice can double-spend because she cannot anticipate Bob's blinding factor and give him a previously-spent coin which will unblind to the proper form. There could be an issue of fraud, though, where Bob insists that Alice's coin was no good even though it actually was. Since he has blinded it she will have no way of recognizing it when he eventually deposits it. In the current system this does not arise as Alice can always give him another copy of the coin and prove that it is good, and she can further determine if Bob has deposited it. So some of the trust in the bank necessary with regular ecash gets replaced by trust between payee and payor in Simon Spero's system.

If Bob insists that the bank wouldn't redeem Alice's coin, that's not Alice's fault. The bank should have reserved the money when Alice withdrew it. Since nobody other than Bob sees the unblinded coin, it's Bob's fault if somebody else spent it before Bob could. In the case of fraud by the bank, since the bank signed the coin, the bank should be liable if it won't redeem it. Perhaps the problem is that Bob insists that Alice's coin was not signed by the bank. In that case, how about this modification? Alice should first show Bob the doubly blinded coin she gave to the bank and the signed doubly blinded coin she received back. Bob can verify the signature and then Alice can give him the blinding factor so he can unblind it himself. Bob also needs to sign the singly blinded coin that he gives to Alice so that Alice can later show that she gave him the correct blinding factor if Bob tries to claim that she didn't. Are the any problems with this? -- Sure we spend a lot of money, but that doesn't mean | Tom Weinstein we *do* anything. -- Washington DC motto | tomw@engr.sgi.com

In article <DGyIMI.KM9@sgi.sgi.com>, Hal <hfinney@shell.portal.com> writes:

tomw@orac.engr.sgi.com (Tom Weinstein) writes:

...

Perhaps the problem is that Bob insists that Alice's coin was not signed by the bank. In that case, how about this modification? Alice should first show Bob the doubly blinded coin she gave to the bank and the signed doubly blinded coin she received back. Bob can verify the signature and then Alice can give him the blinding factor so he can unblind it himself. Bob also needs to sign the singly blinded coin that he gives to Alice so that Alice can later show that she gave him the correct blinding factor if Bob tries to claim that she didn't.

The problem with this is that Bob and the bank can now collude to trace Alice, since he sees what she sent to the bank. This is not as bad as in the forward traceability case of regular ecash, because it happens after Alice has completed her bank transaction, rather than before, but it would be better to be untraceable since that is the whole point of this variation.

Good point. To guard against this, Alice needs to double blind what she sends to the bank. She can then remove one layer of blinding and show the results to Bob. Of course Bob and the bank can still colude because of the timing of the transactions. This seems to be a fundamental weakness of this reverse e-cash scheme. -- Sure we spend a lot of money, but that doesn't mean | Tom Weinstein we *do* anything. -- Washington DC motto | tomw@engr.sgi.com

On Mon, 23 Oct 1995, Hal wrote:

This is an interesting idea but it is more complicated than necessary, I think. The denomination can be carried in the exponent, in which case there is no need for cut and choose and nobody can cheat the bank. A coin suitable for deposit is a signed number of some special form. To pay Bob, Alice does not withdraw anything ahead of time. Rather, Bob gives her a blinded coin, which she reblinds and gives to the bank. The bank signs it (debiting Alice's account) and gives it back to her. She strips off her blinding and gives it to Bob. He strips off his own blinding and verfifies that he is left with a signed number of the appropriate form.

Using the above protocol, payee anonymity will not be compromised by collusion between the bank and the payer, but the payee and the bank can collude to identify the payer! (This reverses the situation in normal Chaumian ecash, and of course in certain circumstances may be preferable.) This collusion can succeed even if Alice (the payer) reblinds the coin she gets from Bob before asking the bank to sign it, because Alice must withdraw the coin after Bob gives it to her and before returning it to Bob. Bob can ask the bank to record the names of everyone who withdrew money during that period, and after two or three repeated transactions can narrow the list of possible payers down to one person. (This is reminescent of the time-correlation attack on remailers.) In the original protocol this isn't possible because Alice can withdraw the money ahead of time. Wei Dai

Jiri Baum <jirib@sweeney.cs.monash.edu.au> writes:

Hello Hal <hfinney@shell.portal.com> H wrote:

...

There could be an issue of fraud, though, where Bob insists that Alice's coin was no good even though it actually was.

Cut'n'choose between Alice and Bob? Ie Alice asks Bob for half the blinds to check that the proto-coins are true?

This would work to protect Alice from certain kinds of fraud by Bob, but it increases the amount of data considerably, and it still does not resolve the main issue that Bob claims that his coin didn't unlind to clean data. Who is at fault in that case? How can this be resolved?

Apart from no-good proto-coins, is there any other way the coin could be no good?

Alice could give Bob bogus data, Bob could give Alice bogus data, Bob could claim that Alice gave him bogus data (even though it was good).

As for no-good proto-coins, it's Bob's fault, isn't it? Alice has a record of what Bob sent, and what she sent back. Anybody can check that the latter is a bank-signed version of the former.

If what she got from Bob was signed by him, she can prove that she gave him back a bank-signed version of that. (He has to sign it, otherwise she could just exhibit two bogus numbers, one the cube of the other.) Given that, your idea seems good. Alice can prove that she did her part OK, so if she is able to show such a proof then Bob must be at fault.

Given this, there's no need (from this) for Alice to know that the proto-coins are good (if they aren't, Bob's an idiot, but there's not much Alice can do about it - I guess given all the blinding factors the bank could replace the coin, seeing that it signed a worthless one).

Yes, I think so, so there is no need for the cut and choose.

An interesting question is whether Bob and Nick can now collude to expose Alice. Therefore Alice would at least want to verify that the proto-coins are true? Would that suffice? Or is that not necessary?

I don't think they can. All Bob sees is his own blinded coin, and the signed version of that. The bank sees a separately blinded number which it signed. Alice's blinding factor can be anything, so there is no linkage between them. However, the timing is a problem. Bob knows _when_ Alice communicated with the bank. So he can collude with the bank afterwards to identify those withdrawals which took place at that time, one of which must have been Alice. This could be a problem. In regular ecash, the timing issue is potentially less serious because the payee can in principle have a totally anonymous relationship to the bank, and exchange his received coins for fresh ones. But in this system doing that is more difficult. Alice must withdraw funds rather than deposit them. To do so totally anonymously she would have to present coins to the bank at withdrawal time equal in value to the amount she wanted to pay Bob. The bank would replace these coins with fresh ones that it signs, which are the doubly-blinded ones which Bob has provided to Alice. So this is a somewhat more roundabout approach. However, if you do this, and Alice communicates with the bank anonymously, then both sides seem to be pretty well protected against collusion. Hal