Negligible Function

Updated 11 Aug 2026

•
What it is
- •
  intuitively, a value so small it's "zero for all practical purposes" — e.g. $2^{-100}$
•
Related terms
- •
  super-poly — a value $N$ where $1/N$ is negligible
- •
  poly-bounded — a "reasonably sized" value; the running time of an efficient adversary is poly-bounded
•
Useful facts
- •
  the sum of two negligible values is negligible; the sum or product of two poly-bounded values is poly-bounded; a poly-bounded value times a negligible value is negligible
•
Two ways to formalize it
- •
  practical/concrete framing — pick concrete cutoffs, e.g. treat $1/2^{30}$ (roughly one event per gigabyte of data) as non-negligible and $1/2^{80}$ as negligible for the life of a key
- •
  asymptotic framing — treat probabilities as functions of a security parameter $\lambda$ ; a function is negligible if it's eventually smaller than $1/\lambda^d$ for every constant $d$ (decays faster than any polynomial), and non-negligible if it's infinitely often bigger than some $1/\lambda^d$
•
Note
- •
  the book itself treats the full formal definitions (of "efficient," "negligible," etc.) as necessary but "somewhat tedious, and not really very enlightening" — the intuitive picture above is what matters for following the rest of the material
•
Related
- •
  Attack Game
- •
  Semantic Security

Linked references 3