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:

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.

Blind DSA signatures are quite a bit more complicated, but can also be accomplished. See this paper for a protocol.

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.