The Complexity of Fighting Spam   

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.

To apply this approach one needs to  be  able  to  come  up  with computational  problems where solving them requires significant expenditure of resources while verifying a solution can be done easily.   The papers below  introduce  this  approach (see here) and concentrate on the choice of  computational  problems  for  which most of  the  work is in retrieving information from memory (see here).  In particular  the connection to pebbling problems is described here. Finally, for a survey on moderate hardness see here.

Recent talk on the subject: ppt

On-Line Papers:

Back to On-Line Publications

Back Home