# What exactly is a negligible (and non-negligible) function?

The mathematical definition of neglible and non-neglible functions is fairly clear-cut, but why they are important and how they are used in cryptography?

-

In perfectly secret schemes like the one-time pad, the probability of success does not improve with greater computational power. However, in modern cryptographic schemes, we generally do not try to achieve perfect secrecy(yes governments may use the one time pad, but this is generally not practical for the average user). In fact, given unbounded computational power, all of our non-perfectly-secret schemes are insecure(also note that for public-key cryptography, perfect secrecy is unachievable using classic cryptography so all schemes are insecure against unbounded computational power). Instead, we define security against a specific set of adversaries whose computational power is bounded. Generally, we assume an adversary that is bounded to run in time polynomial to $n$, where $n$ is the security parameter given to the key generation algorithm(more precisely, the key generation algorithm is given input $1^n$ so that $n$ will be its input size and its output--the key--will be polynomial in the size of its input.)

So consider a scheme $\Pi$ where the only attack against it is brute force attack. We consider $\Pi$ to be secure if it cannot be broken by a brute force attack in polynomial time.

The idea of negligible probability encompasses this exact notion. In $\Pi$, let's say that we have a polynomial-bounded adversary. Brute force attack is not an option. But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one. In this case, we define security using negligible functions: The probability of success has to be smaller than the reciprocal of any polynomial function.

And this makes a lot of sense: If the success probability for an individual guess is a reciprocal of a polynomial function, then the adversary can try a polynomial amount of guesses and succeed with high probability. In sum then, if the overall success rate is $1/poly(n)$ then we consider this a feasible attack and the scheme is insecure.

So, we require that the success probability must be less than the reciprocal of every polynomial function. This way, even if the adversary tries poly(n) guesses, it will not be significant since it will only have tried:

$$poly(n)/superpoly(n)$$

As $n$ grows, the denominator grows far faster than the numerator and the success probability will not be significant.

Edited to add Here is an informal argument that may make this clearer: To see that the notions of superpolynomial brute force attack and negligible probability guessing are equivalent, consider a scheme with $K$ possible keys.

Brute force attack on the key set runs in $K$ time. Moreover, the probability of choosing a key at random and it being the correct key is $1/K$. Now, if $K$ is polynomial in $n$, (the security parameter), then this scheme can be brute forced in time $K = poly(n)$. Moreover a random guess succeeds with probability $1/K= 1/poly(n)=nonnegliglbe$ and the scheme is by both definitions insecure.

To secure the scheme then, we want to make brute force run in superpolynomial time. In other words,$K$ must be superpolynomial in $n$. Well then, the probability of guessing correctly on a single guess is $$1/K=1/superpoly(n)$$ and this is by definition negligible probability.

Although informal, I think this last part motivates the use of negligible functions in security proofs.

-
That was a nice explanation, I would +1 you if I could. –  Nico Bellic Dec 26 '12 at 6:42
Asymptotic security claims aren't that popular nowadays. Concrete security claims are preferred, because they make a statement about the concrete key sizes we use. –  CodesInChaos Dec 26 '12 at 10:06
You should add what $n$ is. Otherwise "polynomial" doesn't make much sense. –  Paŭlo Ebermann Dec 26 '12 at 12:47
@PaŭloEbermann I did mention that $n$ is the security parameter but I'll edit it to make it clearer –  AFS Dec 26 '12 at 18:25
Thanks, it is now better. –  Paŭlo Ebermann Dec 26 '12 at 19:31
While this is a very good explanation, I would like to add that you will see negligible functions also in other proofs. One example are peusdorandom strings. If an attacker looks at a string, he should only be able to decide if this string is pseudo-random or "real" random" with probability (distribution) $$½ + negl(n)$$
True. This also is related to a brute force attack. An equivalent definition for PRF security is that no adversary with oracle access to some function $f:\{0,1\)^n \rightarrow \{0,1\}^n$ can determine if it's a PRF or a random function in time $n$(the adversary is given $1^n$ as input). With unbounded time, one way to distinguish is to brute force and see if the oracle is a PRF(this works since there are at most $2^n$ functions is a PRF family with an $n$-length key while there are $2^{n*2^n}$ random functions. Without brute force though, the distinguisher can only hope to guess the right –  AFS Dec 28 '12 at 16:12