apr 2011

Blind signature basics

I'm starting work on my diploma thesis this month. The exact topic isn't set in stone yet, but it will be something crypto. If everything goes dreamy-awesome, I'll find something nice to write about lattice-based blind signatures or somesuch. Background:

• Blind signatures are used for e-cash. I'm fascinated with e-cash.
• Lattice-based methods are candidates for quantum-resistant systems. Appearently there's lots of current research going on.
• I've done some lattice theory at Charles University in Prague. Never thought I'd see it again, so wouldn't that be something.
• There's zero knowledge in there somewhere. Another fascination.

So, time to sum up the basics. As far as my history serves, David Chaum invented blind signatures in the 80s for electronic voting but nobody wanted to buy that, so he also invented electronic cash. Then he got really paranoid and didn't sell it either. Real quick summary. ;)

Anyway…

The principle is to mix whatever you want signed (electronic voting ballot, 100 EUR banknote) with a random blinding factor and divide that out only after Trent (your government, bank) has signed. Thus Trent cannot recognize and connect the note to you when it comes back to him later.

The classic algorithm is based on RSA and is painted up fast. Unfortunately, my awesome markup language still has no fancy math support so you have to live with ASCII art:

m = message to be signed
e = public "encryption" (i.e. verification) exponent
n = public modulus
d = secret "decryption" (i.e. signing) exponent
k = blinding factor (just a random number)

x^(de) = x^(ed) = x (mod n)         -- RSA property

Alice prepares:  mk^e               -- blinded message
Trent signs:     (mk^e)^d = m^d k
Alice unblinds:  m^d k / k = m^d    -- signed message
Bob can check:   (m^d)^e = m

One might think that signing something completely blindly might be a bad idea. After all, a bank needs to know the value of the note it is signing. To ensure any desired property of the signed document, Trent can require a cut-and-choose step. In this case Alice must give him n different but equivalent messages. He chooses one of them and asks Alice to unblind all the others. Trent signs the remaining blinded one if the others satisfy the desired property. Alice's chance to cheat of 1:n can be made unattractive by attaching a suitable penalty.