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.
Related On-Line Papers: