Semi Hard Problem

last modified: February 1, 2006

A semi-hard problem is a problem which requires a human-noticeable amount of time to solve on a typical computer; but is not intractable. Examples include partial hash collisions, factoring of medium-sized numbers (64-128 bits), etc.

SemiHardProblems are useful in combatting DenialOfService attacks, wherein the amount of requests for service (spam emails, etc) generated by an attacker is far greater than what a legitimate user would generate. Solving one instance of the problem is not a significant load on a legitimate user's system, but solving many different instances of the problem is.

One application of this trick is HashCash.


Loading...