Participants are the Bank, the Spender, and the Merchant.

Initialization is done once and for all by some central authority. Choose a large prime $p$ such that $q=(p-1)/2$ is also prime (see Exercise 15 in Chapter 13). Let $g$ be the square of a primitive root mod $p$. This implies that $g^{k_1}\equiv g^{k_2}(\text{m}\text{o}\text{d}p)⟺k_1\equiv k_2(\text{m}\text{o}\text{d}q)$. Two secret random exponents are chosen, and $g_1$ and $g_2$ are defined to be $g$ raised to these exponents mod $p$. These exponents are then discarded (storing them serves no useful purpose, and if a hacker discovers them, then the system is compromised). The numbers

are made public. Also, two public hash functions are chosen. The first, $H$, takes a 5-tuple of integers as input and outputs an integer mod $q$. The second, $H_0$, takes a 4-tuple of integers as input and outputs an integer mod $q$.

The bank chooses its secret identity number $x$ and computes

The number $h$ is made public and identifies the bank.

The Spender chooses a secret identity number $u$ and computes the account number

The number $I$ is sent to the Bank, which stores $I$ along with information identifying the Spender (e.g., name, address). However, the Spender does not send $u$ to the bank. The Bank sends

to the Spender.

The Merchant chooses an identification number $M$ and registers it with the bank.

The Spender contacts the bank, asking for a coin. The bank requires proof of identity, just as when someone is withdrawing classical cash from an account. All coins in the present scheme have the same value. A coin will be represented by a 6-tuple of numbers

This may seem overly complicated, but we’ll see that most of this effort is needed to preserve anonymity and at the same time prevent double spending.

Here is how the numbers are constructed.

1. The Bank chooses a random number $w$ (a different number for each coin), computes

   $$g_w\equiv g^w\text{ and }\beta \equiv (I{g}_2{)}^w(\text{m}\text{o}\text{d}p)\text{,}$$

   and sends $g_w$ and $\beta$ to the Spender.

2. The Spender chooses a secret random 5-tuple of integers

   $$(s\text{,}{x}_1\text{,}{x}_2\text{,}{\alpha }_1\text{,}{\alpha }_2)\text{.}$$

3. The Spender computes

   $$\begin{array}{rc}A\equiv & (I{g}_2{)}^s\text{,}B\equiv g_1^{x_1}{g}_2^{x_2}\text{,}z\equiv {z^{\prime }}^s\text{,}\\ a\equiv & g_w^{{\alpha }_1}{g}^{{\alpha }_2}\text{,}b\equiv {\beta }^{s{\alpha }_1}{A}^{{\alpha }_2}(\text{m}\text{o}\text{d}p)\text{.}\end{array}$$

   Coins with $A=1$ are not allowed. This can happen in only two ways. One is when $s\equiv 0(\text{m}\text{o}\text{d}q)$, so we require $s\cancel{\equiv }0$. The other is when $I{g}_2\equiv 1(\text{m}\text{o}\text{d}p)$, which means the Spender has solved a discrete logarithm problem by a lucky choice of $u$. The prime $p$ should be chosen so large that this has essentially no chance of happening.

4. The Spender computes

   $$c\equiv {\alpha }_1^{-1}H(A\text{,}B\text{,}z\text{,}a\text{,}b)(\text{m}\text{o}\text{d}q)$$

   and sends $c$ to the Bank. Here $H$ is the public hash function mentioned earlier.

5. The Bank computes $c_1\equiv cx+w(\text{m}\text{o}\text{d}q)$ and sends $c_1$ to the Spender.

6. The Spender computes

   $$r\equiv {\alpha }_1{c}_1+{\alpha }_2(\text{m}\text{o}\text{d}q)\text{.}$$

   The coin $(A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r)$ is now complete. The amount of the coin is deducted from the Spender’s bank account.

The procedure, which is quite fast, is repeated each time a Spender wants a coin. A new random number $w$ should be chosen by the Bank for each transaction. Similarly, each spender should choose a new 5-tuple $(s\text{,}{x}_1\text{,}{x}_2\text{,}{\alpha }_1\text{,}{\alpha }_2)$ for each coin.

The Spender gives the coin $(A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r)$ to the Merchant. The following procedure is then performed:

1. The Merchant checks whether

   $$g^r\equiv a{h}^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}{A}^r\equiv z^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}b(\text{m}\text{o}\text{d}p)\text{.}$$

   If this is the case, the Merchant knows that the coin is valid. However, more steps are required to prevent double spending.

