A note on blind signature schemes

RSA blind signatures

Traditional RSA signatures have the form S = M^d mod N, where M is the message, (N, e) is the public key, and d is the secret key, selected such that for any m: m^{e*d} = m (see here for details on how keys are constructed). Chaum observed that a user could ‘blind’ an RSA message for a bank to sign, by first selecting a random r (in the range 1 through N-1, such that r has an inverse mod N) and giving the bank the blinded value (M * r^e) mod N.

The bank can compute (M * r^e)^d mod N using its secret key, and return this ‘almost signed’ value to the user. Since d is selected to such that any m^{ed} = m, the equation simplifies to:

(M * r^e)^d ≡ (M^d * r^{ed}) ≡ M^d * r      mod N

The user can simply divide out r (technically: multiply by r^{-1} mod N) to obtain the actual signature M^d mod N.

(Side note: many crypto libraries employ this technique for a different purpose — to avoid timing attacks on RSA decryption. By ‘blinding’ the value before applying the secret key, the library prevents the attacker from submitting specific numbers to be decrypted. This stops a class of known remote timing attacks.)

Schnorr/DSA blind signatures

The DSA scheme is based (not loosely) on the Elgamal and Schnorr signature schemes. Let (g, p, q, y) be the public key, where (g, p, q) describe a group of order q, with generator g (see here for details on how these elements are chosen) and y = g^x mod p. Let H() be a hash function that maps to elements in the space (1, 2, …, q-1).

To form a traditional (non-blind) Schnorr signature on the message M, the signer picks a random k between (1 and q-1) and computes the signature (r, s) as:

r = g^k mod p,     s = (H(M || g^k)*x + k) mod q

The symbol || indicates concatenation. Any party can verify this signature using the public key, by checking the following equality:

g^s == y^{H(M || r)} * g^k     mod p 

To turn the above into a blind signature, the user and the bank engage in the following protocol.

  1. The bank picks k as above, and generates r = g^k mod p. It sends r to the user.
  2. The user now picks random a, b in (1, … q-1) and computes (r’, e’, e) as:

    r’ = r*(g^a)*(y^b) mod p
    e’ = H(M || r’)
    e = e’ – b mod q

    She sends e to the bank and retains the rest.

  3. The bank computes s = ex + k mod q and returns s.
  4. The user computes s’ = s + a mod q. The pair (r’, s’) is a valid signature on M.
Whew! Ok, note that the bank sees only the value e, which is based on a hash of M, but is blinded by the random factor b. This ensures that the bank does not learn anything about M.
The intuition for correctness is a little bit more complicated, and I’m going to leave it for the reader to work out. But it too holds: the new pair (r’, s’) is also a valid solution to the signature verification equation described above.
Blind DSA signatures are quite a bit more complicated, but can also be accomplished. See this paper for a protocol.
Are there other blind signature schemes?
Tons. My favorite is the Camenisch-Lysyanskaya class of signatures, which allow you to extract signatures on message vectors — lists of messages — then show the signature on any subset at all. This signature scheme is the basis of many anonymous credential schemes, as well as some eCash protocols. There are also many more recent blind signatures in newer settings, such as bilinear groups.

Selectively revealing a cheater’s identity

The problem of revealing a user’s identity (on double spend) is kind of an interesting one.

The first proposal actually comes from Chaum, Fiat and Naor, but that one’s a little complicated. For discussion purposes, it’s probably easier to talk about this later scheme by Stefan Brands.

Brands’ scheme is neat because it actually turns a known vulnerability of signature schemes like Schnorr and DSA into an asset that prevents double-spending.

You might remember I mentioned in a previous post that there’s a serious concern in signature schemes like DSA. These schemes use a random nonce value, and if that nonce is ever re-used twice (with two different messages), anyone can recover the signer’s key. Brands’ scheme actually turns this weakness into a feature: speaking at a very high level, each coin withdrawn from the bank consists of a bank-signed secret value and a single secret nonce (broken into pieces).

Spending a Brands coin is something like making a signature using this key and nonce; the user can do it once with no worries, but the second time she does it, anyone can recover her key.

This is a pretty rough, inaccurate intuition. For a much more detailed explanation of Brands’ scheme, see here.

2 thoughts on “A note on blind signature schemes

Comments are closed.