I was riding the train tonight, re-reading some old crypto papers, including Chaum's Auscrypt paper on digital pseudonyms, credentials, and such. He described a method for letting libraries catch people who don't return library books, while still preserving confidentiality of all transactions. It occured to me that a modified form of his idea could help curb abuse of remailers.
Chaum's idea was pretty complicated, but I think a simpler approach could work using the existing Magic Money software. One idea we have talked about to help curb abuse would be to simply charge digital postage for every message. However, it was pointed out that in practice postage costs would probably be so low that this would only help in extreme cases of volume abuse.
My idea is to have the coins not represent money, but to have them be "non-abuse tokens". With every message would be included a non-abuse token in the form that Magic Money uses when you exchange incoming money at the bank. This is composed of the coin itself, plus what is called a "proto-coin" which is a blinded version of what will become the new coin. The remailer would check the incoming non-abuse token to make sure it hadn't been seen before, just like the bank does with Magic Money.
However, it would not immediately sign and return the blinded proto-coin. Instead, it would hold onto it for a day or two to see if any complaints came back about the message. This would require remembering the outgoing message-ID along with the proto-coin, but nothing else would have to be remembered about the message, and of course with remailer chains the true source of the message would be completely unknown.
If no complaints come in (which is the case with the vast majority of messages, in my experience) the remailer would sign and publish the blinded proto-coin. This would be put in some public place which was generally available to all who might use the remailer. The user who sent the message would be watching for this proto-coin and pick it up, un-blinding it with his Magic Money software, to produce a new non-abuse token which he can use to send another message.
If serious complaints do come in about the message, the remailer would not sign the proto-coin, and the sender would have lost a non-abuse token.
The nice thing about this system is that it protects the privacy of the user of the remailer system. With the Magic Money technology each non-abuse token is blinded so there is no linkage possible between issuing of such tokens and their use. The big problem with the remailers now is that abusive messages can't be addressed without trying to track down who sent them, which is usually impossible. This system addresses the problem without hurting anyone's privacy.
A couple of issues that I have glossed over would include how the non-abuse tokens are issued in the first place. There is the obvious danger that an abuser manages to keep getting new tokens by pretending to be a new net user who would like to use the remailer. Two solutions to this would be first, to charge a significant sum for a handful of non-abuse tokens; this would be a one-time fee for non-abusers but could get expensive for those who abuse; or second, to only give non-abuse tokens to users who could be identified by their True Names. (This isn't a situation which needs military-grade security; semi-secure methods of identifying true names should be adequate.)
One other thing I suggested above which might seem a little controversial was that the signed but still-blinded proto-coins could be made available in the clear. Since these are in the form r*f(x)^(1/d) where r, a random number, is only known to the user who created the proto-coin, I think they are effectively one-time-pad encrypted. So I don't see any need for these messages to be hidden with a public key. In fact, I don't think Magic Money would really need to have a public key for the user since it is only used to protect these messages, and I don't think they need protection. Comments are welcome on this point.
One last point involves the definition of abuse. As far as I am concerned that is up to the remailer operator. Last week I got a very polite and worried letter from a girl wondering why she had received mail from my remailer inviting her to suck some guy's finger, except it wasn't his finger. (Despite our recent discussion of this list's implicit "X" rating I am reluctant to be more explicit.) I don't get too many of these but I feel bad about them all the same. My current approach is to add each person to the list of blocked outgoing addresses, but I think the technology would allow for a more effective solution.