why-negligible-funcs

Sat Apr 04 2026

Repetition Amplifies Polynomial Success Rates

Say an attacker breaks a scheme with probability $\epsilon$ in a single attempt, where $\epsilon$ is some non-negligible function of the security parameter $n$ (for example, $\epsilon = 1/n^2$).

If the attacker repeats the experiment $q$ times independently, the probability of failing every single time is:

$(1 - \epsilon)^q$

Since $(1 - \epsilon)$ is strictly less than 1, multiplying it by itself $q$ times makes it continuously decrease. So the success probability $1 - (1 - \epsilon)^q$ keeps growing toward 1.

With a polynomial base success rate, this actually works. If $\epsilon = 1/n^2$ and the attacker runs $q = n^2$ experiments, the total success probability is roughly $n^2 \cdot 1/n^2 = 1$. That's a guaranteed break.

Where This Gets Confusing

So what about making $\epsilon$ really small? If the attacker has a $0.0001\%$ chance of success, the same logic still applies. Repeating the experiment enough times drives the failure probability toward zero. The math doesn't care how small $\epsilon$ is, only that $(1 - \epsilon) < 1$.

I couldn't see why defining a special class of "negligible" functions would change anything. Multiplying a number less than 1 by itself always decreases it. What makes negligible different?

The Asymptotic Race

The answer isn't that the failure probability stops decreasing. It does decrease. The point is that the attacker is computationally bounded and can only run polynomially many experiments.

Modern cryptography limits the base success probability to a negligible function $\text{negl}(n)$, defined as a function that shrinks faster than the inverse of any positive polynomial. For any polynomial $p(n)$, there exists $N$ such that for all $n > N$:

$\text{negl}(n) < \frac{1}{p(n)}$

In practice, negligible functions shrink exponentially (like $2^{-n}$). A polynomial-time attacker is limited to $q(n)$ repetitions where $q(n)$ is some polynomial. Their total success probability is bounded by:

$q(n) \cdot \text{negl}(n)$

For example, $n^{10} \cdot 2^{-n}$. As $n$ grows, $2^{-n}$ crushes $n^{10}$. The product goes to zero no matter how large the polynomial exponent is.

This is why the definition works: a polynomial $\epsilon$ (like $1/n^2$) can be amplified to near-certainty with polynomially many tries. A negligible $\epsilon$ cannot. Polynomial repetitions can't outpace exponential shrinkage.

Why Cryptographers Prove Bounds, Not Exact Probabilities

Security proofs don't compute the exact success probability of an attacker. They prove that a worst-case ceiling is negligible, and that's enough.

The Union Bound. If an attacker has $q$ tries, each with success probability $\text{negl}(n)$, the probability of succeeding at least once is bounded by:

$P(\text{at least one success}) \le q \cdot \text{negl}(n)$

Since polynomial $\times$ negligible is still negligible, the ceiling stays negligible. That's the whole argument.

Why the bound is tight (the binomial approximation). The exact probability of at least one success in $q$ independent tries is $1 - (1 - \epsilon)^q$ where $\epsilon = \text{negl}(n)$. Expanding $(1 - \epsilon)^q$ via the binomial theorem:

$1 - q\epsilon + \frac{q(q-1)}{2}\epsilon^2 - \frac{q(q-1)(q-2)}{6}\epsilon^3 + \cdots$

Substituting back into $1 - (1 - \epsilon)^q$:

$q\epsilon - \frac{q(q-1)}{2}\epsilon^2 + \cdots$

Because $\epsilon$ is astronomically small (say $2^{-256}$), higher-order terms like $\epsilon^2$ and $\epsilon^3$ vanish. The dominant surviving term is $q\epsilon$. So the Union Bound $q \cdot \text{negl}(n)$ isn't just a valid ceiling, it's a very tight approximation of the exact value.

Why we still prefer the bound over the exact formula. The binomial formula $1 - (1 - \epsilon)^q$ assumes every attempt is perfectly independent. Real attackers use adaptive strategies: if the first query fails, they analyze that failure to craft a better second query. When trials are dependent, the binomial math breaks down entirely. The Union Bound holds even for dependent events. No matter how the attacker correlates their queries or learns from past failures, the total success probability is trapped below $q \cdot \text{negl}(n)$.