hashcash / Dwork-Naor paper (Re: RSA Conference: Deterence measures for SPAM)

[Adam Back <aba@dcs.ex.ac.uk>]

Steve Schear <schear@lvdi.net> writes on cypherpunks:
> Kevin McCurley, IBM, delivered a paper on using electronic commerce
> techniques (i.e., d-postage) to deter SPAM.  He cites a work by
> Cynthia Dwork and Moni Naor, "Pricing via Processing or Combatting
> Junk Mail," 
> http://www.wisdom.weizmann.ac.il/Papers/trs/CS95-20/abstract.html I
> wan't able to access that paper and would be interested to know how
> similar their appraoch is to HashCash.

I had a look and their approach is very similar to that of hashcash.
Thanks for posting the reference, I found the paper very interesting,
and have contacted the authors (and Kevin (who is also webmaster of
www.digicrime.com)) with comments.  Their work predates hashcash by
about 4 years.  They have the same idea of using a CPU cost function
to combat unsolicited bulk email and other unmetered resource abuses.

Their cost functions are not based on hash collisions, but on public
key problems.  The use of public key problems allows them to construct
a trap-door cost function.  The holder of the private key can compute
valid tokens cheaply.  This allows them to propose a third party which
sells bulk email tokens without itself having to have large CPU
resources.  Their example application is what they see as legitimate
bulk emails, like conference calls.  (I am not sure I always agree
with this -- I get no end of spam conference calls which I have no
interest in attending or submitting to, but the functionality of
trap-door cost functions does allow more flexibility).

Their cost functions are more expensive to verify than hashcash
because they involve modular exponentations.

I can simulate the short cut cost function functionality with
symmetric encryption techniques by modifying the hashcash protocol.
Users, or service providers wishing to participate in enabling a third
party to sell tokens to bulk emailers for their email address(es) can
aid the third party in bypassing the hashcash verification process on
their eternity filter.

This can be done with no databases on the ISP mail hub server
(preserving privacy), and with no real time communications required
between trusted bulk email token seller and mail hub.

Adam