A Note on Negligible Functions
Abstract: The notion of a negligible function is used in theoretical cryptography to formalize the notion of a function asymptotically ``too small to matter.'' We claim the issue that really arises is what it might mean for a sequence 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 can say this for any one-way function. We can also reconcile different definitions of negligible error arguments and computational proofs of knowledge that have appeared in the literature.
Although there are some cryptographic consequences, the main result is something purely about negligible functions.
Keywords: Negligible functions, one-way functions, arguments, proofs of knowledge.
comment: Received March 12, 1997. Revised March 23, 1997.
contact author: mihir@cs.ucsd.edu
Fetch PostScript file of the full paper.