Blind signatures with DSA/ECDSA?

[An Metet]

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.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: Blind signatures with DSA/ECDSA?

[privacy.at Anonymous Remailer]

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.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Blind signatures with DSA/ECDSA?

[Eric Rescorla]

Folks,

Does anyone know if there is a blind signature scheme that works with
DSA or ECDSA? I know about Camenisch, Pivetau and Stadler's "Blind
Signatures Based on the Discrete Logarithm Problem" (1994), but as far
as I can tell that doesn't produce straight DSA-verifiable signatures
and so is a lot less desirable than it might otherwise be.

Has there been any better work on this?

Thanks,
-Ekr

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]