Last year, Stefan Brands announced that he had come up with improved versions of Chaumian cash and credentialling protocols which were smaller, faster, and had provable correctness. He still hasn't gone public with them, but I thought I'd write up an introduction to his earlier work so people can see what direction things are going. IMO, if he plays his cards right his technology could be the foundation for electronic commerce. OTOH if he is too greedy he'll be bypassed. It appears he is seeking patents on everything, a necessary step for commercial interest, but we'll see how he markets it. This is based on Brands' "An Efficient Off-line Electronic Cash System Based on the Representation Problem", which was available on the net for a while before he took it off. I'm not sure what its status is now. Perhaps he removed it pending release of his improved version. Brands' work is based on discrete logs rather than RSA. The discrete logarithm problem is the "other" widely-used foundation for crypto primitives, underlying Diffie-Hellman key exchange, ElGamal, Schnorr, and DSS signatures, and many others. I'll do a brief intro to using discrete logs and then get to Brands' cash. Discrete-log based cryptosystems generally work with a modulus n which is prime, along with a "generator" g < n such that the series g^0, g^1, g^2, ... , includes all values from 1 to n-1. It is pretty straightforward to find such n's and g's. It is easy to compute g^x for any x, but intractable to calculate x given just g^x. (Notation: ^ represents exponentiation, and all math is implicitly mod n). x is called the discrete log (to the base g) of g^x and the difficulty of solving this is the foundation of these protocols. Note that unlike RSA, where taking eth roots is hard for everyone except the owner of the secret key, taking discrete logs is hard for everyone, without exception. There is no trap door here. Diffie-Hellman key exchange As an introduction, consider Diffie-Hellman key exchange. In this protocol, two people, Alice and Bob, want to publicly exchange data and end up with a secret value which only they know. 1. Alice chooses a random x and sends GX = g^x to Bob. Bob chooses a random y and sends GY = g^y to Alice. 2. Alice calculates GY^x, which is g^(y*x). Bob calculates GX^y, which is g^(x*y). 3. These are equal, so they use them as their shared secret value. An observer sees only GX and GY, and without knowledge of x and y is unable to calculate g^(x*y). DH-based identification protocol An identification protocol allows someone to prove that he is really who he claims. In this context, the prover Paul will convince the verifier Vicki that he knows the secret key corresponding to Paul's established public key. In this and the following systems, Paul has a secret key x<n, and a public key GX = g^x. Again, note that it is impossible to go from GX to x assuming discrete logs are hard. 1. Vicki chooses a random y and sends GY = g^y to Paul. 2. Paul calculates GYX = GY^x = g^(y*x) and sends that back to Vicki. 3. Vicki confirms that GYX = GX^y; both should be g^(x*y). This is like DH except that Paul exposes the secret information he calculated, and only he could have done this. One problem with this protocol is that perhaps Paul calculating xth powers for Vicki might reveal something about x. The next protocol solves that: Schnorr identification protocol This comes from Schnorr, Journal of Cryptology, v4 n3, 1991. 1. Paul chooses a random w and sends GW = g^w to Vicki. 2. Vicki chooses a random c and sends it to Paul. 3. Paul calculates r = cx+w and sends that to Vicki. 4. Vicki confirms that g^r = (GX^c)*GW. Both should be g^(cx+w). The extra step of Paul sending g^w for a random w makes this protocol reveal less information about x. For any one run of the protocol, there is some value of w which would produce a given r for any x, so knowing r and c doesn't tell you anything about x. Chaum discrete-log interactive signature protocol This is the basic signature used by Brands, but I believe it comes from Chaum&Pederson, Crypto 92. It is an extension of the previous protocol to allow signatures. A digital signature on a value m is a certificate which could only have been produced by the owner of a particular public key. In this protocol, a message m (<n) is being signed. The basic signature value is MX = m^x, which Paul sends. By itself, though, this signature is not obviously correct. Without knowing x, Paul's secret key, there is no way to confirm it. So, Vicki must engage in an interactive protocol with Paul in which he will prove that MX is equal to m^x. It is very similar to the previous one: 1. Paul chooses a random w and sends GW = g^w and MW = m^w to Vicki. 2. Vicki chooses a random c and sends it to Paul. 3. Paul calculates r = cx+w and sends that to Vicki. 4. Vicki confirms that g^r = (GX^c)*GW. Both should be g^(cx+w). She also confirms that m^r = (MX^c)*MW. Both should be m^(cx+w). This is the previous protocol plus one extra number, MW. The fact that the same r is used for both m and g shows that m was raised to the same power as g in creating MX vs GX. Chaum Discrete-Log Signature Protocol Interactive signature protocols may have advantages in some circumstances, but in most cases we would prefer a signature which can be checked without help from Paul. There is a simple trick which can turn most interactive signature protocols into regular signatures. The idea is that instead of c being chosen at random by Vicki, it is calculated by using a cryptographically strong hash function (such as MD4, MD5, or DHS) on the values which are publicly known by that point in the protocol: m, MX, GW and MW. Since both Paul and Vicki could calculate the hash, there is no need for Vicki to send c to Paul. Instead, he can do everything in one step. This leads to: 1. Paul calculates MX = m^x. He then chooses a random w and calculates GW = g^w and MW = m^w. He then calculates c = hash(m,MX,GW,MW). He calculates r = cx+w, and sends MX, GW, MW and r to Vicki. The tuple (MX,GW,MW,r) is the signature on m. 2. Vicki calculates c = hash(m,MX,GW,MW). She then verifies, as before, that g^r = (GX^c)*GW. Both should be g^(cx+w). She also confirms that m^r = (MX^c)*MW. Both should be m^(cx+w). This protocol is not interactive. Once Paul has completed step 1, the signature can be published and anyone can play Vicki's part in checking it. Such a signature is functionally similar to the PGP signatures we see on messages on the net, but as you can see the mathematics behind it is completely different. OK, that's all for now. Next comes the good part: blind signatures. Unlike Chaum's original blind signatures, which are the foundation of his cash system, the discrete-log blind signatures have "restrictive blinding", where there are limitations on what kinds of changes can be made to the number being signed during the blinding process. This allows Brands to dispense with the clumsy cut-and-choose techniques Chaum was forced to use in his advanced cash and credential systems. I'll write more about this later today or tomorrow. Hal
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 non- interactive 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 trans- formation 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 easily- undoable 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 inter- active 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
-----BEGIN PGP SIGNED MESSAGE----- OK, for those who have stuck with me so far, I will describe a slightly simplified version of Brands' off-line cash. Users' anonymity is protected unless they double spend. (At last we are departing from Chaum and getting into some of the territory blazed by Brands.) The first thing that is done is that the value which is signed by the cash issuer in the creation of the cash encodes some information which represents the identity of the user. Let's call the user Irving, and the number which encodes his identity (it might just be his bank account number in this case) we will call I. The rule is that the issuer will only sign values which are of the form d*g1^I, where d is a fixed number used in the cash system, and g1 is another fixed value which is used here similarly to the g of the signature protocol itself. (d can actually encode the denomination by having a few different d values that are used, or else denominations can be encoded by different secret-key x values of the bank as is done in Chaum's cash.) As in a simplified version of the on-line cash, the signature is blinded to m' by raising it to the power s (we don't multiply by g^t here), getting a number m' of the form (d^s)*g1^(I*s) for random s. This totally masks Irving's I so it is not revealed in normal use. Now, the next new step is that Irving divides this m' value into two parts, called A and B, such that A*B equals m'. This can only be done (due to the discrete log problem) by having A=(d^x1)*(g1^y1) and B=(d^x2)*(g1^y2) such that s=x1+x2 and I*s=y1+y2. In other words, the exponents on d and g1 are split randomly into two parts and these used to form A and B. If anyone can find out s and I*s after the cash is spent, they can learn Irving's identity. They know m', A, and B, because they get revealed when Irving spends (as shown below). But this is not enough to learn s & I*s. If you find out x1, x2, y1, and y2, though, this allows s and I*s to be deduced, and therefore also breaks the anonymity. In spending the cash, Irving must reveal the signed m', along with A and B. (B can actually be deduced as m'/A.) Then, the store comes up with a challenge c (this is a different c than in the withdrawal protocol). Irving has to reply with two numbers: x1+c*x2, and y1+c*y2. This is pretty scary! He's really putting his cojones on the line, here. s(=x1+x2) and s*I(=y1+y2) will give him away, and here he's revealing a simple linear combination of x1&x2, and y1&y2. But he's actually safe in doing so - as long as he doesn't double-spend. x1+c*x2 still perfectly blinds x1 and x2, since nothing is known about these values, and likewise for y1 and y2. Just like in the original signature protocol where Paul gave away c*x+w, x his secret key, this is safe. (Well, it does appear that he should make sure c!=1. Then he would be telling x1+c*x2 = x1+x2, which is what he doesn't want to give away!) Irving might be tempted to lie about x1+c*x2 and y1+c*y2, but if he does he will be caught. The shop calculates A*(B^c), and this should be equal to d^(x1+c*x2)*g1^(y1+c*y2). Once this is verified, the shop, having checked the signature on m', accepts the cash. Now consider what happens if Irving tries to spend the cash again. This second shop will produce a different c challenge; call it c'. Again Irving must respond with x1+c'*x2 and y1+c'*y2. But now his goose is cooked. Once the bank gets the information from both shops it knows both x1+c*x2 and x1+c'*x2, and it knows c and c', so it can deduce x1 and x2. Likewise it can calculate y1 and y2. Adding these up gives s and I*s, and dividing these gives Irving's identity I. He's caught. There is one significant complication I have skipped over here, and that is the possibility that Irving could choose different A and B values (always with A*B=m') each time he spends. Then the x's & y's would be different each time and he wouldn't get caught. This is avoided by making a small change to the signature-checking algorithm. Earlier recall that a non-interactive signature on m' was defined by (MX',GW',MW',r'), and that it was checked by setting c'=Hash(m',MX',GW',MW'), and doing the special calculation with c' and r'. For this off-line cash we make a small change, which is that the hash function is calculated as c'=Hash(m',MX',GW',MW',A,B). We include the A and B in calculating the hash function. The bank never sees A and B, just like it never sees any of the other values in the hash function, but c' depends on them. If Irving tries to change A and B, then the c' which the shop calculates (using this longer hash formula) will be different, and it won't work with the r' that Irving got back from the bank. So by including more terms in the hash input we in effect get those things signed as well in a blinded way by the bank. (I think a similar hashing trick is how Schnorr signatures work, BTW). Once again, this protocol looks complicated, but compare it with Chaum's original off-line cash: there is no cut and choose, and the amount of data exchanged at each step is not very large, a few multi-precision values. I wrote up a long description of Chaum's off-line cash at a similar level of detail to this one, and I really think Brands' cash is far superior. Hal Finney -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLllXXKgTA69YIUw3AQHdFQP7BNop9S9RihTKEyBZCEvB7JD7SkGth+uk eftNFTjjGyKsxFeeyE1wK14G5N/55I7g7ADhSO36BRPrj0Wyv8Z9lpWP0fLA02Ga mCJnaspPN8oF29Jd/uuA7Sqa62FkIUW0MolWLIcqCshmrL6fG0dOZrhh34fBi/+o cOjp8H17ziM= =CVfC -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- A few closing notes on Brands' technology: There is a trick which is used in a lot of the discrete-log algorithms which reduces the storage space needed and speeds up the calculations by a factor of up to 4. Originally I described the generator g as being one whose order is equal to n-1; that is, the series g^0, g^1, ...g^(n-1) encompasses all the numbers from 1 to n-1 before looping. However, it turns out to be advantageous in many cases to choose a generator which has a smaller period. The period of the generator must be a divisor of p-1, as it turns out. Choosing a generator with period q, a prime which divides p-1, allows all of the results to continue to work as long as a couple of small changes are made. Exponent arithmetic must be done mod q, since that is the "wrap around" point. For example, where the signature algorithm does r=c*x+w, this would be done mod q. (It actually needs to be done mod n-1 in the full-cycle-generator case, but I didn't get into that detail.) The other thing that has to be done is that when random numbers are chosen, they should be from 1 to q if they are exponents (as in the case of w from the signature algorithm), and they should be in the group generated by g (that is, the set of values g^0, g^1, g^2, ...) if they are bases (like g1 and d in the off-line cash algorithm). A typical set of values for q and n are 140 bits and 512 bits. This is what is used in the government DSS (at least in the first version; I'm not sure what other options they came up with). This means that exponentiation only has to be done to 140-bit powers rather than 512-bit powers, which only takes about 1/4 as long. It also means that everywhere in the protocol that an exponent is stored or transmitted only about 1/4 as many bits have to be sent. Yet even with these smaller exponent values solving the discrete-log problem is believed to be as difficult as with full-sized exponents. Sometimes people ask how the difficulty of discrete-log compares with factoring. I haven't been able to really get a clear answer on this. One quote on sci.crypt last year said that discrete-log for 1024 bits is harder than factoring for 512 bits, and likewise factoring for 1024 bits is harder than discrete-log for 512 bits. But this isn't saying much considering the 1024 bit problems are probably a million times harder than the 512 bit problems. I've sent email to Brands every few months gently hinting about when he might be willing to publish his results. Originally he was going to publish earlier this year, but then he decided to hold off for a few months while he looked for investors. I don't know what luck he has had with that, but recently he said that he'd be publishing before the end of 1994. I sent him my ideas for a pseudonym/credentialing system, and he very kindly said that he used similar concepts for some of his technology. However, a limitation of my idea was that a credential can be transferred only to one specific other pseudonym, although the credential issuer does not know what pseudonym it is. Brands said this is one of the types of credentials he can do, but that he also uses "a different mechanism" to provide for credentials which can be shown at any shop where one has a pseudonym. I haven't been able to figure out how to do that. One nice thing about this credentialling system, BTW, is that the credentials can be issued by the shops/companies themselves. In Chaum's system only one agency can give credentials. That is because RSA sig- natures are used, and you can't have two different RSA signers both share the same modulus n. (They would both have to know the factors.) But with the discrete-log signatures, many people can share the same n, have their own secret keys x, and issue signatures. So, at least with the simplified credentials I described, shops can issue their own cre- dentials in the form of signatures on pseudonyms which were validated by the validating agency using its own signatures. Everyone would share the same modulus and therefore be able to make their own signatures. Hal Finney -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLlnlIagTA69YIUw3AQGGYgQAl2ZW5Wsg/+RNbPn9g83jQKA3BwZqdKJc pOf22GlED8/DUCcNDd6Sh3aXg5puWsVudNgMFlRQ8IzNUMAxsabjLZ0BU1xFgojG AH9zo98Yvb+QJ5Nc1EpbvCJmkcJiv4q2rdPrSE/CiOCWbZju2re548E6SrRzo/Ce usGYHLWtU5E= =F9is -----END PGP SIGNATURE-----
participants (1)
-
Hal