by J. Orlin Grabbe
Note: In order to read the following text properly, your web browser must be able to handle subscripts and superscripts; i.e. the html commands "sub" and "sup". These commands are used as necessary.
A. General Features
Here we will step through the details of a digital cash system created by Stefan Brands, while a Ph.D. student at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Brands' offline digital cash system allows the upfront prevention of doublespending (using an observer), yet maintains complete user privacy provided no double spending takes place. The revelation of identity under doublespending is a backup precaution to observer failure.
Brands' system is laid out in a series of CWI technical reports with varying notation. The basic system is based on discrete logarithmsin particular the representation problem. The security of the system depends on the existence of a collisionfree hash function and the difficulty of finding discrete logarithms. There is, however, a variant of the system which uses RSA, in which case the security of the system supposedly depends on the existence of a collisionfree hash function and the difficulty of factoring. (I say "supposedly," because this is the consensus on RSA security. But I believe that RSA is less secure than factoring.)
Some importants features of the system include these:
Brands' scheme uses a Schnorrtype protocol both at withdrawal of digital cashwhere the bank performs a restrictive blind signatureand also in interaction with the merchant, where the customer does a Schnorr proofofpossession (shows knowledge of a representation) as a challengeandresponse. The system's security hinges on the security of the signature scheme. More than one signature scheme can be implemented.
Brands' offline cash system is just one instance of a general technique: namely a credentialsharing system in which credentials that are shown only once can be transferred between "organizations", while privacy is guaranteed. For example, an offline cash system can be constructed in which payments are made under a pseudonym. Then, in order to pay with a coin, an account holder need send no more than 35 bytes to an "organization" at which he has a pseudonym.
With this introduction, let's look at the different pieces of Brands' digital cash system, then combine them into a workable whole.
B. Restrictive Blind Signatures
Restrictive blind signatures are used in the protocol to withdraw digital cash from the bank. Each withdrawn coin is represented as a unique piece of digital information containing the bank's digital signature. Recall that a blind signature allows one to obtain a signature on a message (on digital cash, in this case) in such a way that the message itself remains unknown to the signer.
We begin with a generator g of a group G(q) of prime order q mod p, and the public key h of the signer: h = g^x. Here x (the power) is the signer's private key, which can only be discovered by taking discrete logarithms: x = log_g (h). Note that this publicprivate key pair differs from the RSA system, but corresponds to the public/private key pairs in the Digital Signature Algorithm.
All calculations are done modulo p, for some large prime p, unless otherwise stated. The powers of each generator g produce each of the q numbers in G(q), and the prime q divides p1. This means 1 = g^q = g^(p1) mod p.
Let M denote a message. This message may be anything, including a piece of digital cash to be signed. To sign this message, the bank will raise it to the power x mod p, yielding
[1] z = signed(M) = M^x.
Now, let's introduce some a few terms to make it easier to keep track of various pieces of the protocol. (This terminology is my own, and not that of Stefan Brands or ChaumPederson, from whom some of the basics of the scheme are derived.) If we raise the message M to a random power w, we will call the result b a pseudo signature. That is,
[2] b = pseudosigned(M) = M^w.
The public key of the signer is a generator g raised to the power x. So let's call the generator g raised to a random power w a pseudopublic key. Label this a. Thus we have
[3] public key h = g^x,
[4] pseudopublic key a = g^w.
We now have the essential elements that will be used in the restrictive blind signature scheme (see Table 1). Remember that h, g, q, and p are already known to both parties, before anything takes place.
The steps in the restrictive blind signature protocol are as follows (all calculations in this protocol are done mod p, unless otherwise stated):
Step 1: The receiver (customer) sends a message (piece of digital cash) M to the signer (the bank). It is intended that the bank sign M with its secret key x (yielding z = M^x) and to also supply a signed proof about x using the bank's public key h; namely, that log_g (h) = x = log_M (z). The proof is to guarantee to the customer that the bank has signed M with a valid signature; namely with its secret key x.
primes p, q where q divides p1
generator g of G(q) in Z(p)*
message M
signer private
key x
signer random
number w
signer public
key h = g^x
mod p
signer pseudopublic
key a = g^w
mod p
signed
message z =
M^x mod p
pseudosigned
message b =
M^w mod p
collisionfree hash
function H
challenge from
receiver c
signer response to
challenge r
= w + c*x mod q
verification that
signature x is on
g (g^x=h) and M
(M^x=z)a*h^c = g^r mod p
b*z^c = M^r mod
p
receivergenerated random numbers s, t, u, v
blinded
message M' = M^s * g^t
signed blinded
message z' = z^s*h^t = M'^x
blinded pseudo
public key a' = a^u*g^v = g^w'
blinded pseudo
signed message b' =[a^(u*t)]*[b^(u*s)]*M'^v = M'^w'
equivalent
blinded intercept w' = u*w + v mod q
blinded challenge
(hash value) c' = H(M', z', a', b')
returned
challenge to signer c = c'/u mod q
receiver
calculated response r' = v + u*r = w' + c'*x mod
q
Step 2: The signer (the bank) generates a random number w and sends to the receiver (customer) the following elements:
the signed message z = M^x
the pseudopublic key a = g^w
the pseudosigned message b = M^w.At this point the customer now has two objects signed with the bank's private key x: namely, the signed message z = M^x and the bank's public key, which is itself a "signed" generator h = g^x. The customer also has two objects pseudosigned with the random number w: the pseudosigned message b = M^w and the pseudopublic key a = g^w. These additional objects will allow the bank to give a zeroknowledge proof that it has performed a valid signature on M with its private key x. That is, a and b will be used to verify a relationship with respect to the customer's challenge c (in Step 5, below).
Step 3: The receiver (customer) generates a challenge c. To do this, the customer first generates four random numbers: s, t and u, v. Using s and t, the customer computes modifications of M and z, namely the blinded message M' and the signed blinded message z':
[5] M' = M^s * g^t (blinded message)
[6] z' = z^s*h^t
= (M^x)^s*(g^x)^t
= [M^s*g^t]^x
= M'^x (signed blinded message)So at this point the customer has a valid signature on the transformed message M', which is unknown to the bank. The original signed message z has been "blinded" by raising it to the power s and multiplying it by h^t.
Using u and v, the receiver (customer) computes modifications of a, and b, namely, a', and b':
[7] a' = a^u*g^v = (g^w)^u*g^v = g^w',
[8] b' = [a^(u*t)]*[b^(u*s)]*M'^v
= [(g^w)^(u*t)]*[(M^w)^(u*s)]*M'^v
= [(g^t)^(u*w)]*[(M^s)^(u*w)]*M'^v
= [M'^(u*w)]*M'^v
= M'^w'.where
[9] w' = u*w + v mod q.The customer then computes the hash value
[10] c' = H(M', z', a', b'),
and sends to the bank the challenge c:
[11] c = c'/u mod q .
Step 4: The signer (bank) responds with
[12] r = w + c*x mod q.Notice this is a point on a line with slope x (the secret key) and intercept w.
Step 5: The receiver (customer) uses the challenge c and the response r to check that
[13] a*h^c = g^r
and
[14] b*z^c = M^r .
If so, the receiver accepts the signature.
Note that in Step 5, if the bank has responded with the proper value of r, namely r = w+c*x, then
and alsoa*h^c = (g^w)*(g^x)^c
= g^(w+c*x)
= g^r
b*z^c = (M^w)*(M^x)^c= M^(w+c*x)
= M^r .
Step 3 may look confusing. But it is just a formalized way of generating the challenge c in such a way that the signer (bank) does not know the transformed message M', which has a valid signature z' = M'^x. Neither can the bank link transactions by manipulating the random number w, since this has been effectively modified to a new value w'.
The receiver (customer) can also compute
r' = u*r + v mod q= (u*w + v) + u*c*x mod q
= w' + c' *x mod q.
Here r' is the proper response to the challenge c', but is, however, only known to the customer and not the bank.
C.The Basic Digital Cash System.
1. Preliminary Setup
There are three participant types in the basic digital cash system: a bank banque, a merchant or shop S, and a customer or user U. U can also be thought of as the user's smart card, personal digital assistant, or computer.
The bank banque chooses three generatorsg, g_{1}, g_{2}from G(q) in Z(p)*. The bank also selects a secret key, or exponent, x, 1< x < q, and announces its public key h = g^x mod p.
The bank additionally needs two collisionfree hash functionsH and H_{o} . Each of H and H_{o} has as its output a member of the set Z(q)* = {1, 2, ..., q1}. H takes as its input set any five members of G(q), while H_{o} takes as its input set any two members of G(q), along with two additional variables SHOPID and DATETIME:
H(g_{a}, g_{b}, g_{c}, g_{d}, g_{e}) = k, where k is some member of Z(q)*,
H_{o}(g_{f}, g_{g}, SHOPID, DATETIME) = k', where k' is some member of Z(q)*.
The bank announces p, q, g, g_{1}, g_{2}, h, H and H_{o} as public information, but keeps x secret.
A coin issued by the bank is a piece of signed digital information. For simplicity, we will assume that all coins have the same size (say $100). This will make the mathematics simpler in the following discussion. But the system can be readily modified to allow for coins of different value. Both the user U and the bank banque are involved in the production of a coin, as both supply random information used in its creation.
Definition: a
coin is two numbers A, B, and a
signature on A and B composed of four numbers where
c = H(A,B,z,a,b).

Note that this definition looks exactly like equations [13] and [14], as it should, since the coin is the signed message outcome of a restrictive blind signature. Now, where the different numbers in the coin definition come from is explained in the following two sections. But, briefly, is a challenge issued by the user U to the bank banque. The number r is a response to that challenge. The number g is a generator announced by the bank, while h is the bank's public key. The number z is the bank's signature on some customer identifying information. The origin of A, B, a, and b will be explained presently.
2. Opening an Account.
The user has public/private key pairs. These are not used in the protocols that follow so will not be denoted by individual symbols. But we require that the user be able to send digitally signed messages to the bank.
To open an account, the user U generates a random number u_{1} from Z(q)*, and computes an identifier or public key
[15] h_{u} = g_{1}^u_{1} mod p .
The user checks that h_{u}*g_{2} is not equal to 1 mod p, and if so sends h_{u} to the bank, keeping u_{1} secret. The bank stores h_{u} along with any other information it requires on U. The bank computes and returns to the user U a signature with its secret key x as follows:
[16] z = (h_{u}*g_{2})^x mod p .
primes p, q where q divides p1
generators g, g_{1}, g_{2} of G(q) in
Z(p)*
secret identifier
key of user u_{1}
user public
key h_{u} = g_{1}^u_{1}
mod p
equivalent
identifier signed by bank M = h_{u}*g_{2}
bank's private
key x
bank's random
number w
bank's public
key h = g^x
mod p
bank's pseudo
public key a
= g^w mod p
banksigned user
identifier z
= M^x mod p
bankpseudo
signed user identifier b = M^w mod p
collisionfree
hash function H
challenge to
bank c
bank's response
to challenge r = w + c*x mod q
verification that
signature x is on g (g^x=h)
and M (M^x=z)a*h^c = g^r mod
p
b*z^c = M^r =
(h_{u}*g_{2})^r mod p
user
generated random numbers s, x_{1}, x_{2},
u, v
blinded user
identifier (coin element) A = M^s =
(h_{u}*g_{2})^s
additional coin
element B =
g_{1}^x_{1}*g_{2}^x_{2}
signed blinded
user identifier z' = z^s = A^x
blinded pseudo
public key a' = a^u*g^v
blinded pseudo
signed user identifier b' = b^(s*u)*A^v
equivalent
blinded intercept w' = u*w + v mod q
blinded challenge
(hash value) c' = H(A, B, z', a', b')
challenge
returned to bank c = c'/u mod q
usercalculated
transformed response r' = v + r*u = w' + c'*x mod
q
coin
definition {A, B, (z',a',b',r')}, where
a'* h^c' = g^r' mod
p
b'*z'^c' = A^r'
mod p
c' =
H(A,B,z',a',b')
challenge from
shop d
= H_{o}(A, B, SHOPID, DATE
TIME)
user response to
shop challenge r_{1} = d*(u_{1}*s) +
x_{1} mod q
r_{2} = d*s +
x_{2} mod q
shop
verification A^d*B =
g_{1}^r_{1}*g_{2}^r_{2}
mod p
Note that this last relationship, equation [16], is the same as equation [1], where in this case the message M = h_{u}*g_{2} . The representation of z (in terms of g_{1}, g_{2}) is {u_{1}*x, x} because z = (g_{1}^u_{1}*g_{2})^x = g_{1}^(u_{1}*x)*g_{2}^x. The representation of M is {u_{1}, 1}.
3. Withdrawal Protocol.
Before the user U is allowed to withdraw a coin, U must first prove ownership of his account. Such proof will eliminate imposters. To do this, U sends a digitally signed coin withdrawal request to the bank. Next the following protocol is enacted. This protocol will generate the numbers defining the coin.
Step 1: The bank banque generates a random number w from Z(q)*, and sends the pseudopublic key a and the pseudosigned message b to the user U:
[17] a= g^w mod pStep 2: The user U generates three random numbers s, x_{1} , and x_{2} from Z(q)*. These are used to calculate
[18] b = (h_{u}*g_{2})^w mod p .
[19] A = (h_{u}*g_{2})^s mod p
[20] B = g_{1}^x_{1}*g_{2}^x_{2} mod p
[21] z' = z^s mod p .
Note that z' is a signature on A. That is, z' = z^s = [(h_{u}*g_{2})^x]^s = A^x. Hence A plays the same role as the blinded message M' in equation [5].
U also generates two random numbers u, v from Z(q)*. These are used to calculate
[22] a' = a^u*g^v mod p
[23] b' = b^(s*u)*A^v mod p
The user U then computes the the challenge c' as follows:
and then sends the blinded challenge c back to the bank banque:[24] c' = H(A, B, z', a', b')
[25] c = c'/u mod q .Step 3: The bank banque sends the response r :
[26] r = w + c*x mod qand debits U's account in the amount equal to the value of one coin.
Step 4: U accepts the debit only if
[27] g^r = a*h^c mod pNote that equations [27] and [28] are the same as [13] and [14], which we verified previously. The user U also calculates r':[28] (h_{u}*g_{2})^r = b*z^c mod p .
[29] r' = v + r*u mod q .
The coin is the set of numbers {A, B, (z',a',b',r')}. The user knows the representation or signature {z',a',b',r'} on the coin. Note, however, that in the withdrawal protocol described above, nowhere did we specify the denomination of the coin (say $100). Hence the limited system we are using here implicitly assumes all coins are of the same size. But the set of numbers {A, B, (z',a',b',r')} allows the user to prove that he made a coin withdrawal from the bank, and hence the set of numbers represents an obligation of the bank equal to one coin.
Now, if one can't forge the bank's signature, which involves x (see equation [16]), then one can't forge coins. There can't be more coins in circulation than there are coin withdrawals. But forging the bank's signature would require the ability to extract discrete logarithms. Moreover, no one else can spend this coin without knowing its representation (z', a',b',r').
4. Payment Protocol.
When the user U is ready to spend the coin, the following protocol is enacted between the user and the shop S
Step 1: The user sends {A, B, (z',a',b',r')} to S.
Step 2: The shop returns the challenge d:
[30] d = H_{o}(A, B, SHOPID, DATETIME) .
Step 3: The user U calculates the responses r_{1}, r_{2}:
[31] r_{1} = d*(u_{1}*s) + x_{1} mod qStep 4: The shop S accepts the coin only if
[32] r_{2} = d*s + x_{2} mod q
[33] A^d*B = g_{1}^r_{1}*g_{2}^r_{2} mod p
[34] g^r' = a'*h^c' mod p
[35] A^r' = b'*z'^c' mod p .
Recall that c' = H(A, B, z', a', b'), so the shop can calculate this value for itself. The other relationships may be verified as follows. Equation [33] follows from
Equation [34] follows fromA^d*B = (h_{u}*g_{2})^(s*d)*[g_{1} ^x_{1}*g_{2}^x_{2}] mod p
= g_{1}^(u_{1}*s*d+ x_{1})*g_{2}^(s*d+x_{2}) mod p
= g_{1}^r_{1}*g_{2}^r_{2} mod p.
g^r' = g^(v+r*u) mod pEquation [35] follows from
= g^(v+(w+c*x)*u) mod p
= g^(w*u+v)*g^(x*c*u) mod p
= (a^u*g^v)*h^(c*u) mod p
= a'*h^c' mod p.
A^r' = ((h_{u}*g_{2})^s)^(v+r*u) mod pIn equation [35], which is the analog of equation [28], the shop uses uses A = M' = (h_{u}*g_{2})^s instead of M = h_{u}*g_{2} to verify the coin in the protocol, because the shop does not see M, but only the blinded value M'.
= (h_{u}*g_{2})^(s*v+s*(w+c*x)*u) mod p
= [(h_{u}*g_{2})^(s*w*u)]*[( h_{u}*g_{2})^(s*x*c*u+s*v)] mod p
= [b^(s*u)]*[A^(x*c*u+v)] mod p
= [b^(s*u)]*[z'^(c*u)*A^v] mod p
= [b^(s*u)*A^v]*z'^(c*u) mod p
= b'*z'^c' mod p.
5. Deposit Protocol.
When the shop S is ready to deposit the coin at the bank banque, the shop sends the payment transcript consisting of the coin {A, B, (z',a',b',r')}, along with (r_{1}, r_{2}) and the DATETIME of the transaction. The bank already knows the SHOPID, which is used in the communication.
Step 1: The bank verifies equations [33] to [35] to see that this is a valid coin.
Step 2: If the coin is valid, the bank checks its database to see if the coin was spent previously (that is, the bank checks for doublespending).
a. If the coin is not in the database, then it was not previously spent. Hence the bank credits the account of S, and records the coin in the form
{A, B, DATETIME, r_{1}, r_{2}}.
b. If the coin is already in the database, then a fraud has occurred. If S previously deposited the coin, and the DATETIME are the same, then S is trying to deposit the same coin or transcript twice. The deposit is rejected for that reason. The bank knows the identity of the shop S responsible.
c. Otherwise, the coin has been doublespent, and the bank takes steps to unmask the doublespender. The bank has two sets of information on the coin:
{A, B, DATETIME, r_{1}, r_{2}}.
{A, B, DATETIME', r'_{1}, r'_{2}}.
Hence, the bank can calculate
(r_{1}  r'_{1}) / (r_{2}  r'_{2}) = [d*(u_{1}*s)  d'*(u_{1}*s)] / [d*s  d's]
= u_{1} mod q.
Thus it can check its database for the user identity (see equation [15])
h_{u} = g_{1}^u_{1} mod p.
In addition, the bank now knows u_{1} also, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of
u_{1} = log_g_{1} (h_{u}) mod p
serves as proof of the doublespending.
D. The Digital Cash System with Observer.
To incorporate an observerfor the prior prevention of doublespendingin this framework only requires a slight modification of the above procedure. The essential change is that the bank provides the user with an observer which contains a hidden random number o_{1} embedded in memory (ROM). In addition, when the user withdraws a coin from the bank, the observer itself creates a second random number o_{2} which is stored in nonvolatile memory (EEPROM). This second number is erased when the coin is spent in the payment protocol.
Since the basic equations in the modified protocols are very similar to equations [15][35], we will number the equations with the same numbers, but with an "O" appended to denote the "observer" equations (e.g. [15O] corresponds to [15]).
To open an account, the user U generates a random number u_{1} from Z(q)*, and computes the following number (an identifier or public key) which is sent to the bank
h_{u} = g_{1}^u_{1} mod p .The user keeps u_{1} secret.
The bank provides U with an observer (O), which has embedded within ROM a random number o_{1} from Z(q)*. The user U does not know what o_{1} is. The bank computes the observer public key h_{o} = g_{1}^o_{1} and issues the user identifier (account number) I,
[15O] I = h_{u}* h_{o} = g_{1}^(o_{1} + u_{1}) mod p,and stores I along with any other information it requires on U. The bank computes a signature using its secret key x as follows:
[16O] z = (I*g_{2})^x mod p,
and returns h_{o} and z to the user.
Note that, unlike previously, the user U does not know a representation of either z or M. If we set M = I*g_{2}, the representation of z (in terms of g_{1}, g_{2}) is {(o_{1}+u_{1})*x, x}, while the representation of M is {o_{1}+u_{1}, 1}. Neither party knows these representations; the bank doesn't know u_{1} and the user doesn't know o_{1} .
1. Withdrawal Protocol with Observer.
Before the user U is allowed to withdraw a coin, U must first prove ownership of his account, as before. To do this, U sends a digitally signed coin withdrawal request to the bank. Next the following protocol is enacted.
Step 1: This step is new. Here the observer O generates a random number o_{2} from Z(q)*. The observer calculates h_{c} = g_{1}^o_{2} and transfers this to the user U (i.e. the user's hardware or software).
Step 2: The bank generates a random number w from Z(q)*, and sends the pseudopublic key a and the pseudosigned message b to the user U:
[17O] a = g^w mod p
[18O] b = (I*g_{2})^w mod p .
Step 3: The user U generates four (not just three) random numbers s, x_{1}, x_{2}, and e from Z(q)*. These are used to calculate
[19O] A = (I*g_{2})^s mod p
[20 O] B = g_{1}^x_{1}*g_{2}^x_{2}* h_{o}^(e*s)* h_{c} mod p
[21O] z' = z^s mod p .
As before, z' is a signature on A. That is, z' = A^x.
U also generates two random numbers u, v from Z(q)*. These are used to calculate
[22O] a' = a^u*g^v mod p
[23O] b' = b^(s*u)*A^v mod p
primes p, q where q divides p1
generators g, g_{1}, g_{2} of G(q) in
Z(p)*
secret key of
observer o_{1}
secret identifier
key of user u_{1}
public key of
observer h_{o} = g_{1}^o_{1}
mod p
public key of
user h_{u} = g_{1}^u_{1} mod
p
user identifier
(joint public key) I = h_{o}* h_{u} =
g_{1}^(o_{1} + u_{1}) mod p
equivalent
identifier signed by bank M = I*g_{2}
bank's private
key x
bank's random
number w
observercreated
random number o_{2}
observer public
key in coin withdrawal h_{c} =
g_{1}^o_{2}
bank's public
key h = g^x
mod p
bank's pseudo
public key a
= g^w mod p
banksigned user
identifier z
= M^x mod p
bankpseudo
signed user identifier b = M^w mod p
collisionfree
hash function H
challenge to
bank c
response to
challenge r
= w + c*x mod q
verification that
signature x is on g (g^x=h) and M (M^x=z) a*h^c = g^r
b*z^c = M^r =
(I*g_{2})^rusergenerated random
numbers s, x_{1}, x_{2},
u, v
blinded user
identifier (coin element) A = M^s =
(I*g_{2})^s
additional coin
element B =
g_{1}^x_{1}*g_{2}^x_{2}*
h_{o}^(e*s)* h_{c}
signed blinded
user identifier z' = z^s = A^x
blinded pseudo
public key a' = a^u*g^v
blinded pseudo
signed user identifier b' = b^(s*u)*A^v
equivalent
blinded intercept w' = u*w + v mod q
blinded challenge
(hash value) c' = H(A, B, z', a', b')
challenge
returned to bank c = c'/u mod q
usercalculated
transformed response r' = v + r*u = w' + c'*x mod
q
coin
definition {A, B, (z',a',b',r')}, where
a'* h^c' = g^r' mod
p
b'*z'^c' = A^r'
mod p
c' =
H(A,B,z',a',b')
challenge from
shop to user d = H_{o}(A, B, SHOPID, DATE
TIME)
user's challenge
to observer d^{o}= s*(d+e) mod q
response from
observer r_{1}^{o} =
d^{o}*o_{1} +
o_{2} mod q
user verfication
of observer response g_{1}^r_{1}^{o} =
h_{o}^d^{o}*h_{c} mod p
user response to
shop challenge r_{1} = r_{1}^{o} +
d*(u_{1}*s) + x_{1} mod q
r_{2} = d*s +
x_{2} mod q
shop
verification A^d*B =
g_{1}^r_{1}*g_{2}^r_{2}
mod p
The user U then computes the the challenge c' as follows:
[24O] c' = H(A, B, z', a', b')
and then sends the blinded challenge c back to the bank banque:
[25O] c = c'/u mod q .
Step 4: The bank sends the response r :
[26O] r = w + c*x mod q
and debits U's account in the amount equal to the value of one coin.
Step 5: U accepts the debit only if
[27O] g^r = a*h^c mod p[28O] (I*g_{2})^r = b*z^c mod p .
The user U also calculates r':
[29O] r' = v + r*u mod q .
The coin is the set of numbers {A, B, (z',a',b',r')}, as before.
2. Payment Protocol with Observer.
When the user U is ready to spend the coin, the following protocol is enacted between the user and the shop S.
Step 1: The user sends {A, B, (z',a',b',r')} to S.Note that equation [33O] follows from
Step 2: The shop returns the challenge d:
[30O] d = H_{o}(A, B, SHOPID, DATETIME) .Step 3: This step is new. The user U calculates the response
[30AO] d^{o} = s*(d+e) mod q
and sends d^{o} to the observer O. The observer calculates its response
[30BO] r_{1}^{o} = d^{o}*o_{1} + o_{2} mod q ,
returns o_{2} to the user U, and erases o_{2} from memory. Note this is the point where the observer prevents doublespending. For if o_{2} has already been erased, the observer locks up, and the transaction is not allowed to take place.
The observer here is in effect performing the Schnorr identification protocol, by proving its knowledge of the representation (o_{1}, o_{2}).
Step 4: The user U first verifies the response from the observer O:
The user U then calculates the responses r_{1}, r_{2} for the shop S:[30CO] g_{1}^r_{1}^{o} = h_{o}^d^{o}* h_{c} mod p .
[31O] r_{1} = r_{1}^{o} + d*(u_{1}*s) + x_{1} mod q
[32O] r_{2} = d*s + x_{2} mod q
Step 5: The shop S accepts the coin only if (using c' calculated from the publicly known hash function):
[33O] A^d*B = g_{1}^r_{1}*g_{2}^r_{2} mod p
[34O] g^r' = a'*h^c' mod p
[35O] A^r' = b'*z'^c' mod p .
A^d*B = (I*g_{2})^(s*d)*[g_{1}^x _{1}*g_{2}^x_{2}*h_{o}^(e*s)* h_{c}] mod p
= g_{1}^[(o_{1}+u_{1})*s*d+ x_{1}+ o_{1}*e*s+ o_{2}]*g_{2}^(s*d+x_{2}) mod p
= g_{1}^[s*(d+e)*o_{1}+ o_{2} + d*u_{1}*s + x_{1}]*g_{2}^(s*d+x_{2}) mod p
= g_{1}^r_{1}*g_{2}^r_{2} mod p .
The user U does not know a representation of his identifying information I (because he doesn't know o_{1}), hence he does not know A by himself. Hence the user can't spend the coin without the help of the observer O.
However, if the tamperresistance is broken, and the user spends the coin without the help of the observer, the user can be identified, as we see next.
3. Deposit Protocol with Observer.
As before, when the shop S is ready to deposit the coin at the bank banque, the shop sends the payment transcript consisting of the coin {A, B, (z',a',b',r')}, along with (r_{1}, r_{2}) and the DATETIME of the transaction. The bank already knows the SHOPID, which is used in the communication. The steps below are exactly as those seen previously.
Step 1: The bank verifies equations [33O] to [35O] to see that this is a valid coin.
Step 2: If the coin is valid, the bank checks its database to see if the coin was spent previously (that is, the bank checks for doublespending).
a. If the coin is not in the database, then it was not previously spent. Hence the bank credits the account of S, and records the coin in the form
{A, B, DATETIME, r_{1}, r_{2}}.
b. If the coin is already in the database, then a fraud has occurred. If S previously deposited the coin, and the DATETIME are the same, then S is trying to deposit the same coin or transcript twice. The deposit is rejected for that reason. The bank knows the identity of the shop S responsible and can take steps to ascertain whether this is error or fraud.
c. Otherwise, the coin has been doublespent, and the bank takes steps to unmask the doublespender. The bank will have two sets of information regarding the coin:
{A, B, DATETIME, r_{1}, r_{2}}.Hence, the shop can calculate
{A, B, DATETIME', r'_{1}, r'_{2}}.
(r_{1}  r'_{1}) / (r_{2}  r'_{2}) = [d*s*(o_{1}+u_{1})  d'*s*(o_{1}+u_{1})] / [d*s  d's]
= o_{1}+ u_{1} .
Thus the bank can check its database for the user identity (see equation [15O])
I = g_{1}^(o_{1}+u_{1} ) mod p.
In addition, the bank, which already knew o_{1}, now knows u_{1} also, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of
u_{1} = log_g_{1} (I)  o_{1} mod pserves as proof of the doublespending.
E. Internet Cash Using a Counter
To this point we have a digital cash system that uses a restrictive blind signature. The latter prevents the bank from tracing a coin after signing it, because the user transforms the withdrawn coin into a blinded version that has a valid signature of the bank. But if the coin is doublespent the blinding is stripped away, and the secret key (and hence the identity) of the user who doublespent is revealed. The latter is accomplished using the "two points determine a line" principlethe slope of the line being the user's secret key. We have also added an observer into the system, which prevents doublespending at its source (provided the tamperresistance isn't broken), making the system more efficient, because resources do not have to be wasted tracking down counterfeiters.
The use of Schnorr authentication (a Schnorr signature, in fact, as the challenge is generated from a hash function) between the bank and the user at withdrawal means the user does not have to trust the bank to provide a valid signature on the coin. The use of Schnorr authentication between the user and the merchant means that the coin can be spent with a merchant off line, because doublespenders can be traced after the fact. Schnorr authentication also takes place between the user and the observer to prevent doublespending before it occurs, and to assure the user the observer isn't secretly leaking identifying information.
But all coins in the system are of the same size. This would not be practical if the system were used for the small payments (micropayments) for information that are often contemplated for the Internet, such as pennies for several kilobytes of information from a research journal. Pennysized coins would make the total number of coins much too large. So in this section we add a counter, which is a running (changeable) balance maintained in EEPROM by the observer in a smart card or a PC (PCMCIA) card. Withdrawals from the bank increase the counter balance, while payments to merchants decrease the balance.
This requires some system modifications. When a payment is made to a merchant, the observer will provide a digital signature on the payment amount. This will ensure that the counter has been decreased by the same amount as the payment to the merchant. (The observer will also verify that the amount of the payment is not greater than the existing balance on the counter.) An observer secret key that is used to sign the payment amount will be unique to the observer. Such a unique secret key in each observer is necessary because otherwise, if one observer were cracked and the secret key extracted, the entire system would be compromised.
The observer will also provide the merchant the observer's public key so that it can verify the observer's signature on the amount. This, however, creates a practical problem. How does the merchant know that the public key sent to it is a valid public key of the observer, and not one substituted by the user who has signed an invalid payment amount? The merchant could keep a large database of all valid observer public keys for comparison, but this would not be practical. A more realistic solution is to have the user also submit a certificate at payment time, where a certificate is the bank's signature on the observer's public key.
However, this alone is not sufficient for the bank's security. If the user were to break the tamperresistance of the observer, the user could then forge a signature on payment amounts of arbitrary size, using the secret key embedded in the observer. (Meanwhile, the user could continue to supply certificates showing the bank's signature on the public key corresponding to this secret key.) So a further refinement, to limit the amount of damage to the bank (or digital cash supplier) in the event of observer failure or tampering, is to have each payment amount signed with a separate secret key of the observer, each of which is accompanied by a public key which has been certified by the bank. That means that a set of such key pairs will have to be periodically downloaded from the bank into the observer. (Only the secret keys need be stored in the observer. The public keys and certificates could be stored elsewhere in the user's computer.) Thus if the observer were cracked, the attacker thief would have to keep withdrawing new certified keys from the bank in order to keep spending. This should limit the amount of damage before the doublespender is identified, and also limit the incentive to invest resources in order to compromise observers.
The use of payment certificates requires a certificateissuing protocol. These payment certificates can be thought of as individual checks in an electronic checkbook. Each check (certificate) can only be used once, and the amount of the certificate is filled in at payment time. Once all the blank checks have been used, more must be downloaded from the bank. (This contrasts with the previous protocol, in which the user would download a set of coins of predetermined size. Because the coin size was fixed, we did not have to worry about filling in the amount.)
The details of this certificateissuing protocol will be highlighted in the description of the modified system that follows.
1. Opening an Internet Account.
To open an account, the user (user's computer) U generates a random number u_{1} from Z(q)*, and computes the following number (a user identifier public key) which is sent to the bank
h_{u} = g_{1}^u_{1} mod p .The user keeps u_{1} secret, perhaps even keeping part of u_{1} in the form of a password that must be typed into the computer as needed.
The bank banque verifies the identity of the user in some fashion. The bank generates for U a secret random number o_{1} from Z(q)*, and stores this along with the user information in an account database. The account database contains a balance variable representing the amount of money the user has with the bank.
The bank provides U with an observer (O), which has embedded within ROM the secret key o_{1}, the generator g_{1}, a description of G(q) (namely, p and q), computer code to enact the protocols below, and a variable called balance representing the amount of money withdrawn from the bank. The user U does not know what o_{1} is. The bank computes the observer identifier public key h_{o} = g_{1}^o_{1} and the joint user/observer identifier public key I,
[15I] I = h_{u}* h_{o} = g_{1}^(o_{1} + u_{1}) mod p,
and stores these in the account database. The bank also computes a signature z on user identification information using its secret key x:
[16I] z = (I*g_{2})^x mod p,and makes h_{o} and z known to the user. The variables h_{o}, I, and z are stored in the user's software along with h_{u} and u_{1}.
Because the user U does not know o_{1}, he cannot compute for himeself signatures with respect to the joint public key I. This will prevent him from doublespending certified keys issued by the bank banque. The user's secret key u_{1}, meanwhile, prevents framing attempts by the bank. The bank can't falsely accuse the user of doublespending, because the bank can't demonstrate knowledge of u_{1}. The bank can only learn u_{1} if the user (by breaking the observer) doublespends the same certified keys.
In addition to the key o_{1}, the generator g_{1}, the primes p and q, and the balance variable, the observer will need the following items:
These stored variables will be used by the observer O in the protocols that follow.
2. Internet Withdrawal Protocol.
Because we are now using a digital cash counter, we have to keep track of the circumstances under which the counter balance can be changed. Assuming that the bank does not extend credit in connection with digital cash, the first requirement will be that any amount paid via a digitallysigned check must not be greater than the available counter balance. Payments made will reduce the counter balance, while withdrawals from the bank will increase it.
The following withdrawal protocol is performed between the observer and the bank, intermediated by the user's software. The user identifies himself to the bank using the joint key I of the user and observer, and requests to withdraw an amount. Then
Step 1: The bank banque decreases the account balance of the user U by the amount the user withdraws. Using the notation ":=" to mean "replaced by", and balance' to denote the user's balance at the bank:
balance' := balance'  amountStep 2: This information is passed to the observer O via the user. The observer first verifies that
seq := seq + 1
v := f(key, sequence, amount) .
v := f(key, sequence, amount) .If so, then the observer adjusts the balance in the counter:
balance := balance + amount
seq := seq + 1.
This transfer is very simple, because we have only adjusted a total, without specifying anything about how this total will be spent.
The use of a sequence number is intended to prevent replay attacks. If the user replays the same bank instructions to the observer, in an attempt to increase the balance without another withdrawal, the replay attack will fail because the sequence number has changed. The observer created verification v will not match the one sent by the bank.
3. Key Certificate Issuing Protocol.
To make payment to a shop S (merchant, service provider), the user U must provide a signature on the intended payment amount, along with a key certificate from the bank banque certifying the public key corresponding to the signature. Various schemes are possible, but for explicitness, we will assume that each key certificate is good for a payment amount up to a prepaid maximum, and in any case is only good for an amount that does not exceed the available balance.
First, in the offline preprocessing stage, these two steps take place:
A certificate is then withdrawn by the following online protocol between the bank banque and the user U.Step 1: The observer O generates a random number o_{2} from Z(q)*. The observer calculates the corresponding public key h_{c} = g_{1}^o_{2} and transfers this to the user (i.e. the user's hardware or software).
Step 2: The user U generates five random numbers s, x_{1}, x_{2}, u, and v from Z(q)*. These are used to calculate
[19I] A = (I*g_{2})^s mod p
[20I] B = g_{1}^x_{1}*g_{2}^x_{2}*h_{c }^s mod p
[21I] z' = z^s mod p
[22I] a' = h^u*g^v mod p
[23I] b' = z'^u*A^v mod pAs before, z' is a signature on A. That is, z' = A^x. The user (user's computer) stores A, B, and s, x_{1}, x_{2} for later use in the payment protocol. The variables a', b', and u, v are stored temporarily.
Step 1: The bank generates a random number w from Z(q)*, and sends the pseudopublic key a and the pseudosigned identifier b to the user U:and stores r'. The numbers a', b', and u, v can now be erased, as they are no longer needed.
[17I] a = g^w mod p
[18I] b = (I*g_{2})^w mod p .
Step 2: The user U then computes the challenge c'
[24I] c' = H(A, B, z', a*a', b^s*b'),
stores c', and then sends the blinded challenge c back to the bank banque:
[25I] c = c' + u mod q .
Step 3: The bank sends the response r :
[26I] r = w + c*x mod q
and debits U's account in the amount equal to the value of one coin.
Step 4: U, either while online or offline, accepts the debit only if
The user U also calculates r':[27I] g^r = a*h^c mod p
[28I] (I*g_{2})^r = b*z^c mod p .
[29I] r' = r + v mod q .
The pair (A,B) can be considered the public key of the user with respect to a subsequent payment. The triple (z',c',r') is the bank's certificate on this key. Note the calculation of c' includes a, b, as well as A, B; z' bears the bank's signature x directly; and r' is calculated from the bank's reponse to the challenge c.
primes p, q where q divides p1
generators g, g_{1}, g_{2} of G(q) in
Z(p)*
secret key of
observer o_{1}
secret identifier
key of user u_{1}
identifier public
key of observer h_{o} = g_{1}^o_{1}
mod p
identifier public
key of user h_{u} = g_{1}^u_{1} mod
p
joint user
identifier (joint public key) I = h_{o}* h_{u} =
g_{1}^(o_{1} + u_{1}) mod p
equivalent
identifier signed by bank M = I*g_{2}
amount of
observerstored digital cash balance
symmetric key
shared between bank & observer key
observer
sequence number seq
observer one
way function f(.)
bank's private
key x
bank's random
number w
observercreated
random number o_{2}
observer public
key in certificiate withdrawal h_{c} =
g_{1}^o_{2} mod p
bank's public
key h = g^x
mod p
bank's pseudo
public key a
= g^w mod p
banksigned user
identifier z
= M^x mod p
bankpseudo
signed user identifier b = M^w mod p
collisionfree
hash function H
challenge to
bank c
response to
challenge r
= w + c*x mod q
verification that
signature x is on g (g^x=h) and M (M^x=z) a*h^c = g^r
b*z^c = M^r =
(I*g_{2})^rusergenerated random
numbers s, x_{1}, x_{2}, u,
v
blinded
certificate element A = M^s = (I*g_{2})^s
additional
certificate element B =
g_{1}^x_{1}*g_{2}^x_{2}*h_{c
}^s
certificate public
key of user (A,B)
signed blinded
user identifier z' = z^s = A^x
temporary
variable a' = h^u*g^v
second temporary
variable b' = z'^u*A^v
blinded challenge
(hash value) c' = H(A, B, z', a*a', b^s*b')
challenge sent to
bank c = c' + u mod q
usercalculated
transformed response r' = r + v mod q
bank
certificate on public key of user (z',c',r') on (A,B) such that
c' = H(A, B, z',
g^r'*h^(c'), A^r'*z'^(c'))
payment
specification spec =
(AMOUNT, SHOPID, DATETIME)
equivalent
challenge from user to observer d = H_{o}(A, B, spec)
response from
observer r_{1}^{o} = d*o_{1} +
o_{2} mod q
user verfication
of observer response g_{1}^r_{1}^{o} =
h_{o}^d*h_{c} mod p
equivalent user
response to shop r_{1} = s*(r_{1}^{o} +
d*u_{1}) + x_{1} mod q
r_{2} = d*s +
x_{2} mod q
shop
verifications A^d*B =
g_{1}^r_{1}*g_{2}^r_{2}
mod p
c' = H(A, B, z',
g^r'*h^(c'), A^r'*z'^(c'))
deposited
payment transcript {(A,B), (z', c', r'), (r_{1}, r_{2}),
spec}
4. Internet Payment Protocol.
When the user U is ready to spend an amount AMOUNT at a shop S, the user first performs the following preprocessing offline.
Step 1: The user decides on the amount AMOUNT to be transferred. This is concatenated into a spec vector,The actual payment will be done online between the user and the shop S:
spec = (AMOUNT, SHOPID, DATE TIME).
The user U then sends A, B, spec to the observer O.
Step 2: The observer O verifies that o_{2} is still in memory and that AMOUNT<=balance. O then computes
The observer erases o_{2} from memory and returns r_{1} to the user U.[30I] d = H_{o}(A, B, spec)
[30BI] r_{1}^{o} = d*o_{1} + o_{2} mod q
balance := balance  AMOUNT.
Step 3: The user U also computes
d = H_{o}(A, B, spec)
and verifies that
[30CI] g_{1}^r_{1}^{o} = h_{o}^d*h_{c} mod p .The user U then calculates the responses r_{1}, r_{2} to be used vis àvis the shop S:
[31I] r_{1} = s*(r_{1}^{o} + d*u_{1}) + x_{1} mod q
[32I] r_{2} = d*s + x_{2} mod q
Step 1: The user U sends {(A, B), (z', c', r'), (r_{1}, r_{2}), spec} to S.Note that equation [33I] follows from
Step 2: The shop S accepts the coin only if:
[33I] A^d*B = g_{1}^r_{1}*g_{2}^r_{2} mod p , and
c' = H(A, B, z', g^r'*h^(c'), A^r'*z'^(c')) .
A^d*B = (I*g_{2})^(s*d)*[g_{1}^x _{1}*g_{2}^x_{2}* h_{c}^s] mod p
= g_{1}^[(o_{1}+u_{1})*s*d+ x_{1}+ o_{2}*s]*g_{2}^(s*d+x_{2}) mod p
= g_{1}^[s*((d*o_{1}+ o_{2}) + d*u_{1}) + x_{1} ]*g_{2}^(s*d+x_{2}) mod p
= g_{1}^r_{1}*g_{2}^r_{2} mod p .
The last two inputs to the hash function H correspond to a*a' and b^s*b', as can be seen from the following identities:
a*a' = g^w*h^u*g^v= g^(w+u*x+v)
= g^(w+c*x+v)*g^(u*xc*x)
= g^r'*h^(uc)
= g^r'*h^(c'),b^s*b' = (I*g_{2})^(w*s)*z'^u*A^v
= A^w*A^(x*u)*A^v
= A^(w+x*u+v)
= A^(r'c*x+u*x)
= A^r'*z'^(uc)
= A^r'*z'^(c').
5. Internet Deposit Protocol.
When the shop S is ready to deposit the payment transcript at the bank ( (preferably when network traffic is low), the shop sends it the transcript {(A,B), (z',c',r'), (r_{1},r_{2}), spec}.
Step 1: The bank checks its database to see if the transcript (A,B) was stored previously.
a. If not, the bank calculates d = H_{o}(A, B, spec), and verifies equation [33I] and the calculation of c'. If these are verified, the bank stores {A, B, r_{1}, r_{2}, spec} in the bank's deposit database, and credits AMOUNT to the shop's account.
b. If the coin is already in the database, then a fraud has occurred. If the spec of the information already stored is identical to that of the new payment transcript, then S is trying to deposit the same coin or transcript twice. The deposit is rejected for that reason. The bank knows the identity of the shop S responsible and can take steps to ascertain whether this is error or fraud.
c. Otherwise, the coin has been doublespent, and the bank takes steps to unmask the doublespender. To this end, the bank will have two sets of information regarding the coin:
{A, B, r_{1}, r_{2}, spec}.
{A, B, r'_{1}, r'_{2}, spec}.
Hence, the shop can calculate
(r_{1}  r'_{1}) / (r_{2}  r'_{2}) = [s*d*( o_{1}+u_{1})  s*d'*( o_{1}+u_{1}) ] / [d*s  d's]
= o_{1}+ u_{1} .
The bank can check its database for the user identity, or joint public key (see equation [15I]),
I = g_{1}^(o_{1}+u_{1} ) mod p.
In addition, the bank now knows u_{1} also, since it knows o_{1}, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of
u_{1} = log_g_{1} (I)  o_{1} mod p
serves as proof of the doublespending.
Copyright 1997 J. Orlin Grabbe, 1475 Terminal Way, Suite E, Reno, NV 89502