From: Hal <hfinney@shell.portal.com>
Date: Thu, 25 Aug 94 09:23:46 PDT
To: cypherpunks@toad.com
Subject: Re: Brands cash
In-Reply-To: <199408201652.JAA29752@jobe.shell.portal.com>
Message-ID: <199408251623.JAA22878@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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