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