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) 1/2 + negl(n). He can always toss a coin (that gives hom probability 1/2) but maybe he can extract some piece of information that "improves" his guess.
twallutis
- 159
- 5