Brands cash

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