We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing functions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.
In the more general setting, in which we have an arbitrary resource and
a
resource manager, a user desiring access to the resource would compute
a moderately hard function
of the request id.
(The request id could be composed of the user's identifier together
with,
say the date and time of the request.)
The pricing function may be chosen to have something like a trap door:
given
some additional information the computation would be considerably less
expensive We call this a shortcut
. The shortcut may be used by the resource manager to allocate cheap
access
to the resource, as the manager sees fit, by bypassing the control
mechanism.
For example, in the case of electronic mail the shortcut permits the
post
office to grant bulk mailings at a price chosen by the post office,
circumventing
the cost of directly evaluating the pricing function for each recipient.
Postscript ,
gzipped Postscript.
Related
On-Line Papers: