0
$\begingroup$

In the book IMC by Katz and Lindell, definition 3.8 says that "if for all PPT adversaries A, there is a negligible function negl such that for all n ......".

I am confused about why it holds not for "sufficiently large n's" but for "all n".

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Because the definition of "negligible" already incorporates "for all sufficiently large $n$." $\endgroup$
    – Mikero
    Mar 31 at 4:04

1 Answer 1

4
$\begingroup$

It does not matter. If the inequality $f(n)\leq \mathsf{negl}(n)$ holds for $n>n_0$, then we can always find a constant $$c_0 = \max \left\{ 1, \frac{f(1)}{\mathsf{negl}(1)}, \cdots, \frac{f(n_0)}{\mathsf{negl}(n_0)}\right\}$$ such that $f(n)\leq c_0\mathsf{negl}(n)$ holds for all $n$ while $c_0\mathsf{negl}(n)$ is still negligible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.