Eric Cordian writes:
Let's see. The mint picks a prime, p, a generator, g, and a random number k, and publishes (p, g, g^k mod p).
The mint then signs stuff by raising it to the k power mod p, and not telling anyone what k is.
We blind coins by picking a random b, and sending the coin times g^b to the mint, and after the mint raises it to the k power and sends it back, we can reverse engineer coin^k.
A few years ago I discovered that this allows the bank to "mark" the cash. The bank can use a different exponent k' instead of the exponent k it is supposed to be using, on certain withdrawals. On every deposit, it checks the incoming coin using both k and k', and is able to quietly identify the marked withdrawals. In more detail: during withdrawal, the user submits y * g^b. The bank, to mark the cash, raises it to the k' power rather than the k power. The creates y^k' * g^bk'. The user unsuspectingly unblinds by calculating g^kb and dividing it, leaving y^k' * g^(b(k'-k)). This is what is later submitted to the bank, along with y. The bank, at this point, knows y, k, k', g, and the product above. It does not know b. It can calculate y^k' and divide to get g^(b(k'-k)). It can raise to the inverse power of (k'-k) to get g^b. Now it can multiply by y to get y * g^b. This is the same value which was submitted to be signed in the first place. By keeping a record of the values which were signed using the special k' exponent, the bank can look back and see which one this one is, thereby linking the deposit to the withdrawal, which is exactly what blinding is supposed to prevent. In order to avoid this, the bank can prove that it operated correctly (that is, it raised its input to the same k power that g is raised to in the public g^k value) using a zero-knowledge proof. I believe the latest version of the Lucre software does this. However, it's possible that the Lucre ZK proof is only honest-verifier zero knowledge. An honest-verifier ZK proof is one which is ZK only if the verifier follows the protocol; for example, when it is supposed to choose a random value, it in effect flips a coin. The point of a ZK proof is that a transcript is unconvincing to third parties, because the verifier would have been able to create a fake transcript. He could do so by, in effect, working backwards from chosen results to figure out what his coin flips would have had to be. However, if the verifier chooses his bits using a fixed sequence like a strong PRNG, then when he reveals the transcript, he can also show that his "random" bits were determined by his PRNG seed. This proves that he did not in fact have the flexibility to choose his bits by working backwards, and therefore the proof is convincing to a third party. In this case, the transcript of the "ZK proof" would in fact prove that the bank knew the k of g^k. The transcript is therefore a signature, and in conjunction with the coin, it is arguably a blind signature. Blind signatures are patented until July, 2005. Given that the whole point of this application of Wagner blinding was to avoid the Chaum blind signature patent; that that patent expires in two years; that the current licensee has shown no effort to enforce the patent; that Wagner blinding also risks falling under another patent, on Chaum's undeniable signature; and that the bank's operation even with Wagner blinding looks an awful lot like a blind signature; then why not just use Chaum's blinding? It would be enormously simpler, and safer too. It's far more widely analyzed and there are a number of improvements in the literature.