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' off-line digital cash system allows the up-front prevention of double-spending (using an observer), yet maintains complete user privacy provided no double- spending takes place. The revelation of identity under double-spending 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 logarithms--in particular the representation problem. The security of the system depends on the existence of a collision-free 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 collision-free 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 Schnorr-type protocol both at withdrawal of digital cash--where the bank performs a restrictive blind signature--and also in interaction with the merchant, where the customer does a Schnorr proof-of-possession (shows knowledge of a representation) as a challenge-and-response. The system's security hinges on the security of the signature scheme. More than one signature scheme can be implemented.

Brands' off-line cash system is just one instance of a general technique: namely a credential-sharing system in which credentials that are shown only once can be transferred between "organizations", while privacy is guaranteed. For example, an off-line 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 public-private 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 p-1. This means 1 = g^q = g^(p-1) 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 Chaum-Pederson, 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 = pseudo-signed(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 pseudo-public key. Label this a. Thus we have

[3] public key h = g^x,

[4] pseudo-public 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.

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 pseudo-public key a = g^w
the pseudo-signed 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 pseudo-signed with the random number w: the pseudo-signed message b = M^w and the pseudo-public key a = g^w. These additional objects will allow the bank to give a zero-knowledge 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

a*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 generators--g, g₁, g₂--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 collision-free hash functions--H and H_o . Each of H and H_o has as its output a member of the set Z(q)* = {1, 2, ..., q-1}. 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 SHOP-ID and DATE-TIME:

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, SHOP-ID, DATE-TIME) = k', where k' is some member of Z(q)*.

Note that this last relationship, equation [16], is the same as equation [1], where in this case the message M = h_u*g₂ . The representation of z (in terms of g₁, g₂) is {u₁*x, x} because z = (g₁^u₁*g₂)^x = g₁^(u₁*x)*g₂^x. The representation of M is {u₁, 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 pseudo-public key a and the pseudo-signed message b to the user U:

[17] a= g^w mod p
[18] b = (h_u*g₂)^w mod p .

Step 2: The user U generates three random numbers s, x₁ , and x₂ from Z(q)*. These are used to calculate

[19] A = (h_u*g₂)^s mod p
[20] B = g₁^x₁*g₂^x₂ mod p
[21] z' = z^s mod p .

Note that z' is a signature on A. That is, z' = z^s = [(h_u*g₂)^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:

[24] c' = H(A, B, z', a', b')

and then sends the blinded challenge c back to the bank banque:

[25] c = c'/u mod q .

Step 3: The bank banque sends the response r :

[26] r = w + c*x mod q

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

[28] (h_u*g₂)^r = b*z^c mod p .

Note that equations [27] and [28] are the same as [13] and [14], which we verified previously. The user U also calculates r':

[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, SHOP-ID, DATE-TIME) .

Step 3: The user U calculates the responses r₁, r₂:

[31] r₁ = d*(u₁*s) + x₁ mod q
[32] r₂ = d*s + x₂ mod q

Step 4: The shop S accepts the coin only if

[33] A^d*B = g₁^r₁*g₂^r₂ 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

A^d*B = (h_u*g₂)^(s*d)*[g₁ ^x₁*g₂^x₂] mod p

= g₁^(u₁*s*d+ x₁)*g₂^(s*d+x₂) mod p
= g₁^r₁*g₂^r₂ mod p.

g^r' = g^(v+r*u) mod p

= 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₂)^s)^(v+r*u) mod p

= (h_u*g₂)^(s*v+s*(w+c*x)*u) mod p
= [(h_u*g₂)^(s*w*u)]*[( h_u*g₂)^(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₁, r₂) and the DATE-TIME of the transaction. The bank already knows the SHOP-ID, 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 double-spending).

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, DATE-TIME, r₁, r₂}.

b. If the coin is already in the database, then a fraud has occurred. If S previously deposited the coin, and the DATE-TIME 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 double-spent, and the bank takes steps to unmask the double-spender. The bank has two sets of information on the coin:

{A, B, DATE-TIME, r₁, r₂}.
{A, B, DATE-TIME', r'₁, r'₂}.

Hence, the bank can calculate

(r₁ - r'₁) / (r₂ - r'₂) = [d*(u₁*s) - d'*(u₁*s)] / [d*s - d's]
= u₁ mod q.

Thus it can check its database for the user identity (see equation [15])

h_u = g₁^u₁ mod p.

In addition, the bank now knows u₁ also, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of

u₁ = log_g₁ (h_u) mod p

serves as proof of the double-spending.

D. The Digital Cash System with Observer.

To incorporate an observer--for the prior prevention of double-spending--in 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₁ embedded in memory (ROM). In addition, when the user withdraws a coin from the bank, the observer itself creates a second random number o₂ which is stored in non-volatile 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. [15-O] corresponds to [15]).

To open an account, the user U generates a random number u₁ from Z(q)*, and computes the following number (an identifier or public key) which is sent to the bank

h_u = g₁^u₁ mod p .

