LNCS 2729 On Memory Bound Functions for Fighting Spam 1st Edition by Cynthia Dwork, Andrew Goldberg, Moni Naor  ISBN 3540451463 9783540451464

In 1992, Dwork and Naor proposed that e-mail messages be accompanied by easy-to-check proofs of computational effort in order to discourage junk e-mail, now known as spam. They proposed specific CPU-bound functions for this purpose. Burrows suggested that, since memory access speeds vary across machines much less than do CPU speeds, memory-bound functions may behave more equitably than CPU-bound functions; this approach was first explored by Abadi, Burrows, Manasse, and Wobber [3].

We further investigate this intriguing proposal. Specifically, we

1) Provide a formal model of computation and a statement of the problem;

2) Provide an abstract function and prove an asymptotically tight amortized lower bound on the number of memory accesses required to compute an acceptable proof of effort; specifically, we prove that, on average, the sender of a message must perform many unrelated accesses to memory, while the receiver, in order to verify the work, has to perform significantly fewer accesses;

3) Propose a concrete instantiation of our abstract function, inspired by the RC4 stream cipher;

4) Describe techniques to permit the receiver to verify the computation with no memory accesses;

5) Give experimental results showing that our concrete memory-bound function is only about four times slower on a 233 MHz settop box than on a 3.06 GHz workstation, and that speedup of the function is limited even if an adversary knows the access sequence and uses optimal off-line cache replacement.