Superpolynomially small

The notion of impossibility of a task for a polynomial-time attacker is neither worst-case complexity nor average-case complexity. Instead, as explained in Section 2.3, the success probability of an attacker has to be negligibly small, where the probability is taken over both the problem instances and the internal random choices of the attacker. A sequence n of non-negative values is called negligibly small or superpolynomially small if for all c > 0 for sufficiently large k < k . Some authors abbreviate this as < l/poly(k) . Similarly, the sequence is called exponentially small if it is smaller than the inverse of some exponential function in k. 

Computational security. For computational security, the quantifier over the attacker strategies is restricted toAe PPA n Attacker class(Scheme, Req), where PPA denotes the class of probabilistic polynomial-time interactive algorithms. In this case, one can at most allow other system parameters to grow polynomially with the security parameters under consideration, and one usually requires superpolynomially small error probabilities only. 

Suitable classes of very small functions are those where the probability decreases superpolynomially or exponentially in one of the security parameters, say k. However, one must take care with the remaining system parameters. In the order of increasing security, one can leave them constant while k tends to infinity, or let them grow at most polynomially with k, or universally quantify over them after the quantifier over k. Moreover, some requirements may only be fulfilled if more than one security parameter tends to infinity. Examples can be seen in later chapters. 

The best general-purpose algorithms used in practice until recently have expected miming times of L [ c] with small constants c (between 1 and depending on whether one only considers algorithms whose running time has been proved). As time complexity is usually measured in terms of the length of the input, not of the input n itself, this is superpolynomial, but not strictly exponential because of the square root in the exponent. The number field sieve only has a third root in the exponent, i.e., c] with c around 2. 

---

See also in sourсe #XX -- [ ]

---