The bank provides U with an observer (O), which has embedded within ROM a random number o₁ from Z(q)*. The user U does not know what o₁ is. The bank computes the observer public key h_o = g₁^o₁ and issues the user identifier (account number) I,

[15-O] I = h_u* h_o = g₁^(o₁ + u₁) mod p,

[16-O] z = (I*g₂)^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₂, the representation of z (in terms of g₁, g₂) is {(o₁+u₁)*x, x}, while the representation of M is {o₁+u₁, 1}. Neither party knows these representations; the bank doesn't know u₁ and the user doesn't know o₁ .

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₂ from Z(q)*. The observer calculates h_c = g₁^o₂ 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 pseudo-public key a and the pseudo-signed message b to the user U:

[17-O] a = g^w mod p
[18-O] b = (I*g₂)^w mod p .

Step 3: The user U generates four (not just three) random numbers s, x₁, x₂, and e from Z(q)*. These are used to calculate

[19-O] A = (I*g₂)^s mod p
[20- O] B = g₁^x₁*g₂^x₂* h_o^(e*s)* h_c mod p
[21-O] 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

[22-O] a' = a^u*g^v mod p
[23-O] b' = b^(s*u)*A^v mod p

The user U then computes the the challenge c' as follows:

[24-O] c' = H(A, B, z', a', b')

and then sends the blinded challenge c back to the bank banque:

[25-O] c = c'/u mod q .

Step 4: The bank sends the response r :

[26-O] 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

[27-O] g^r = a*h^c mod p

[28-O] (I*g₂)^r = b*z^c mod p .

The user U also calculates r':

[29-O] 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.

Step 2: The shop returns the challenge d:

[30-O] d = H_o(A, B, SHOP-ID, DATE-TIME) .

Step 3: This step is new. The user U calculates the response

[30A-O] d^o = s*(d+e) mod q

and sends d^o to the observer O. The observer calculates its response

[30B-O] r₁^o = d^o*o₁ + o₂ mod q ,

returns o₂ to the user U, and erases o₂ from memory. Note this is the point where the observer prevents double-spending. For if o₂ 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₁, o₂).

Step 4: The user U first verifies the response from the observer O:

[30C-O] g₁^r₁^o = h_o^d^o* h_c mod p .

The user U then calculates the responses r₁, r₂ for the shop S:

[31-O] r₁ = r₁^o + d*(u₁*s) + x₁ mod q
[32-O] r₂ = d*s + x₂ mod q

Step 5: The shop S accepts the coin only if (using c' calculated from the publicly known hash function):

[33-O] A^d*B = g₁^r₁*g₂^r₂ mod p
[34-O] g^r' = a'*h^c' mod p
[35-O] A^r' = b'*z'^c' mod p .

A^d*B = (I*g₂)^(s*d)*[g₁^x ₁*g₂^x₂*h_o^(e*s)* h_c] mod p

= g₁^[(o₁+u₁)*s*d+ x₁+ o₁*e*s+ o₂]*g₂^(s*d+x₂) mod p
= g₁^[s*(d+e)*o₁+ o₂ + d*u₁*s + x₁]*g₂^(s*d+x₂) mod p
= g₁^r₁*g₂^r₂ mod p .

The user U does not know a representation of his identifying information I (because he doesn't know o₁), 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 tamper-resistance 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₁, r₂) and the DATE-TIME of the transaction. The bank already knows the SHOP-ID, which is used in the communication. The steps below are exactly as those seen previously.

Step 1: The bank verifies equations [33-O] to [35-O] 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 double-spending).

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, DATE-TIME, r₁, r₂}.

b. If the coin is already in the database, then a fraud has occurred. If S previously deposited the coin, and the DATE-TIME 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 double-spent, and the bank takes steps to unmask the double-spender. The bank will have two sets of information regarding the coin:

