Identity Agnostic Online Cash
Douglas Barnes
Abstract: One of the unique aspects of Chaum's blind signature
scheme for anonymous transactions is that it is practiced entirely by the side
that wants to be anonymous. In a customer-bank relationship, the customer's
software practices the technology, not the bank's. Chaum's patent on blind
signatures cites as prior art a non-anonymous signature scheme that differs
significantly only in steps taken by the "customer" side. An open standard for
electronic cash would then allow a bank or other cash issuer to remain
agnostic with respect to customer's software blinding or not blinding. Since
the bank's software would be practicing technology cited as prior art by
Chaum in his patent, and would have a substantial non-infringing use, I
argue that the bank would not need to license
Chaum's patents, provided the bank itself only provided non-blinding
customer software.
Background
The increasing importance of online commerce has lead to a great flurry of
competing methods for buying and selling goods and services across
networks; in addition there is also increased activity in the area of using
portable computing devices (smart cards) to replace conventional cash for off-
line transactions. An important goal for many researchers has been to
develop ways of making both online and offline transactions behave as much
like traditional cash transactions as possible.
Such electronic cash systems have many important attributes beyond the
scope of this paper, but the academic literature on payment protocols focuses
on the following four dimensions:
- Anonymous vs. Traceable
Does a particular electronic "coin" contain sufficient information to identify
the spender? If electronic payment systems are built on top of traceable
transactions, then it is possible for issuers to build sophisticated databases
about spenders.
- Linkable vs. Unlinkable
Even if a particular coin cannot be traced to a particular spender, can a set of
payments be linked together? If payments are linkable, this makes
identification of the spender by correlation a relatively staightforward process,
and leads to the same kinds of abuses possible with traceable systems.
- Online vs. Offline
When a coin is spent, does the vendor have to communicate with the issuer
to check the validity of a coin, or to prevent double spending? As networks
become more widespread, and as bandwidth availability increases and costs
decrease, the need for pure offline cash correspondingly decreases; it is also
substantially more difficult to implement.
- Software vs. Hardware
Does the system require users to have some sort of tamper-proof black box to
prevent fraud? Hardware requirements of this sort greatly complicate the use
of online electronic cash in general purpose computers; by the same token,
complete control over the hardware leads to greater reliability than is
currently available with general purpose computers.
Blind signature systems easily and intuitively lend themselves to building
anonymous, unlinkable, online, software-based electronic cash. However,
despite the fact that this technology was first published ten years ago, we have
not yet seen a single significant implementation. Partly this is because banks
and other potential issuers are conservative by nature and are somewhat
daunted by the need to develop new policies and controls for a system based
on anonymous electronic cash.
Personal experience and anecdotal evidence suggests that at least some of the
blame rests with David Chaum himself, holder of the root patent on blind
signatures (US Patent 4,759,063) and numerous derivative patents. Although
the patent holder frequently alludes to real implementations of his technology
"real soon now," it is abundantly clear that the cost of licensing, as well as
attendant difficulties of dealing with this particular patent holder provide for
a significant barrier to entry.
Examination of blind signature technology shows a way around this problem
for the cash issuer: by their very fundamental nature, blind signatures are
practiced entirely by customer software. Therefore it is possible for an
electronic cash issuer to develop software with the substantial non-infringing
use of issuing non-blinded electronic cash, which can also accomodate the
practice of a blinding protocol by the customer. When operating software
implementing this protocol, the issuer cannot distinguish on withdrawal
whether the customer is blinding or not blinding, and would have to go to
some lengths to distinguish cash on redemption as having originated from a
blinding operation or not.
Such dual-purpose "agnostic" software can be deployed in preparation for
better licensing terms, the invalidation of the relevant patents, or a
declaration of patent misuse. Also, it can accomodate users in jurisdictions
where the patent is not valid.
In this paper I will compare blind-signature electronic cash systems to an
ordinary signature-based electronic cash systems, and show that the difference
between the two rests solely in the customer software; I will also show that an
issuer can implement exactly the same protocol and bank software for dealing
with both kinds of customer software.
Two Withdrawal Protocols
[All examples in this paper will omit a number of things that are not
strictly relevant to comparing the protocols, such as how the parties
authenticate themselves to each other, how accounts are established with the
cash issuer, how sessions are encrypted against interception by a third party,
how coin denominations are requested, how the bank accounts for issue and
deposit of coins, and how currencies are managed over time.]
Here are the protocols for withdrawing a single electronic coin in both a
simple signature system and a blind-signature system.
Definitions:
h(x) A one-way function
tok A token prior to signing by the bank
coin A digital string redeemable for value via the bank
resp Response from bank
e RSA encryption (public) key for a particular value of coin
d RSA decryption (private) key for a particular value of coin
n RSA prime
Non-Blinding Withdrawal Protocol
Customer Bank
-------- ----
X <- random
tok = h(X)
--- tok --->
resp = tok^d mod n
<--- resp ---
coin = resp
Blinding Withdrawal Protocol
Customer Bank
-------- ----
X <- random
r <- random
tok = h(X) * (r^e mod n)
--- tok --->
resp = tok^d mod n
<--- resp ---
coin = resp/r
From these two examples, we can see that the protocol is identical in both the
blinding and non-blinding cases with respect to the bank's behavior.
For the same value of X, both protocols generate the same coin, although
tok
and resp will have different values. This is because:
(tok*(r^e mod n))^d mod n == (tok^d * r) mod n
One can then divide the right term by r and get tok^d mod n.
A Single Spending Protocol
Regardless of which withdrawal protocol is used, only one spending protocol
is needed. The customer gives the coin to the vendor, who then presents it to
the bank to both check its validity and to deposit it.
Definitions:
X Original random serial number
h(x) A one-way function
coin A digital string redeemable for value via the bank
e RSA encryption (public) key for a particular value of coin
n RSA prime
Spending Protocol
Vendor Bank
------ ----
---- X, coin --->
trial = coin^e mod n
if (trial == h(X)) and
coin not spent, then
put coin in spent coin db,
and send accept
<--- accept -----
else
<--- reject -----
Note that at this point the bank could determine if
the coin was originally issued to a customer who blinded
the value before the bank signed it. However, the bank
would have to store a copy of all signed tokens and
check all submitted coins against this database.
Conclusion
Based on these observations, it is my sincere hope that potential issuers of
electronic cash can concentrate on overcoming the other difficulties of
implementing and deploying electronic cash systems rather than being
thwarted by the barrier to entry posed by the patent holder on blind
signatures.
I do urge anyone thinking of doing this to consult first with a qualified
attorney specializing in intellectual property issues, as I am not an attorney
and this should not be interpreted as legal advice.
|