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 signatures 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 credentials 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=