From daw@cs.berkeley.edu Fri Aug  9 20:24:00 PDT 1996
Article: 860 of isaac.lists.coderpunks
Path: news.isaac.cs.berkeley.edu!not-for-mail
From: daw@cs.berkeley.edu (David Wagner)
Newsgroups: isaac.lists.coderpunks
Subject: Payer-anonymous micropayments
Date: 29 Jul 1996 00:41:01 -0700
Organization: ISAAC Group, UC Berkeley
Lines: 104
Sender: daemon@abraham.cs.berkeley.edu
Approved: mail2news@news.isaac.cs.berkeley.edu
Distribution: isaac
Message-ID: <4thme3$kh7@joseph.cs.berkeley.edu>
NNTP-Posting-Host: abraham.cs.berkeley.edu
Precedence: bulk

I thought I'd share my thoughts on a subject I had pondered about a while ago:
how to build a cryptographically strong anonymous digital micropayment system.

There has recently been a lot of interest in micropayment protocols.  Still,
all the proposed micropayment methods that I know of do not provide
cryptographic protection of your identity.  The obvious approach -- simply
using Chaumian digital cash (i.e. Digicash's ecash) -- provides those
guarantees, but it requires a public-key operation for every micropayment, so
it is perhaps a bit too heavyweight for true micropayment applications.

I think it is important to consider privacy concerns even in micropayment
applications.  If Bob Dole's videotape renting record (or a list of Al Gore's
purchases on the Information Superhighway, or Chelsea Clinton's GIF downloads
>from  the net) were ever leaked to the public, I'd predict an outcry.

One popular micropayment technique uses chained one-way hashes to reduce the
public-key operations required.  Recall that the idea is to repeatedly apply a
one-way function f to produce a stick of coins
	N, f^{100}(N), sig_B(C, f^{100}(N)).
Here f^i(N) denotes i repeated applications of f to N, i.e.
	f^{i+1}(x) = f^i(f(x))		f^0(x) = x,
and sig(x) denotes a public-key signature on x.  The customer C buys a stick of
coins from a trusted third party broker B, who provides the signature on
f^{100}(N):
	C->B: C, f^{100}(N)
	B->C: sig_B(C, f^{100}(N))
Before spending at a shop S, the customer commits
	C->S: f^{100}(N), sig_B(C, f^{100}(N));
the shop verifies the broker's signature offline.  To spend the first coin on
the stick, the customer provides a pre-image of f
	C->S: f^{99}(N)
and the shop verifies that the received bitstring is indeed a pre-image of
f^{100}(N) under f.  Similarly, the i-th coin of the stick is spent by sending
f^{100-i}(N).  Later during off-peak hours, the shop can provide the broker
with the signature on the stick of coins as well as all the coins spent at the
shop, and the broker will pay the shop back.

Several folks have proposed schemes based on this basic idea of coin sticks;
if the abbreviated explanation above was confusing, see Rivest and Shamir's
paper ( http://theory.lcs.mit.edu/~rivest/RivestShamir-mpay.ps ).

To stop double-spending, the client's identity is included in the signature on
the stick, and brokers are likely to require real-world proof of identification
(such as a credit card or driver's license); brokers can identify and blacklist
(or prosecute) double-spenders through this technique.  This is likely to
deter most double-spending.  Of course some double-spending may occur, but the
assumption is that so little money is at stake in micropayment schemes that
this should not be a serious concern to most businesses in real life.

Note that this protocol can be easily blinded with Chaumian techniques: remove
the client's identity from the signature and use a blind signature protocol in
the withdrawal phase.  For instance, with RSA the withdrawal protocol becomes
	C->B: C, b^e f^{100}(N) mod n
	B->C: ( b^e f^{100}(N) )^d mod n
where (e,n) is the broker's public key, d is the corresponding private key, and
b is the blinding factor.  Note that C obtains the signature on f^{100}(N) as
	sig_B(f^{100}(N))
		= ( f^{100}(N) )^d mod n
		= b^{-1} ( b^e f^{100}(N) )^d mod n.
The commitment and payment phases of the protocol above can remain unchanged.
Multiple purchases at the same shop with the same stick can be linked together,
but this doesn't seem to be a huge problem in practice.

The blinding does cause some problems with double-spending; still, they are not
too hard to fix.  Shops can simply verify stick commitments online with the
broker, as is done in online Chaumian ecash protocols.  This doesn't seem to be
too terrible a requirement; subsequent verification of each of the 100 coins in
the stick requires just a hash calculation for each coin.

The largest remaining obstacle is how to deal with partially-spent sticks.
With the unblinded coin stick protocols, customers can simply spend the rest of
a partially-spent stick at another shops or redeem it at their broker.
However, in the blinded protocol, spending coins from the same stick at two
different places allows those two purchase locations to be linked, so the
traditional approach doesn't work.  Still, this obstacle can be surmounted.

One possibility is for brokers to buy back partially-spent sticks with
payee-anonymous digital coins (even if those coins were merely a local scrip
that could be redeemed only for new full sticks from the same broker).  Again,
shops could also give change (via a payee-anonymous method, of course).  Chaum
has described how to do payee-anonymous digital cash for change-making.

Another possibility is for brokers to redeem partially-spent sticks immediately
for a shorter full stick; for instance, if I have 87 unspent coins remaining in
my 100 coin stick, I could anonymously redeem it at my broker (using the above
blinded protocol) for a new full 87-coin stick.  (However, don't fall into the
trap of suggesting that I redeem a 60-unspent-coin stick and a 50-unspent-coin
stick for a new full 110-coin stick: that makes the shop purchases on the first
two sticks linkable.)

So I think the difficulties that payee-anonymity introduces in the above
blinded micropayment scheme can be patched up without too many contortions.
It's true-- in the final analysis, there *are* still some costs associated
with providing payer-anonymity-- but I think they are fairly minor.

One practical advantage of this micropayment scheme is that it could be
deployed quickly with some fairly small modifications to Digicash's ecash
system.  Best of all, we get cryptographic guarantees of payer-anonymity.

Any comments?


P.S.  Some of these ideas arose from conversations with Ian Goldberg-- thanks
to him for all the enlightening discussions!