30-10-2009, 03:11 PM
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, some moderately hard functions that most recent systems will evaluate at about the same speed are discussed. For this purpose, we rely on memory-bound computations. A family of moderately hard, memory-bound functions and Ticket servers, are described and we explain how to use them for protecting against abuses.