Cut and choose protocol is a significant technique for
digital cash. It is what makes
blind signatures useful, and the technique used to assure that a person spending digital cash more than once is identified (while keeping the person anonymous on a single spending).
The basic concept is this: Party A presents a bunch of blinded somethings to party B. Party B choose some of the somethings, and demand the unblinding factors for these, leaving the rest of the somethings blinded.
For simple digital cash, cut and choose is used in two places:
- When a coin is created, the person wanting to create the coin presents a bunch of potential coins to the blank, with all the coins blinded. The bank demands the unblinding factor for all but one of the coins (randomly choosing which), and verifies that they are correct (contain the identifying data for the person requesting the coin creation, are for the correct amount, and are generally well-formed.) After the bank has verified this, it signs the remaining coin without seeing it. By increasing the number of coins checked, any level of security can be attained (though even with only two coins there is a 50% chance that somebody that attempts fraud is caught.)
- Each coin contains a number of copies of data identifying the creator of the coin. Each copy of this data is split into two halves in such a way that having one half gives no information, and having both halves fully identify the person. When the person spends the money, the merchant requests the unblinding factors for one of the halves of each split identity, randomly chosing which half. The merchant send these unblinding factors along with the coin to the bank when he redeems the note. If a coin is spent twice, the different merchants are likely to request different halves of at least one copy of the identity. The bank thus gets the complete identity of the double spender (even with only one copy of the split identity, the likelihood of getting caught is 50%.)
Note that the identity halves must contain something that distinguish them from random garbage; one way of ensuring this is to have each half contain a copy of the bank's name, and do the blinding by using symmetric encryption with the keys as the blinding factors.
There is a trick that can be used to increase the security of step 1 at the expense of the size of the coin. Instead of leaving one coin to be signed, the bank checks only half the coins, and puts a blind signature on all the rest - concatenated together. When the coin is spent, the merchant checks that all the coins that were concat'ed are the same value. This results in an attacker having to a 1/2^(n/2) chance of getting everything right (for n submitted coins), rather than 1/n.