2. The Merchant computes

   $$d=H_0(A\text{,}B\text{,}M\text{,}t)\text{,}$$

   where $H_0$ is the hash function chosen in the initialization phase and $t$ is a number representing the date and time of the transaction. The number $t$ is included so that different transactions will have different values of $d$. The Merchant sends $d$ to the Spender.

3. The Spender computes

   $$r_1\equiv dus+x_1\text{,}{r}_2\equiv ds+x_2(\text{m}\text{o}\text{d}q)\text{,}$$

   where $u$ is the Spender’s secret number, and $s\text{,}{x}_1\text{,}{x}_2$ are part of the secret random 5-tuple chosen earlier. The Spender sends $r_1$ and $r_2$ to the Merchant.

4. The Merchant checks whether

   $$g_1^{r_1}{g}_2^{r_2}\equiv A^{d}B(\text{m}\text{o}\text{d}p)\text{.}$$

   If this congruence holds, the Merchant accepts the coin. Otherwise, the Merchant rejects it.

A few days after receiving the coin, the Merchant wants to deposit it in the Bank. The Merchant submits the coin $(A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r)$ plus the triple $(r_1\text{,}{r}_2\text{,}d)$. The Bank performs the following:

1. The Bank checks that the coin $(A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r)$ has not been previously deposited. If it hasn’t been, then the next step is performed. If it has been previously deposited, the Bank skips to the Fraud Control procedures discussed in the next subsection.

2. The Bank checks that

   $$g^r\equiv a{h}^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}{A}^r\equiv z^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}b\text{,}\text{ and }{g}_1^{r_1}{g}_2^{r_2}\equiv A^{d}B(\text{m}\text{o}\text{d}p)\text{.}$$

   If so, the coin is valid and the Merchant’s account is credited.

There are several possible ways for someone to try to cheat. Here is how they are dealt with.

1. The Spender spends the coin twice, once with the Merchant, and once with someone we’ll call the Vendor. The Merchant submits the coin along with the triple $(r_1\text{,}{r}_2\text{,}d)$. The Vendor submits the coin along with the triple $(r_1^{{}^{\prime }}\text{,}{r}_2^{{}^{\prime }}\text{,}{d}^{\prime })$. An easy calculation shows that

   $$r_1-r_1^{{}^{\prime }}\equiv us(d-d^{\prime })\text{,}{r}_2-r_2^{{}^{\prime }}\equiv s(d-d^{\prime })(\text{m}\text{o}\text{d}q)\text{.}$$

   Dividing yields $u\equiv (r_1-r_1^{{}^{\prime }})(r_2-r_2^{{}^{\prime }}{)}^{-1}(\text{m}\text{o}\text{d}q)$. The Bank computes $I\equiv g_1^u(\text{m}\text{o}\text{d}p)$ and identifies the Spender. Since the Bank cannot discover $u$ otherwise, it has proof (at least beyond a reasonable doubt) that double spending has occurred. The Spender is then sent to jail (if the jury believes that the discrete logarithm problem is hard).

2. The Merchant tries submitting the coin twice, once with the legitimate triple $(r_1\text{,}{r}_2\text{,}d)$ and once with a forged triple $(r_1^{{}^{\prime }}\text{,}{r}_2^{{}^{\prime }}\text{,}{d}^{\prime })$. This is essentially impossible for the Merchant to do, since it is very difficult for the Merchant to produce numbers such that

   $$g_1^{r_1^{{}^{\prime }}}{g}_2^{r_2^{{}^{\prime }}}\equiv A^{d^{\prime }}B(\text{m}\text{o}\text{d}p)\text{.}$$

3. Someone tries to make an unauthorized coin. This requires finding numbers such that $g^r\equiv a{h}^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}$ and $A^r\equiv z^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}b$. This is probably hard to do. For example, starting with $A\text{,}B\text{,}z\text{,}a\text{,}b$, then trying to find $r$, requires solving a discrete logarithm problem just to make the first equation work. Note that the Spender is foiled in attempts to produce a second coin using a new 5-tuple since the values of $x$ is known only to the Bank. Therefore, finding the correct value of $r$ is very difficult.

