Negligible probabilities – Encryption and Decryption
4.4.2 Negligible probabilities
As discussed earlier in this chapter, computational security allows having encryption schemes that Eve might break with some very small probability. As long as this probability is negligible, such schemes are considered secure.
But how specifically small does a probability need to be to be considered negligible? In cryptography, this is precisely defined using negligible functions. A negligible function is a function that decreases faster toward zero with n than the reciprocal of any polynomial. More formally, a function f is negligible if for every polynomial p there exists an N such that for all integers n > N it holds that:
As an example, both the functions 2−n and 2− are negligible (although they approach zero at different rates).
If Eve might break an encryption scheme E with the probability of 1∕p(n) for some (positive) polynomial p, E is considered insecure. In contrast, if Eve can break that scheme with a probability that is asymptotically smaller than 1∕p(n) for every polynomial p, then the scheme is consider secure because the probability of Eve’s success is so tiny that it can be neglected.
Events that occur with a negligible probability (using the precise definition given earlier) are so unlikely to happen that they can be ignored in practice [97]. Thus, in the context of computational security, the breaking of an encryption scheme that happens with negligible probability can be ignored.
To summarize, in the realm of computational security, an encryption scheme is considered secure if, for every probabilistic polynomial-time attack, the probability of that attack being successful is negligible [97].
The preceding security definition is asymptotic because it employs the concept of negligible probability. Recall that negligible probability allows Eve to succeed for small values of the security parameter n. But when that value crosses some threshold N, the probability of Eve succeeding becomes so small we can neglect it.