Blind signatures with DSA/ECDSA?

[An Metet]

-----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-----