-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Here is the blind DSA signature based on MacKenzie and Reiter, http://www.ece.cmu.edu/~reiter/papers/2001/CRYPTO.pdf, in graphical form. Recall that a DSA public key is p, q, g, y; private key x; signature on hash h is: Choose k < q r = g^k mod p mod q s = rx/k + h/k mod q Output (r,s) Here is the blind signature protocol, with Alice, the recipient, on the left and Bob, the signer, on the right: Alice (recipient) Bob (signer) - ------------------------------------------------ Choose k2 < q z2 = 1/k2 mod q Send r2 = g^k2 mod p <--------------------------- Choose k1 < q r = r2^k1 mod p mod q Send a=E(r/k1 mod q) and b = E(h/k1 mod q) and ZKP --------------------------> Check ZKP Choose d < q^5 Send c = a '*' x*z2 '+' b '*' z2 '+' E(d*q) <--------------------------- s = D(c) mod q Output (r,s) Here, E() and D() represent encryption and decryption in a homomorphic encryption system like the Paillier encryption. Only Alice knows the private key, but Bob is able to multiply encrypted values by scalars (indicated by '*' above) and to add encrypted values (indicated by '+' above). ZKP sent by Alice in the 2nd step is a zero knowledge proof that the two encrypted values are known and are < q^3. (Actually the values are less than q but the standard ZKP for this has some slop in it, which is OK for this purpose.) Bob operates on the two homomorphic encryptions of r/k1 and h/k1. He multiplies the first by x/k2 and the second by 1/k2 and adds them to get rx/k + h/k mod q (where k = k1*k2), exactly as required for the signature. Then he adds the large multiple of q to fully hide his secret x value. One interesting thing about this protocol is that it may escape the Chaum blind signature patent, US 4759063, for two reasons. First, the Chaum patent covers three step blinding, while this is a four step process. In the regular Chaum blind signature there is no need for the initial step where the signer sends an initial r2 value. That step is crucial here; k2 must be fresh for every signature or the signer's key is leaked. Second, the Chaum patent describes the signer's operation as performing a public key digital signature operation. This is in fact how the Chaum blind signature works; the signer does do an ordinary RSA signature operation. But in this case, the signer performs a completely different transformation, working with two homomorphically encrypted values in an unusual way. This is not a conventional digital signature operation. Therefore this type of blind signature should escape the patent. Of course the patent expires in a little over a year so it is largely moot now anyway. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.0 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQFAirIcHIAd9K7kkjIRAk/nAJ0cIxTYSudiKd0rrXv/T1kUuMHbjQCfSaya NmVhsnuT/jBeqf5eVIx2FaI= =x3ps -----END PGP SIGNATURE-----