Abstract:

Consider the following simple technique for combatting 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, as a single machine can send only 8,000 messages per day. 
   
This talk describes recent work on the choice of functional challenges 
that can be used to yield easily verifiable proofs of computational
effort, especially in retrieving information from memory.
   
Joint work with Cynthia Dwork and Andrew Goldberg