contemplating remailer postage

[jim@uu4.psi.com]

Although lot of people (including me) have mentioned Digital Stamps, or  
remailer postage, when describing advanced remailers, I've yet to see a  
good description of a practical remailer postage mechanism.  I assume it  
will be (or has been) modeled after one of the Chaumian digital cash  
protocols.  If there has been work done on a remailer postage mechanism,  
could somebody post the details? (or a reference)

Here's what I think would make up a practical remailer postage mechanism:

I think that each remailer should issue its own stamps, rather than using  
a central digital postage service.  The existence of a centralize digital  
postage service creates a single point of failure for the entire remailer  
system.  It also complicates the protocol needed to validate digital  
stamps and check for double spending.  Of course, having each remailer  
issue its own stamps would increase the complexity for the users of the  
remailer system.  However, I believe the increased user-side complexity  
can be completely hidden within a good set of scripts (e.g. the scripts  
could maintain a subdirectory for each remailer to hold stamps for that  
remailer).

If all digital stamps have the same "denomination", then the protocol for  
obtaining stamps can be greatly simplified.  You wont need to engage in a  
cut-and-choose protocol with the remailer (see page 121, Digital Cash  
Protocol #4, Applied Cryptography).  To obtain 100 stamps from R1, Bob  
would generate and blind 100 uniqueness strings (random numbers large  
enough that they are unlikely to collide with anyone else's) and send them  
all to R1.  R1 would simply sign all 100 of them and send them back.  Bob  
would unblind them and store them in his "R1_stamps" subdirectory.

Given the low value of individual stamps, it is probably not necessary to  
try to determine who is attempting to double spend stamps.  Therefore,  
stamps wouldn't need the identity strings used in Digital Cash Protocol  
#4.  Also, since the remailer is both "bank" and "merchant", there's no  
chance of the "merchant" cheating the "bank".

...

When Bob wants to route a message through R1, he place an R1 stamp at the  
appropriate level within the nested envelopes.  These stamps can also be  
used in SASE's.

When R1 receives a stamped message (or SASE) it will check the signature  
of the stamp.  If the signature doesn't verify, R1 discards the message.   
If the signature verifies, R1 checks the uniqueness string against his  
archive of "used" stamps.  If the uniqueness string is present in the  
archive, the stamp has already been used and the message will be  
discarded.  If the uniqueness string is not present in the archive, R1  
will route the message on to the next hop.  Finally, R1 places the  
uniqueness string in his "used stamp" archive.

Seems simple enough.  The major sticking point (to me) is the remailer's  
"used stamp" archive.  This could grow to be very large.  Something needs  
to be done to keep the archive from getting too large.

One idea is to have the remailer periodically change the key it uses to  
sign stamps.  Changing the "stamp validation key" effectively invalidates  
all unused stamps signed by that key.  If you haven't used the stamp by  
that time, you're out of luck.  The remailer can purge its "used stamp"  
archive whenever it changes its "stamp validation key".

Of course, invalidating peoples' unused stamps out from under them is not  
a nice thing for a remailer to do.  The remailer could provide a mechanism  
whereby people could get new stamps from old, unused stamps.  To make this  
work, the remailer would have to retain the previous "used stamp" archive  
for a while to give people a chance to get new stamps.  However, there  
still needs to be a limit on how long the remailer retains the "used  
stamp" archives for old validation keys.  If you wait too long, you would  
lose any chance to get new stamps from old.

Comments welcome.

Jim_Miller@suite.com