 Cryptographically negligible probability

A cryptographically negligible probability is a function $\epsilon (\lambda )$ of the cryptographic security parameter that eventually becomes smaller than every inverse power of that parameter. Formally,The threshold $N_c$ may depend on $c$. This is the inverse-polynomial definition of negligibility used in asymptotic cryptography.^[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 $\epsilon (\lambda )$. The union bound gives total success probability at most ${\lambda }^3\epsilon (\lambda )$, without requiring independent attempts. Given any $c>0$, negligibility with exponent $c+4$ eventually givesThus 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.