Fighting spam: Moderately hard memory-bound computations

Mike Burrows (joint work with Martin Abadi, Mark Manasse, and Ted Wobber)

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we discuss moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we consider memory-bound computations. This talk describes a family of moderately hard, memory-bound functions, and explains how to use them for protecting against abuses. The talk also includes a brief description of a related network service for spam deterrence.


Gates 4B (opposite 490), 10/08/02, 4:30 PM