On 3 Mar 2000, Secret Squirrel wrote:
> If all payments are for different amounts, then this would no longer
> work, as a chain of $123.45 payments would be easy to track. It would
> therefore be necessary for the system to use a single standard payment
> size. If people wanted to pay more, they would send multiple messages.
> If these can be spread out over a period of time, it should be possible
> to hide who has paid whom.
Note that cash payments can have a property which encrypted messages
usually do not : you can have the mix break up the payment into
random-sized chunks, or aggregate several payments into a single
transaction between servers.
For example, say I send a payment for $123.45 -- the remailer might
split this into a payment of $100 and a payment of $23.45. That
$23.45 could then be combined with some other payments to create an
aggregate payment of $100 which is sent to the next remailer in the chain.
That remailer unpacks the aggregate, breaks up the $23.45 into $20
or so and change, and so on.
That example may not be so great, but I wonder if we can get anything from
this kind of dynamic recombination.
It seems that doing this requires some kind of trust in each server.
More specifically, we would trust each server to combine payments
correctly and split them correctly. We would have to enforce this trust
via some kind of audit protocol, such as public posting of encrypted
receipts. Maybe this overhead would eat up any possible gain; it's not
yet clear to me one way or the other.
> Current remailer networks are not very reliable.
That's an understatement. :-(
> A system like this
> would obviously increase the temptation for remailer operators to receive
> payment for some messages but not pass them on.
fair exchange problem or something weaker? can we build a protocol which
commits to a payment when the remailer operator gets a message, then
follows through when the message is passed on?
> Remailers could profit
> by cheating. Chaum proposed making remailers publish logs of the messages
> they had handled, such that it would be possible to see that each remailer
> sent all the messages it received, and the next remailer in the chain
> received all the messages it was sent. This would reveal the source of
> any problems, narrowing it down to the interface between two remailers,
> which should allow for a fix.
It might also allow for a payment to be provably traced to a given
remailer if the payer turns evil at a later date. The payer produces the
(signed) logs of the remailers and shows that his message went through
such and such a remailer at such and such a date. This may be suboptimal
if there are such things as "bad payments" by which I mean payments made
as part of a money laundering or fraud scheme -- payments which could be
cause for action against a remailer operator.
Plus now you have to sign the logs, which adds overhead.
At least three ideas I have connected with this :
1) Weaken the logs such that everyone can see that a remailer sent all
received messages, but not even the sending party can pick out
his message from the logs. From my understanding of Chaum's
1981 paper, his suggestion of signed batches would allow
a sending party to prove that his message actually was in the
batch, since all the encryption is done by the sending party.
You might get around this by having the remailer "add randomness"
of its own to outgoing messages. For instance, it could pick the
random value r used for OAEP. Then you still have to show that
everything in the output batch corresponds to something in the
input batch...
2) Send receipts to the sending party which are "designated verifier"
such that only
a) the sending party
and b) possibly some other arbitrating party / reputation
service / third party trusted not to be evil in court
would find these receipts credible. I can go into detail
on this in case anyone cares...the basic idea is to use the
"designated verifier" proofs of Jakobsson, Impagliazzo, and Sako
http://www.bell-labs.com/user/markusj/dvp.ps
but extend them just slightly to deal in a nice way with multiple
verifiers -- without the verifiers needing to share a secret key
or collaborate in any way.
The advantage of this method is that now we can give all kinds of
receipts and be sure that they won't be used "against us" in court.
These receipts can be very convincing to the sending party.
The disadvantage is that if the server does wrong, and the sending
party can't prove it to anyone else, that's bad. Therefore the
extension to multiple verifiers, one of which is a trusted
arbitrating party.
3) Abandon signed output batches in favor of random "tag numbers"
or "payment magic numbers" embedded in the payment. The numbers
work like this :
1) the sending party picks N remailers.
2) the sending party picks N tag numbers at random from
ye olde really big set (like all 128-bit numbers).
3) The payment is formatted in such a way that each
remailer sees one and only one such tag number. No
remailer sees any other remailer's tag number.
4) When the remailer receives a payment, it
announces, posts, or otherwise makes known that it
received a message with a certain tag number.
5) The sending party sees this and is confident
that his message reached that remailer (with high
probability; collisions are possible but can be
made arbitrarily rare).
6) If the next hop in the remailer chain does not
announce its associated tag number, the sending
party knows that one of these two hops screwed up somehow.
Note that I am assuming the sending party knows the
entire remailer chain in advance.
So the sending party knows not to use either of them ever
again. This would allow the sending party to detect a
remailer interface which is bad -- one of the same goals
as Chaum's signed batch idea.
With this scheme, proving that your message passed through
a given remailer IS still possible. You tell someone the
tag number for that message and that remailer before it announces
the message.
*After* the remailer announces a given tag number, however, it
seems that anyone could easily make up a message containing that
tag number. So trying to claim that your message went through
that remailer after this point does not seem credible any more.
Since the tag numbers are random and picked independently of the
message, they give no information by themselves about the message.
Hopefully in practice such a scheme would not fall victim to
things like people using distinctively biased PRNGs...
The biggest problem (feature?) here is that it alerts the sending
party that something is wrong, but gives no way to transfer
this alert to someone else. Plus you have an issue as to how
long to wait before concluding something is wrong.
I think payment mixes are a great idea. I had been thinking about
something similar in the context of campaign finance donations, but it
never occurred to me to apply the principle to *all* types of
transactions...
Thanks,
-David Molnar
