Welcome to the resource topic for 1997/004
A note on negligible functions
Authors: Mihir BellareAbstract:
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.
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .