Blind signatures with DSA/ECDSA?

[privacy.at Anonymous Remailer]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Often people ask about blind DSA signatures.  There are many known
variants on DSA signatures which allow for blinding, but blinding "plain"
DSA signatures is not discussed much.

Clearly, blinding DSA signatures is possible, through general purpose
two party multi-party computations, such as circuit based protocols.
However these would be too inefficient.

I believe that the technique of Philip MacKenzie and Michael
K. Reiter, Two-Party Generation of DSA Signatures, Crypto 2001,
http://www.ece.cmu.edu/~reiter/papers/, can be adapted for blind DSA
signatures that would be reasonably efficient.  The problem they solved
was different in that both parties had a share of the private key, and
there was no effort to hide the message hash being signed or the (r,s)
signature values.  However the same basic idea should work.

The scheme uses a homomorphic encryption key held by the first party,
Alice, who is the one who will receive the signature.  Bob is the signer.
The homomorphic encryption system allows Bob to take an encrypted value
and multiply it by a constant known to him; and also to add two encrypted
values together.  (That is, Bob can produce an output cyphertext which
holds the result.  He does not learn the result.)  Suggested cryptosystems
with the desired properties include those from Paillier; Naccache and
Stern; or Okamoto and Uchiyama.

Alice starts with the message hash H, and knows the public key parameters
y, g, p and q.  Bob knows the private key x such that y = g^x mod p,
where q is the order of g.  DSA signatures are computed by choosing a
random value k mod q and computing r = g^k mod p mod q; z = 1/k mod q;
s = x*r*z + H*z mod q; with (r,s) being the signature.

For the protocol, Alice and Bob will compute k as multiplicatively
shared, with Alice knowing k1 and Bob knowing k2, where k1*k2 = k mod q.
We start, then, with Bob (the signer) computing r2 = g^k2 mod p and
sending that to Alice.  Alice computes r = r2^k1 mod p mod q = g^(k2*k1)
mod p mod q = g^k mod p mod q.  Alice and Bob also compute z1 = 1/k1
mod q and z2 = 1/k2 mod q respectively; then z = 1/k mod q = z1*z2 mod q.

Alice uses the homomorphic encryption and produces a = E(r*z1) and
b = E(H*z1).  She sends these to Bob along with some ZK proofs that the
values are well formed.  Bob uses the homomorphic properties to multiply
the plaintext of a by x*z2 and the plaintext of b by z2 and to add them,
along with a large random multiple of q, q*d, where d is random mod q^5:
c = a X (x*z2) + b X z2 + E(d*q).  Here X means the operation to multiply
the hidden encrypted value by a scalar, and + is the operation to add two
encrypted values.  Bob sends c back to Alice.

Alice decrypts c and takes the result mod q to recover
s = r*z1*x*z2 + H*z1*z2 = x*r*z + H*z mod q, the other component of the
DSS signature.  She can verify that Bob behaved correctly by checking that
(r,s) is a valid DSS signature on H.

For a quick security analysis, Alice is clearly safe as Bob never
sees anything from her but some encrypted values, and his k2 share of
k is uncorrelated to k itself.  In the other direction, Bob has to be
concerned about revealing x.  He is given two encrypted values and has to
multiply one by x*z2 and the other by z2 and add them.  If the encrypted
plaintexts are u and v, this produces (u*x + v) * z2.  This value is
completely uncorrelated with x, mod q, because of the multiplication by
z2 which is uniformly distributed.  Then adding the large multiple of q
should effectively hide the value of x.  For strictly provable security
it may be necessary for Alice and perhaps even Bob to provide some ZK
proofs that they are behaving correctly.

The system is reasonably efficient, the main issue being the need to be
able to PK encrypt values as large as q^6, which for DSS would be 6*160
or 960 bits.  That would require a Paillier key of about 2K bits which
is very manageable.  The total cost is about 9 modular exponentiations of
2K bit values to 1K bit exponents, plus whatever ZK proofs are necessary.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.0 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFAiKbxHIAd9K7kkjIRAmLEAKCUNcW3fsDysi9Mul9WlFzVMQivWgCgxdHt
dq6rlO2tfSoufs9NrhX616Y=
=gBz4
-----END PGP SIGNATURE-----