From: rah@shipwright.com (Robert Hettinga)
Date: Tue, 19 Dec 95 17:08:15 PST
To: dcsb@ai.mit.edu
Subject: King Kong Does e$
Message-ID: <v02120d03acfd0a819ff2@[199.0.65.105]>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

King Kong Does e$

A while back, when the Microsoft Network hype was at its height, I
forwarded a bunch of articles to www-buyinfo entitled "Oh, No, there
goes Tokyo", about how Godzilla, in the form of Microsoft's Microsoft
Network, was going to stomp all over Tokyo, in the form of the net.
This was before I found out that Netscape's codeword for their Navigator
HTML Browser was "Mozilla".

So, along comes the following on the DCSB list, courtesy of the esteemed
Mr. Lethin:

        Wednesday,  December 13, 1995
        Refreshments 4:15 PM 4:30 - 6:00 PM
        Bartos Theater, E15-070 MIT Media Lab
        Ames Street, Cambridge, MA, USA
        Electronic Money Made Easy
        Dan Simon
        (dansimon@microsoft.com)


Mac in hand, I went to a presentation at the Media Lab's basement
auditorium, and proceed to transcribe his copious overheads, sans
graphics, as fast as my fingers could fly...

Which I present here in it's raw form, with a few corrections, his
cryptic (ahem...) source citations, viz: (cf., MN 93), and the
ocassional note I could cram in when he stopped flipping charts...

Oh, no, there goes Zurich...

- --------------------

Dan Simon Microsoft, now,
Quantum Computing/crypto in Canada before...

Characteristics of cash
        Portable
        Anonymous
        Confidential
        Easily and instantly transferrable
        Owned by those posessing it
        Hard to counterfiet
        Has multiple interchangeable forms.

What isn't cash: e-credit
        Non-anonymous
        Severely limited confidentiality
        Complicated payment protocols two parties and both their respective
        banks involved
        Ownership determined by record-keeping credit/debit authority

