brief review of MIT 12/15/95 "micro-commerce" talks

[james@sparta.lcs.mit.edu (James W. O'Toole Jr.)]

This is a quick summary of the Friday 12/15/95 talks at MIT on
micro-commerce:

Millicent	--- Mark Manasse, Digital Equipment Corporation
	Brokers purchase "scrip" in large batches from vendors;
	users purchase scrip small batches from brokers;
	users give small scrip to vendors in each purchase transaction.
	"Scrip" is vendor-specific and its validity can be efficiently
	verified using hashing.  No public-key crypto is required
	to carry out the protocols, because pairwise trust relationships
	between user and broker, and between broker and vendor, are
	established and these pairs share secrets.


PayWord		--- Ron Rivest, MIT
	Users are issued certificates by brokers, indicating that
	the broker will extend credit to the user.
	Users generate long hash-chains by repeatedly hashing a
	random seed value to obtain a hash-chain root.  Then the user
	promises to a specific vendor that he will pay one cent per
	element of that hash-chain.  This promise is made by the user
	signing (using PKC) the root of the hash chain.
	Each time the user wants to pay one cent to the vendor, she
	sends another element of the hash-chain, working backwards from
	the root, as in the S/Key system.  The vendor redeems the whole
	chain (or whatever portion the user has spent) by sending the
	user's signed promise and the last spent element of the chain
	to the broker.


MicroMint	--- Adi Shamir
	A scheme for issuing coins that is much more like traditional
	physical coin systems in that forgery and cheating are possible,
	but only practical on a large scale, and are detectable and can be
	combatted.  A "coin" in the MicroMint system is a set of 4 values
	that hash to the same value.  Producing such 4-way-colliding values
	is much less expensive in bulk than individually.  The mint produces
	coins in bulk and will redeem them into cash.  To combat active
	forgers, the mint can embed secrets in the coins and reveal the
	secrets	progressively so that vendors can detect forged coins
	cheaply.


Lightweight Signatures for Revocation	--- Silvio Micali, MIT
	A cost/performance analysis of the key revocation system for the
	U.S. Federal Goverment's Public Key Infrastructure.  Taking a
	MITRE-designed plan as a starting point, the communications costs
	are analyzed.  In the MITRE plan, the certification authorities issue
	revocation lists on a semi-weekly or daily basis, these lists being
	then stored in an untrusted and highly replicated database.  When
	a public key is being checked, the receiver queries the database
	to determine the status of the public-key.  In the talk, Silvio
	showed how lightweight signatures can be used to reduce the size
	(and therefore transmission cost) of the revocation lists.
	He also showed that transmission costs can be dramatically
	reduced by not sending large revocation lists in response to queries.
	Instead, the replicated database can store a timestamped
	key-status-report (signed by the certification authority) for
	every single key.  This key-status-report is much smaller than
	the full revocation list.

Overall, the PayWord scheme is probably the one to watch for actual use
on the Internet.  Millicent has an advantage of not using PKC, but
PayWord may be simpler to implement and is being discussed in the WWW
Consortiom and the IETF as a possible draft standard.  It is also worth
noting that PayWord operates essentially by combining a
PKC-signature-based authentication (between user and broker) with a
One-Time-Password (OTP) authentication scheme (as in the S/Key system).
OTP has been getting standardized recently on the Internet and maybe
that will help too.