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

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

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

- The bank picks
*k*as above, and generates*r = g^k mod p*. It sends r to the user. - 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 qShe sends

*e*to the bank and retains the rest. - The bank computes
*s = ex + k*mod q and returns*s*. - The user computes
*s’ = s + a mod q*. The pair*(r’, s’)*is a valid signature on M.

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

*(r’, s’)*is also a valid solution to the signature verification equation described above.

**Are there other blind signature schemes?**

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

This is really technical and it's pretty rough too. But you really made it simple to understand and it's very accurate. Thanks for sharing this one.

Thanks a lot for a concise and yet pretty informative note on blind signatures!