{A, B, DATE-TIME, r₁, r₂}.
{A, B, DATE-TIME', r'₁, r'₂}.

Hence, the shop can calculate

(r₁ - r'₁) / (r₂ - r'₂) = [d*s*(o₁+u₁) - d'*s*(o₁+u₁)] / [d*s - d's]
= o₁+ u₁ .

Thus the bank can check its database for the user identity (see equation [15-O])

I = g₁^(o₁+u₁ ) mod p.

In addition, the bank, which already knew o₁, now knows u₁ also, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of

u₁ = log_g₁ (I) - o₁ mod p

serves as proof of the double-spending.

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 double-spent the blinding is stripped away, and the secret key (and hence the identity) of the user who double-spent is revealed. The latter is accomplished using the "two points determine a line" principle--the slope of the line being the user's secret key. We have also added an observer into the system, which prevents double-spending at its source (provided the tamper-resistance 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 double-spenders can be traced after the fact. Schnorr authentication also takes place between the user and the observer to prevent double-spending 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. Penny-sized 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 tamper-resistance 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 double-spender is identified, and also limit the incentive to invest resources in order to compromise observers.

The use of payment certificates requires a certificate-issuing 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 certificate-issuing 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₁ from Z(q)*, and computes the following number (a user identifier public key) which is sent to the bank

h_u = g₁^u₁ mod p .

The bank banque verifies the identity of the user in some fashion. The bank generates for U a secret random number o₁ 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₁, the generator g₁, 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₁ is. The bank computes the observer identifier public key h_o = g₁^o₁ and the joint user/observer identifier public key I,

[15-I] I = h_u* h_o = g₁^(o₁ + u₁) 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:

[16-I] z = (I*g₂)^x mod p,

Because the user U does not know o₁, he cannot compute for himeself signatures with respect to the joint public key I. This will prevent him from double-spending certified keys issued by the bank banque. The user's secret key u₁, meanwhile, prevents framing attempts by the bank. The bank can't falsely accuse the user of double-spending, because the bank can't demonstrate knowledge of u₁. The bank can only learn u₁ if the user (by breaking the observer) double-spends the same certified keys.

In addition to the key o₁, the generator g₁, 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 digitally-signed 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' - amount
seq := seq + 1
v := f(key, sequence, amount) .

Step 2: This information is passed to the observer O via the user. The observer first verifies that

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 off-line preprocessing stage, these two steps take place:

Step 1: The observer O generates a random number o₂ from Z(q)*. The observer calculates the corresponding public key h_c = g₁^o₂ 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₁, x₂, u, and v from Z(q)*. These are used to calculate

[19-I] A = (I*g₂)^s mod p
[20-I] B = g₁^x₁*g₂^x₂*h_c ^s mod p
[21-I] z' = z^s mod p
[22-I] a' = h^u*g^v mod p
[23-I] b' = z'^u*A^v mod p

As before, z' is a signature on A. That is, z' = A^x. The user (user's computer) stores A, B, and s, x₁, x₂ 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 pseudo-public key a and the pseudo-signed identifier b to the user U:

[17-I] a = g^w mod p
[18-I] b = (I*g₂)^w mod p .

Step 2: The user U then computes the challenge c'

[24-I] c' = H(A, B, z', a*a', b^s*b'),

stores c', and then sends the blinded challenge c back to the bank banque:

[25-I] c = c' + u mod q .

Step 3: The bank sends the response r :

[26-I] 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 on-line or off-line, accepts the debit only if

[27-I] g^r = a*h^c mod p
[28-I] (I*g₂)^r = b*z^c mod p .

The user U also calculates r':

[29-I] 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.

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 pre-processing off-line.

Step 1: The user decides on the amount AMOUNT to be transferred. This is concatenated into a spec vector,

spec = (AMOUNT, SHOP-ID, DATE- TIME).

The user U then sends A, B, spec to the observer O.

Step 2: The observer O verifies that o₂ is still in memory and that AMOUNT<=balance. O then computes

[30-I] d = H_o(A, B, spec)
[30B-I] r₁^o = d*o₁ + o₂ mod q
balance := balance - AMOUNT.

The observer erases o₂ from memory and returns r₁ to the user U.

Step 3: The user U also computes

d = H_o(A, B, spec)

and verifies that

[30C-I] g₁^r₁^o = h_o^d*h_c mod p .

The user U then calculates the responses r₁, r₂ to be used vis- à-vis the shop S:

[31-I] r₁ = s*(r₁^o + d*u₁) + x₁ mod q

[32-I] r₂ = d*s + x₂ mod q

Step 1: The user U sends {(A, B), (z', c', r'), (r₁, r₂), spec} to S.

Step 2: The shop S accepts the coin only if:

[33-I] A^d*B = g₁^r₁*g₂^r₂ mod p , and

c' = H(A, B, z', g^r'*h^(-c'), A^r'*z'^(-c')) .

A^d*B = (I*g₂)^(s*d)*[g₁^x ₁*g₂^x₂* h_c^s] mod p

= g₁^[(o₁+u₁)*s*d+ x₁+ o₂*s]*g₂^(s*d+x₂) mod p
= g₁^[s*((d*o₁+ o₂) + d*u₁) + x₁ ]*g₂^(s*d+x₂) mod p
= g₁^r₁*g₂^r₂ 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*x-c*x)
= g^r'*h^(u-c)
= g^r'*h^(-c'),

b^s*b' = (I*g₂)^(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'^(u-c)
= 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₁,r₂), 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 [33-I] and the calculation of c'. If these are verified, the bank stores {A, B, r₁, r₂, 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 double-spent, and the bank takes steps to unmask the double-spender. To this end, the bank will have two sets of information regarding the coin:

{A, B, r₁, r₂, spec}.
{A, B, r'₁, r'₂, spec}.

Hence, the shop can calculate

(r₁ - r'₁) / (r₂ - r'₂) = [s*d*( o₁+u₁) - s*d'*( o₁+u₁) ] / [d*s - d's]
= o₁+ u₁ .

The bank can check its database for the user identity, or joint public key (see equation [15-I]),

I = g₁^(o₁+u₁ ) mod p.

In addition, the bank now knows u₁ also, since it knows o₁, which it would not otherwise known (without taking discrete logarithms). Hence the bank's knowledge of

u₁ = log_g₁ (I) - o₁ mod p

serves as proof of the double-spending.