## A Note on Negligible Functions

** Author: M. Bellare**
** Abstract: ** In theoretical cryptography, one formalizes the notion of an
adversary's success probability being ``too small to matter'' by asking that it
be a negligible function of the security parameter. We argue that the issue
that really arises is what it might mean for a * collection * of functions
to be ``negligible.'' We consider (and define) two such notions, and prove them
equivalent. Roughly, this enables us to say that any cryptographic primitive
has a * specific * associated ``security level.'' In particular we say
this for any one-way function. We also reconcile different definitions of
negligible error arguments and computational proofs of knowledge that have
appeared in the literature. Although the motivation is cryptographic, the main
result is purely about negligible functions.

** Ref:** Journal of Cryptology Vol. 15, No. 4, 2002, pp. 271--284. Earlier
version: Technical Report CS97-529, Department of Computer Science and
Engineering, UCSD, March 1997.

** Full paper: ** Available as compressed
postscript, postscript, or
pdf. ( Help if this doesn't work).