There has been some discussion here and on the Simple Public Key Infrastructure (SPKI) mailing list about anonymous credentials and abuse. This is something we have of course talked about many times over the years but I don't think we have ever had a specific look at Chaum's approach to the "negative credential" problem. In essence his method allows you to prove that you haven't cheated on any of your contracts, without revealing any more about yourself than that. Chaum uses what he calls "sequenced couples", which are sequences of pseudonym pairs such that credential A on one pair of the sequence can be transformed by the user into credential B on the next pair. This ties into his whole scheme, which is a bit too complicated to explain here. What I will describe is a very simplified version of what Chaum has. Chaum's description can be hard to follow but takes care of a lot more possibilities. His full paper, which BTW is my favorite crypto paper of them all, is: "Showing Credentials Without Identification: Signatures Transferred Between Unconditionally Unlinkable Pseudonyms," D. Chaum, Accepted but not Presented Auscrypt '89. The general idea is this. Every time you engage in a contractual relationship with someone it is done under the auspices of an "anonymous credential" organization. You first show your contract partner a credential from the AC org which guarantees that you have not cheated anyone so far. After you participate in your current interaction, if it completes to everyone's satisfaction, you are given a new credential by the AC org which proves that you still haven't cheated. Each credential can only be used once, so if you cheat someone you can't get a new one. There is a simple and obvious solution which satisfies these requirements. That is to use a blinded signature exactly as is done with DigiCash coins. You get your first credential on registering with the AC organization. (Here we have a bit of a bootstrapping problem, in that the AC org needs to make sure you don't register more than once. But actually since things will be blinded you can just use your SS# or other identity documents.) The credential is a blind signature, unlinkable to your identity. When you go to contract with someone, you show your credential and the AC confirms that it hasn't been used before (exactly like checking for double spending on coins!). The AC marks the credential as being in the "in use" state (putting it on its own private list of such credentials). Then when your contract completes successfully, your partner certifies this fact to the AC, and it then retires your old credential and issues you a new, freshly blinded credential. This credential is unlinkable to your earlier one or to your identity, but it proves that you haven't cheated and you can show it the next time you need to make a contract. Now, obviously this simple solution has problems: - You can transfer credentials to other people. Chaum's more elaborate solution links the credentials to your pseudonyms. - You could get cheated by your contract partner who won't authorize a new credential for you even though you completed your contract. This happens today, unfair credit rating blotches. There would have to be some kind of arbitration procedure. - There is no way of distinguishing someone who's done dozens of successful contracts from someone who's done only one. This is a feature, not a bug... But if you want you can show positive credentials from earlier participants; Chaum's method allows them to be linked to your new pseudonyms. - You can only have one contract going at once. Chaum has some solution involving time limits but I've never fully understood it. The general idea might be that when you go into the contract the AC gives you a new credential which means "he hasn't cheated anybody so far, and if he does cheat someone we'll know about it by <date>". <date> would be the date of completion of the contract. This is still a blinded credential, so the date gets encoded in the signature. Chaum shows how you can even blind the date, moving it in to some earlier date (but never out). Then you can use this credential to establish a new contract as long as the date hasn't expired. It gets complicated once you have multiple contracts with different expiration dates, though. Although this solution is somewhat simplified, hopefully it will give people a picture of how negative credentials can be dealt with while still retaining full anonymity in contract relationships. Hal