In the last installment, I described a particular technique that could be used for signatures based on discrete logs. (There are many DL-based signature algorithms, but this particular one lends itself to the blinding technique.) I should point out that this signature is due to Chaum, and in fact everything I will discuss comes from Chaum's work. Brands goes on to develop some nifty cash systems based on it, but his extensions are too complicated to touch on more than briefly.

Blind signatures are, IMO, the key to anonymous digital cash, and in fact to many forms of anonymity. The ability to engage in mutual information manipulation with another person, while guaranteeing that no linkage will later be possible between the data exchanged and the results of that calculation, is the foundation for interacting in a complex way without losing any privacy. The significant feature of the blind signature I will describe here is that it is a "restrictive" signature. In the original Chaum blinding technique, there were no limits on what was actually being signed. With this restrictive blinding, only a limited set of transformations are possible between what is seen by the signer and what is later exhibited as the signature. These transformations fully protect privacy, but the restrictions protect the interests of the signer and end up simplifying the protocols (which were complex just to protect his interests).

Recall that there were two kinds of DL-based signatures I discussed earlier. In the interactive signature, Vicki the verifier came up with a challenge number c which she went to Paul the prover (signer). Paul produced a response r which depended on c, and using r, c, and the other numbers from the protocol Vicki is able to check and confirm the signature. In the noninteractive signature, the challenge number c is calculated as a cryptographic hash function of the other numbers, and r is again shown based on c. Vicki no longer has to interact with Paul; she (or anyone else) can confirm the signature based on r, c, and the other numbers. The hash function basically takes the place of the interactive verifier, and since it is cryptographically strong c is essentially random.

The blind signature basically combines these two techniques. Vicki wants to end up with a non-interactive signature on m', which is a special transformation of m. To do this, she engages in an interactive signature protocol with Paul, getting him to sign m. But the c she sends to Paul is an easilyundoable blinding of c', which comes from the cryptographic hash function applied to m' and the other numbers. The r she gets back is then easily transformed into an r' that works with the cryptographic hash. The result is that she ends up with a non-interactive signature on m' because Paul was willing to participate in an interactive signature session on m, and Vicki chose the c carefully so it would work in the final signature she shows.

(This shows, BTW, that it is not safe in general to have a system which uses both interactive and non-interactive signatures using the same keys. This technique allows non-interactive signatures to be produced from interactive sessions on different numbers. In the blinding protocol, Paul knows what Vicki is up to, and he willingly goes along with the blind signature. Similar problems were pointed out long ago with RSA signatures.)

Now for the mathematics. Recall the g is the "generator" of the group, the base of all of the powers. x is Paul's secret key, and GX=g^x is his public key. The relationship between m', which is what Vicki will end up with a signature on, and m, which is the number that Paul sees, is

m' = (m^s)*(g^t).

In other words, a signature may be blinded by being taken to any power, and multiplied by any power of the generator g.

This means that if Paul puts some restrictions on the m that he is willing to sign, Vicki will not in general be able to end up with a signature on an arbitrary m' of her choice. Due to the difficulty of the discrete log problem, she cannot in general find s and t such that (m^s)*(g^t) is a desired m'. Instead, she can do little better than to choose s and t at random and just accept whatever m' comes out.

As the first step of the interactive protocol, Paul chooses a random w and sends Vicki MX = m^x, GW = g^w, and MW = m^w. In the non-interactive signature, the challenge c is calculated as the hash of (m,MX,GW,MW). Vicki must transform these numbers so that Paul will not recognize them, but in such a way that the mathematical relationships are maintained.

To do this, Vicki chooses two (more) random numbers, u and v (along with s and t above). These will be such that w'=u*w+v, although Vicki never knows w (or w'). Then she calculates her numbers as follows:

MX' = m'^x = ((m^s)*(g^t))^x = (m^(s*x))*(g^(t*x)) = (MX^s)*(GX^t) GW' = g^w' = g^(u*w+v) = (g^(u*w))*(g^v) = (GW^u)*(g^v) MW' = m'^w' = ((m^s)*(g^t))^(u*w+v) = [...] = (GW^(u*t))*(MW^(u*s))*(m'^v)

These are not that hard given the definitions above, except for that last one, where I skipped a few steps :-).

Using these, Vicki calculates her hash c'= Hash(m',MX',GW',MW'). Now, the c she sends to Paul will be used to calculate r = c*x+w. She wants to end up with r' = c'*x+w' . This can be achieved by the following two transformations, based on w'=u*w+v:

c = c'/u
r' = u*r + v

This c is sent to Paul, and the returned r is transformed to r'. The resulting signature on m' is (MX',GW',MW',r'), and it is perfectly valid just like any other non-interactive signature using this signature function.

Well, the mathematics are a little complicated, I know. The main things to take away are that the restrictive blinding does require some interaction with the signer in order to end up with a non-interactive signature, and that the limitations on the blinding which can be done are to take the signed number to a power and multiply it by some power of g.

There are a couple of easy applications of the simple blind signature. (I made both of these up based on Brands' hints, so if there are problems with these specific examples please don't blame him.)

The blind signature by itself is perfectly suitable for on-line cash. The cash could be represented as any signed value using a particular secret key. Unlike with RSA signatures, it's not possible to conjure up a bunch of perfect 3rd powers (or whatever). The only way to come up with anything that satisifies the tests for a valid signature is by participating in the algorithms above. So by itself (MX',GW',MW',r') and m' could constitute a "piece" of digital cash. It would be anonymous and untraceable just like the simple Chaum online cash.

Another nice application is to a system of pseudonyms and credentials. Chaum originated this idea but his implementation was complicated and clumsy, involving cut-and-choose, hundreds of discarded validator terms, and other messy stuff. Using Brands' technology each person could have an identity string I, and get that signed by the validator-issuer, reblinding it to be I^s which would be the pseudonym at a given organization (you don't need the g^t term for this application). Instantly we have constrained pseudonyms to be of the desired form without any mess.

Now if you get a credential from some organization ("good credit risk"), and want to show it on your pseudonym at another organization, you get them to sign I^s and reblind that to be a signature on I^s'. You can do this by taking I^s to the s'-s power, an allowed transformation under the blinding rules. And you can't turn it into a signature on some other person's pseudonym because there is no way to know what power I^s would have to be taken to to get I'^s for some other I' due to the DL problem.

So, pseudonym/credential systems practically fall in your lap with this signature, and Brands has been able to extend his ideas a very long way along these lines. He has all kinds of different rules which can be applied by modifying the basic idea. I hope that he will be able to publish his results soon so that we can see what the possibilities are.

Hal Finney
hfinney@shell.portal.com
.