Anonymous cash without blind signatures

Anonymous (nobody@replay.com)
Wed, 3 Feb 1999 20:24:04 +0100

• Next message: lcs Mixmaster Remailer: "Re: Chaffing and Winnowing"
• Previous message: Jim Gillogly: "Re: Chaffing and Winnowing"

Here's an idea for an anonymous digital cash scheme, very inefficient,
but perhaps avoiding the patent minefield. In particular, blind digital
signatures are not used.

The simplest form of "cash" (non-anonymous) is for the bank to issue
random numbers which represent cash. It makes a list of each number
that it issues. When a piece of cash is deposited, the bank checks its
list to see if the cash matches an item on the list. If so, the cash
is accepted, and it is erased from the list.

Here's a simple way to convert this into a scheme with limited anonymity.
Imagine that multiple customers are withdrawing cash all at once, in a
big batch. The bank creates a batch of random numbers and adds them to
the list. Then they are distributed to the customers, but it is done in
such a way that the bank can't tell who ends up with which number.

Then, when the money is deposited, the bank knows which batch it came
from, but it doesn't know which specific person in the batch has spent
it. If the batches are large enough, you have good anonymity. Obviously
there is a tradeoff between anonymity (large batches) and convenience of
withdrawals (more frequent batches).

The random distribution can be done via a mix, where each person presents
a public key and the bank encrypts each number with one of the keys,
broadcasting the results. There are some other methods, too, such as
multi-party ANDOS.

But that's not the one I wanted to talk about. Here is the method which
is slow but would provide full anonymity.

Going back to the initial scheme with random numbers per customer,
suppose that, instead of a list of valid numbers, the bank makes sure
that each random number it issues satisfies a secret formula. No one
but the bank knows the formula. When cash is presented for deposit,
the bank checks that the cash satisfies the formula, and if so, it
accepts it and adds it to a spent-coin list to prevent double spending.

This is something like a digital signature scheme, except that only
the "signer" (the bank) can verify signatures. It is not as powerful
as a regular signature in that there is no "public key" which the bank
distributes to let other people verify the signature.

As a simple example, the public coins can be 3DES encrypted values using
a key the bank knows. The encrypted values would have some redundancy
in them. When a coin is deposited, the bank decrypts it with its key
and determines whether the plaintext has the proper redundant form.

As presented, this is not anonymous. To make it so, the bank must be
able to issue coins of the proper form without recognizing them later.
This can be done very easily, albeit slowly, using private multi-party
computation (MPC). In this protocol, several parties each have a private
input, and jointly compute a function on their inputs, without any party
learning any other's input.

In this case, the withdrawer provides the plaintext, a random value with
the proper redundancy, and the bank provides the key. They engage in a
MPC protocol to compute the encryption of the plaintext with the key.
The result is the cash, which should be revealed only to the withdrawer.

The main drawback here is that MPC protocols are extremely slow. There
are various special cases in the literature, but they would not work on
a complex algorithm like 3DES. For this the general purpose protocols
would have to be used, which would probably take hours to generate a
single piece of cash.

This raises the question of whether something less powerful than 3DES
would be good enough. Imagine using a simple boolean circuit to identify
valid cash, applying a formula composed of XOR, AND, OR, NOT gates a few
layers deep, with a specified output value. The formula would be secret,
although its general nature (depth, approximate number and types of gates)
would be known.

Attackers have many valid pieces of cash to try to deduce the formula,
and they also have an oracle in the form of the bank's deposit server
by which they can try putting in forged pieces of cash. Can as simple
a formula as this serve to thwart guessers?

And given such a formula, how can the bank create cash which will satisfy
it? There needs to be a sort of trapdoor, or at least some aspect of the
formula which lets the bank create coins at will.

If a simple formula satisfying these requirements could be devised, this
might become a practical method for issuing anonymous digital cash,
without running afoul of the many patents in this field.

(Recall that there was an earlier proposal for using zero knowledge
proofs to implement a fully anonymous digital cash system without blind
signatures. These examples should put to rest any belief that anonymous
digital cash necessarily requires blind signatures. At this time,
however, the alternative anonymous digital cash proposals are probably
not efficient enough to be practical.)

• Next message: lcs Mixmaster Remailer: "Re: Chaffing and Winnowing"
• Previous message: Jim Gillogly: "Re: Chaffing and Winnowing"