Eliezer S. Yudkowsky, <sentience@pobox.com>, writes:
> hal@rain.org wrote:
> >
> > The calculation takes only a second or so per piece of email, so it is an
> > insignificant cost for most users. But spammers who send out thousands of
> > emails must now customize each one with separate headers and a separate
> > computation. The total computational costs for them are much higher and
> > it automatically puts a limit on how much spam they can afford to send.
>
> The problem should be NP. Thus my mail software only takes a
> millisecond to verify the message, but the spammer still takes a second
> to send it. (Otherwise you've increased their sending costs, but also
> my annoyance on the other end.)
Yes, you're absolutely right. I was remembering the idea incorrectly.
The actual idea was more like requiring the sender to find a random value such that hash (rand, to, subject, date) produces output that has some specified form, like 21 low bits of zeros, where hash() is a cryptographic one-way hash function. This would require on the average trying one million different random values before you find one that works. However the recipient can check it instantly.
Hal