= Cryptographically negligible probability
{title2=$\varepsilon(\lambda)$}
A \b[cryptographically negligible probability] is a function $\varepsilon(\lambda)$ of the <cryptographic security parameter> that eventually becomes smaller than every inverse power of that parameter. Formally,
$$
\forall c>0\ \exists N_c\ \forall\lambda\geq N_c:
\quad 0\leq\varepsilon(\lambda)\leq\lambda^{-c}.
$$
The threshold $N_c$ may depend on $c$. This is the inverse-polynomial definition of negligibility used in asymptotic <cryptography>.<In a World of P=BPP by Oded Goldreich>[Printedp.107, preliminary definitions of negligible and noticeable probabilities]{ref}
For example, $2^{-\lambda}$ is negligible because an exponential eventually dominates every fixed power. The function $\lambda^{-100}$ is not negligible: it exceeds $\lambda^{-101}$ whenever $\lambda>1$. Even the constant $10^{-30}$ is not negligible as a function of $\lambda$, although it is numerically small. Negligibility describes a family of experiments as the parameter grows, rather than a synonym for “unlikely” in one experiment.
An original closure calculation explains why the definition is useful. Suppose an adversary gets at most $\lambda^3$ attempts and each has success probability at most $\varepsilon(\lambda)$. The <union bound> gives total success probability at most $\lambda^3\varepsilon(\lambda)$, without requiring independent attempts. Given any $c>0$, negligibility with exponent $c+4$ eventually gives
$$
\lambda^3\varepsilon(\lambda)
\leq\lambda^3\lambda^{-(c+4)}
=\lambda^{-(c+1)}\leq\lambda^{-c}.
$$
Thus a polynomial number of opportunities preserves negligibility. A concrete numerical guarantee still requires an explicit bound at the chosen parameter; the asymptotic quantifiers alone do not supply that value.
Back to article page
