Gates on Spam

pvt_medic writes "Microsoft is proposing a new system that would require people to pay to send e-mails. Postage would be in the form of allowing others to use your computer to make calculations, similar to the SETi@home project. There are other systems being suggested that would include monetary stamps and people could decide on accepting an e-mail based off the value of the stamp. (story has great picture of Bill Gates as well)" Gates' proposed system will be Microsoft patent-encumbered, unsurprisingly.

Comments

Re:Cha ching, reloaded.

[helmutjd]

If you read the article, it's actually nothing to do with anything like Seti@Home, or any distributed computing application. The computation is simply there to consume time, so that it takes longer to send a message. The mail server knows the answer in advance, and if the client provides the correct answer, the message is relayed... if not, it's denied. That way, spammers HAVE to perform the expensive computation, which significantly slows their mass-mailing efforts. Typical users wouldn't even notice the delay (it could be done in the background or whatever, after the user clicks send). The results of the computation itself are meaningless... so nobody benefits from them, including Microsoft.

Re:Arg.

[Yobgod Ababua]

This article is a decent brief overview of what I was referring to: http://www.techweb.com/wire/story/TWB20031205S0009

Comment removed

[account_deleted]

Comment removed based on user account deletion

Use an NP-hard problem

[lysander]

Coming up with a problem is the least of our worries, just pick a problem that's NP-complete or at least NP-hard. Let's pick an example problem you've heard of: factoring is believed to be NP-hard, and would work fine for this purpose.

The mail server comes up with two random primes, large but not "cryptographically large", sends their product, and waits for the factorization. The mail server could even precompute what random primes it will be using for future questions, or offload that task to another server if it is too busy.

Re:Use an NP-hard problem

[Jason1729]

This is a positive point from Microsoft's point of view. Your 10 year old computer is now completely useless for sending email, so you must now buy a brand new computer, complete with a new Windows license (you don't think they'll let you use linux to run their protocol, do you? :) )

Jason
ProfQuotes

Re:Use an NP-hard problem

[SDPlaya]

The NP complete statement is simply wrong. There are NO computers in existence (except quantum and DNA computers) that can efficiently compute NP-Complete problems (at least that we know of, since NP != P is still open). What this means is that for any sized computer (even one bigger and faster than Deep Blue), it's easy to construct an NP-Complete that is tough to solve, but easy to verify. That's pretty much complexity 101.

Your point about scalability is odd. It's correct, but meaningless. There are no class of problems that you can't compute faster when the computer is faster. But saying a computer is faster is a vague statement since computers almost never uniformly get faster. CPUs get faster (even then there are tradeoffs with things like pipeline depth), memory gets faster, buses get faster, disks get faster, etc... The reason why problem scalability is an issue is because usually there is a bottleneck along one of the resources.

Now it is true that computers which are 10 years apart in age will have a different level of compute available. I imagine the amount of time it would take to construct the solution would be on the order of 1/10 second for a fast computer, and say 1-2 seconds for an old 486 (estimates). Sure not great for the 486, but how fast are you sending email with the 486? The point is that now the spammer who sends a million emails now must wait 1000000/10 seconds.

Re:Cha ching, reloaded.

[antientropic]

You either have two choices -- either the mail server does the same computation, which will either bog the hell out of any high volume mail server

Of course not. It will be the sort of problem that's easy in one direction and hard in the other - like factorisation. The server would just have to pick two large primes (relatively easy, although probabilistic), send the product to the client, have the client factor the product, and verify that the primes the client sends back are the right ones.

Re:Cha ching, reloaded.

[TheFrood]

There are all kinds of problems that are much harder to do in one direction than in the other.

Example: Factor 56,029,043 into primes. You're welcome to use Matlab, octave, xcalc, or whatever.

Answer: 7 times 19 times 43 times 97 times 101.

How long did it take you to solve? A lot more time than it took me to come up with the problem, because all I had to do was pick five primes and multiply them together. Obviously, a computer could factor that number trivially, but the concept scales easily to much bigger primes.

TheFrood

Re:Cha ching, reloaded.

[Anonymous Coward]

Couldn't the calculation to generate the question from the answer be orders of magnitude easier than the reverse?

Its public-key crypto in reverse! Generate several big primes and multiply them together. Send the product and ask for the factors.

Microsoft gets all your work for free

[ministeroforder]

Check out the fine print. "Microsoft and its Affiliates hereby grant you ("Licensee") a fully paid, royalty-free, non-exclusive, worldwide license under Microsoft's Necessary Claims to make, use, sell, offer to sell, import, and otherwise distribute Licensed Implementations, provided, Licensee, on behalf of itself and its Affiliates, hereby grants Microsoft and all other Specification Licensees, a reciprocal fully paid, royalty-free, non-exclusive, worldwide, nontransferable, nonsublicenseable, license under Necessary Claims of Licensee to make, use, sell, offer to sell, import, and otherwise distribute Licensed Implementations." basically whatever code you write, you must give to microsoft for free. Good deal eh?

Re:Cha ching, reloaded.

[ivan256]

You could whitelist those senders so they didn't have to perform the computation.

Either way, a patent encumbered system is unacceptable, no matter how technologically sound it is.

Re:Cha ching, reloaded.

[Coryoth]

Example: Factor 56,029,043 into primes. You're welcome to use Matlab, octave, xcalc, or whatever.

You need to pick bigger primes:

$ factor 56029043

56029043: 7 19 43 97 101

$


never underestimate the effectiveness of a little GNU tool like factor - sitting waiting right at your nearest bash prompt (which can be surprisingly close).

Your point is entirely valid of course, the example is just a little too easy.

Jedidiah.