A key idea in cryptography is using hard functions
in order to obtain secure schemes. The theory of hard functions (e.g., one-way functions) has been a great
success story, and the
community has developed a fairly strong understanding of what
types of cryptographic primitives can be achieved under which
assumption.
We explore the idea of using moderately hard
functions in order to achieve many tasks for which a perfect
solution is impossible, for instance, denial-of-service. We survey some
of the applications of such functions and in particular describe the
properties moderately hard functions need for fighting unsolicited
electronic mail. We suggest several research directions and (re)call
for the development of a theory of such functions.
Postscript ,
gzipped Postscript ,
PDF
Related
On-Line
Papers: