From: hal@rain.org
Date: Wed Feb 03 1999 - 15:20:18 MST
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:02:59 MST