MISC: cut & choose

2 Sep 1993

      -----BEGIN PGP SIGNED MESSAGE-----

Earlier I mentioned cut-and-choose protocols as a way of protecting from
signing a message that you really don't want to (ways of forging signatures
on documents).

The protocols are simple and rest on a probabalistic argument (similar in
some ways to the "proof" in a zero-knowledge proof) - you can be certain
to any degree you wish that you are not about to sign a harmful document.

Essentially, Bob makes multiple copies of the document and appends random 
bits on the end of each.  Then, he blinds each document with a different 
blinding factor, and presents all the copies of the blinded documents to
Alice.  But before she signs anything, she demands that all documents
are unblinded, except one.  Bob complies and produces the unblinding factor
for all the documents except one, and unblinds them.  Alice looks over the
documents to verify their content, and if she is satisfied, she goes ahead
and digitally signs the remaining document, which is still blinded.

For example, say Alice is a digital bank.  Bob wants to get $10 of digital
cash, so he prepares a message, blinds it, and goes to the bank. However, 
Alice, who has read about the notary protocol, is leery of signing random
strings, so Bob goes home again and prepares 100 messages, 100 blinding 
factors, and blinds each message with its own blinding factor.  He shows up
at the bank and gives Alice all the messages.  Alice picks one message and 
hands back the other 99, demanding that Bob unblind them.  So he complies, 
and Alice verifies that they all are in fact messages for $10.  Satisfied,
she digitally signs the last message, knowing that there still is a 1%
chance that Bob cheated the bank by slipping in a $100 message with the
$10 messages.

So Alice can feel as comfortable as she likes by just asking for more
messages.

Say that cash messages look like this (with random bits at the end):

This is $10 of digicash legal tender from First Digital. ADF!#$%@^%&gsu$

When Bob blinds this, it becomes unreadable so Alice can't verify that it
is in fact a legitimate message (Bob may be trying to get Alice's signature
on another document).  But Bob does need to blind the message or the bank
(Alice) can note the random bits, serial number, or whatever, and thus
correlate the cash with him.  

The solution is the above protocol, which leaves an 1/n chance of fooling
the bank, where n is the number of messages.  Alice can ask for n messages
where n is large, but there will still be a 1/n chance that Alice picks
the special message and is tricked into signing it.  (Say Bob slips in a
message for $1000 into a bunch of $10 messages; he may get really lucky
and have Alice pick the $1000 message, demanding he unblind all the rest
to reveal $10 messages).

However, this can get pretty expensive to implement for high confidence 
levels.  Again, I'm sure a document forgery can't occur with PGP or even
RIPEM (in the notary protocol manner) since neither program blinds messages:
they calculate hashes, compress, encrypt, digitally sign hashes, but don't 
obscure messages by a multiplication factor.

MISC: cut & choose

Karl Lui Barrus