On Memory-Bound Functions for Fighting Spam
Andrew Goldberg

Abstract:

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. Recently, Burrows suggested that, since=20 memory access speeds vary across machines much less than do CPU speeds, functions may behave more equitably than CPU-bound function.

We investigate this intriguing proposal, show difficulties of some natural approaches, and propose a solution. We also present experimental data that highlights our memory-bound function performance.

Joint work with Cynthia Dwork and Moni Naor.

Host: Daniel Sleator, Avrim Blum