On Memory-Bound Functions for Fighting Spam
Cynthia Dwork Andrew Goldberg Moni Naor
Abstract:
Consider the following simple technique for combatting junk
mail (spam):
If I don't know you, and you want your e-mail to appear in my inbox,
then you must attach to your message an easily verified "proof of
computational effort"
just for me and just for this message.
If the proof of effort requires, say, 10 seconds to compute on a typical
machine, then the economics of sending spam are radically altered. This
Pricing via Processing approach was originally
in 1992 by Dwork and Naor (see
here).
They proposed specific CPU-bound functions for this purpose. Abadi, Burrows,
Manasse, and Wobber (NDSS 2003) 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. We further
investigate this intriguing proposal. Specifically, we:
- Provide a formal model of computation and a statement of the problem;
- 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. 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
- Propose a concrete instantiation of our abstract function.
- Describe techniques to permit the receiver to verify the
computation with no memory accesses
- 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.
Paper:
Postscript ,
gzipped Postscript.
Recent talk on the
subject:
ppt
Related On-Line
Papers:
- Cynthia Dwork and Moni Naor,
Pricing via Processing or Combatting Junk Mail, Proc. Crypto 1992,
Lecture Notes in Computer Science 740, Springer, pp. 139--147,
Abstract,
Postscript,
gzipped Postscript.
- Cynthia Dwork, Moni Naor and Hoteck Wee , Pebbling and Proofs of
Work. Proc. CRYPTO 2005: 37-54,
Abstract,
Postscript,
gzipped
Postscript,
PDF.
- Moni Naor, Verification of a human in the loop or
Identification via the Turing Test,
Abstract,
Postscript,
gzipped Postscript
Back
to On-Line Publications, Recent Papers
Back
Home