4. Eve L. Dewar, an evil merchant, receives a coin from the Spender and deposits it in the bank, but also tries to spend the coin with the Merchant. Eve gives the coin to the Merchant, who computes $d^{\prime }$, which very likely is not equal to $d$. Eve does not know $u\text{,}{x}_1\text{,}{x}_2\text{,}s$, but she must choose $r_1^{{}^{\prime }}$ and $r_2^{{}^{\prime }}$ such that $g_1^{r_1^{{}^{\prime }}}{g}_2^{r_2^{{}^{\prime }}}\equiv A^{d^{\prime }}B(\text{m}\text{o}\text{d}p)$. This again is a type of discrete logarithm problem. Why can’t Eve simply use the $r_1\text{,}{r}_2$ that she already knows? Since $d^{\prime }\ne d$, the Merchant would find that $g_1^{r_1}{g}_2^{r_2}\cancel{\equiv }{A}^{d^{\prime }}B$.

5. Someone working in the Bank tries to forge a coin. This person has essentially the same information as Eve, plus the identification number $I$. It is possible to make a coin that satisfies $g^r\equiv a{h}^{H(A\text{,}B\text{,}z\text{,}a\text{,}b)}$. However, since the Spender has kept $u$ secret, the person in the bank will not be able to produce a suitable $r_1$. Of course, if $s=0$ were allowed, this would be possible; this is one reason $A=1$ is not allowed.

6. Someone steals the coin from the Spender and tries to spend it. The first verification equation is still satisfied, but the thief does not know $u$ and therefore will not be able to produce $r_1\text{,}{r}_2$ such that $g_1^{r_1}{g}_2^{r_2}\equiv A^{d^{\prime }}B$.

7. Eve L. Dewar, the evil merchant, steals the coin and $(r_1\text{,}{r}_2\text{,}d)$ from the Merchant before they are submitted to the Bank. Unless the bank requires merchants to keep records of the time and date of each transaction, and therefore be able to reproduce the inputs that produced $d$, Eve’s theft will be successful. This, of course, is a flaw of ordinary cash, too.

During the entire transaction with the Merchant, the Spender never needs to provide any identification. This is the same as for purchases made with conventional cash. Also, note that the Bank never sees the values of $A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r$ for the coin until it is deposited by the Merchant. In fact, the Bank provides only the number $w$ and the number $c_1$, and has seen only $c$. However, the coin still contains information that identifies the Spender in the case of double spending. Is it possible for the Merchant or the Bank to extract the Spender’s identity from knowledge of the coin $(A\text{,}B\text{,}z\text{,}a\text{,}b\text{,}r)$ and the triple $(r_1\text{,}{r}_2\text{,}d)$? Since the Bank also knows the identification number $I$, it suffices to consider the case where the Bank is trying to identify the Spender. Since $s\text{,}{x}_1\text{,}{x}_2$ are secret random numbers known only to the Spender, $A$ and $B$ are random numbers. In particular, $A$ is a random power of $g$ and cannot be used to deduce $I$. The number $z$ is simply $A^x(\text{m}\text{o}\text{d}p)$, and so does not provide any help beyond what is known from $A$. Since $a$ and $b$ introduce two new secret random exponents ${\alpha }_1\text{,}{\alpha }_2$, they are again random numbers from the viewpoint of everyone except the Spender.

At this point, there are five numbers, $A\text{,}B\text{,}z\text{,}a\text{,}b$, that look like random powers of $g$ to everyone except the Spender. However, when $c\equiv {\alpha }_1^{-1}H(A\text{,}B\text{,}z\text{,}a\text{,}b)(\text{m}\text{o}\text{d}q)$ is sent to the Bank, the Bank might try to compute the value of $H$ and thus deduce ${\alpha }_1$. But the Bank has not seen the coin and so cannot compute $H$. The Bank could try to keep a list of all values $c$ it has received, along with values of $H$ for every coin that is deposited, and then try all combinations to find ${\alpha }_1$. But it is easily seen that, in a system with millions of coins, the number of possible values of ${\alpha }_1$ is too large for this to be practical. Therefore, it is unlikely that knowledge of $c$, hence of $b$, will help the Bank identify the Spender.

The numbers ${\alpha }_1$ and ${\alpha }_2$ provide what Brands calls a restricted blind signature for the coin. Namely, using the coin once does not allow identification of the signer (namely, the Spender), but using it twice does (and the Spender is sent to jail, as pointed out previously).

To see the effect of the restricted blind signature, suppose ${\alpha }_1$ is essentially removed from the process by taking ${\alpha }_1=1$. Then the Bank could keep a list of values of $c$, along with the person corresponding to each $c$. When a coin is deposited, the value of $H$ would then be computed and compared with the list. Probably there would be only one person for a given $c$, so the Bank could identify the Spender.