What isn't e-cash: offline e-cash
        One desirable feature of cash: transfer without an intermediary
        Problem: doublespending: restore prespending state, respend the same
        cash
        Tracing re-spent cash useless if it was stolen (cf. (cfnII 0091, Yac94,
        etc)
        Tamperproof hardware isn't (cf EGY83)
        Can broadcast small amounts over the net at a huge payoff. Result cash
        as secure cellphone codes (better not be worth much...)

Offline Electronic "bills" don't work. Too big for offline
Offline Electronic coins do work. Easy to counterfiet, not much profit.

(He is interested in electronic banknotes, on-line bearer securities, in
other words)

What can we assume:

        Customers, merchants, banks may wish to transact via many different
        possible media: telephone, Internet, cable network,
        smartcard/terminal, etc. etc.

        If a customer wants a transaction to be anonymous, then an anonymous
        medium must be used (no callerid on the telephone, anonymous remailer,
        etc)

A Modest Proposal
        On-line cash issued by banks owned by a possessor,
        Cryptographically hard to counterfiet
        Cash ownership transferred with bank's help
        aAnonymity of payer, payee based on anonymity of communication medium
        No individual account or prior trust relationship necessary to use a
        bank's cash
        (cf., MN 93)

Formal Security
        E-cash schemes generally described as a set of individual protocols
        (payer-payee, payer-bank, etc.( with intuitively described goals)
        But formal proof of security really requires a model of a full network,
        to consider general attacks, and explicit, formal security goals
        Previous examples:
        (BEA91/MR/91) for computation
        (RS93) for anonymity,
        (BR93) for authentication

What does it look like
        A bank issued banknote has a serial number,amount, and treasuer's
        signature
        It also has an associated "secret" which can be checked against the
        serial number, but can't be gotten from the serial number
        Its owner is whoever has the secret...
        ...but when the issuing bank gets the secret, the banknote is no longer
        valid.
        Publish the bank notes as broken, banknotes no longer valid.

(spiffy graphic elided)

        Customer chooses secret s, serial number n, n=h(s) and amount.
        Customer pays bank (by any method) the amount of the desired banknote
        bank signs serial number and amount
        Transaction may be anonymous (physical cash purchase at bank) pick
        serial number, bank uses private signature to sign the serial number.

(May's  train-locker applies)

How is change made:
        Customer generates secrets, serial numbers and amounts for smaller
        banknotes
        Customer gives bank the secret for the large banknote, and serial
        numbers and amounts for smaller ones
        Bank signs serial numbers and amounts, stores the secret for large
        now-invalid banknote
        Transaction can be completely anonymous.

How is it used for payment
        Payer simply gives bank note to payee by handing over the secret
        payee immediately exchanges the banknote for new ones anonymously, if
        desired
        Old banknote is now invalid, since bank has its secret; hence payer
        can't respend it
        If the bank note is already invalid, bank rejcts exchange and informs
        payee.
        "In effect, these are disposable banknotes"

"the simple way to get around exploding banknote numbers, issue it with
an expiry date."

Estimated outstanding certificates numbers would then be within the
storage capacity of a bank. (per a crony in the Bank of Japan)

Public key from the bank is needed to keep the bank honest.

"miracle of one-way function" (shuts down clueless question...)

Model
        Synchronous network of parties, some dishonest, one of them is the
        bank
        Parties can exchange messages anonymously
        Responder can always broadcast
        Parties and bank keep track of balances each round, a party receives
        instruction to deposit/withwdraw/ a unit value coin to/from the bank or
        pay a coin to another party
        (missed one point..)

Security goals
        Correctness: if all parties are honest, then instructions result in
        correct new balances
        Integrity: parties cannot be ripped off
        Honest bank never accepts more coins than have been withdrawn
        Party can detect dishonest bank
        Anonymity: information available to any coalition should be
        indistinquishable for any sequence of instructions consistent with the
        starting and ending points of distinguised coins entering/leaving
        coalition
        Weak anonymity, contends that that's what we have with serial numbered
        physical notes anyway
        Can make stronger with subsequent anonymous change operations at a
        bank...
        (can also buy with cash at a desk, also on the net with another form of
        digital cash ;-)
        Efficiency: cost of security should grow slowly (polylog at worst) with
        size of network.

Convenience Features
        Only payer, payee, issuing bank involved in transaction
        Each validation and transfer immediate
        Portable
        Easy to handle
        Expiry dates can be added.
        If anonymous withdrawl, then can get lost money back on expiry date, if
        coins weren't cashed.

Security
        Digital signature makes cash unforgeable
        Online validation prevents double spending
        Secrecy of secret preserved even if serial number publically available
        Bank's *only* secret is its private signature key
        Digital signature publicly commits bank to redeeming its e-cash; hence
        customers need not have special trust relationship with bank.

Audience Q: Borenstein's scenario.
A: bad problem. someone can split bank private keys, for instance
(No problem, strawman, what happens when someone breaks Ft. Knox?... --RAH ;-)

Extra features
        Payee can have the e-cash non-anonymously deposited in bank account for
        easier handling and better security (bank as back up)
        Payer can include transaction details with payment package or hide them
        in the secret (to create transaction record to be archived by, for
        example, by the bank) helpful in dispute.

"Secure payments" and E-cash
        "Don't send cash in the mail" even if it gets there, receiver need not
        admit it
        One solution: secure payment protocols (Microsoft/Visa STT)
        Non-anonymous: transaction details attached to payment mediated by
        payer's credit card issuer
        Payee can delay response and batch process transactions

"Secure Payments"
        Protocol's basic idea: payer sends encrypted package to payee giving
        credit card number and transaction details, "payment instructions".
        Only acquirer can read it
        Valid credit card number plus payer's digital signature assure
acquirer
        that payment is legitimate
        (missed one point)

Secure ecash payments
        Payer substitutes ecash secrets for credit card number in payment
        instruction package payment desiring ecash settlement.
        Includes ecash serial numbers amounts when sending package to acquirer
        E-cash issuing bank bank checks validity of ecash payment and exchanges
        it for merchant as apprpriate by signing serial numbers, amounts
        Instant payment, no bad debt


Questions
        Where is the communications cost/ security tradeoff?
        Solutions to dine and dash problem with dishonest bank (anonymity must
        broken to nark on the bank) (cf Cle85)?
        Efficient offline anonymous micropayments solutions?
        Implimentation pitfalls?

- -------------------

So, there are my notes, such as they are...

I walked away from this thinking that on-line cash covers a multitude of
sins:

        You can stick any "secret" into digital cash as long as it's unique
        and you trust the bank to keep it.

        If bank signs the secret they've shared with you and reveal it
        before some expiry date, they can be put out of business, because
        they've blown their reputation.

        If they claim that you've not shared a secret, you expose the secret
        and their signature, same happens.

        If you put an expiry date on Simon's digital cash, you don't have
        to keep track of it all.

        If you have an expiry date on Simon's cash, if you loose it, you
        can tell the bank, and if it's not cashed by the expiry date they
        can give you your money back.

        There's a distinction between on-line "banknotes", which are
        valuable enough to forge, and off-line "coins", which are not.

Simon has a system which has just enough anonymity to be economically
useful, but not perfect enough to keep the truly paranoid happy. Must be
something in the water in Redmond. Essentially, the bank becomes a
quasi-anonymous "line" in what's normally a peer-to-peer transaction.
Takes getting used to.

He's got a web page with all of this in gory detail, I bet, and his
e-mail address is at the top of this post.



Speaking of micropayments, Mark Manasse, Ron Rivest, Adi Shamir, and
Silvio Micali did another talk on Friday which touched on several cool
micropayment schemes, and a much more cost-effective way to do key
revocation. Though I got there exactly 6 minutes late, I missed one
presentation, and didn't take any notes for the rest. Hope someone else
here did. I saw lots of DCSB/Cypherpunks there... Any takers?

Cheers,

Bob Hettinga






-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMNdbfvgyLN8bw6ZVAQH7qwP9GKSx7BegCr5lAOmG6lBo4OYgCPUO9j8N
bqf89b46rTkYrTkSB2DDX7BG/wu4nv/pnf7rA7UBHJjydZuiAVG9KplzevUWFoaI
xVeW8AoVPgKvkZsELK4VrrOayAXNxX9FBX7vGwsedl1SjQgyA3Qo62799GOIDrpQ
xuXYtTtaTfw=
=LQk+
-----END PGP SIGNATURE-----

-----------------
Robert Hettinga (rah@shipwright.com)
e$, 44 Farquhar Street, Boston, MA 02131 USA (617) 958-3971
"Reality is not optional." --Thomas Sowell
The NEW(!) e$ Home Page: http://thumper.vmeng.com/pub/rah/
>>>>Phree Phil: Email: zldf@clark.net  http://www.netresponse.com/zldf <<<<<