Negative credentials

[Hal Finney <hal@rain.org>]

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