I am a bit new to and have currently starting to learn cryptography. I am referring the book 'Introduction to Modern Cryptography' and some other blogs and texts. A concept which I am studying but not able to get full feel of is negligible functions. I have got some understanding of it but its not enough to go in-depth. Regarding the same I am solving this question where I have to prove these functions as negligible or not.
- $n^{-c}$
- $c^{-\log\log n}$
where $c$ is a constant. Can someone please show me how to approach the proof step by step so that I could use the same understanding in other examples and concepts. I would be grateful. Thanks in advance.
In the context of cryptography, negligible usually means that it is negligeable compared to the reciprocal of any polynomial. See definition 2.4 here for the precise meaning: https://intensecrypto.org/public/lec_02_computational-security.html#the-asymptotic-approach
The reason why the class of polynomial function is taken is because the usual model of 'efficient' computation refers to polynomial time algorithms. If some error decays faster than $1/p(n)$ for any $p(n)$, asymptotically it will be invisible to a fixed polynomial time algorithm. For instance, if the probability of some secret being leaked in negligible, a polynomial time adversary cannot just repeat an experiment until the secret is leaked.
For example, $n^{-c}$ is not negligible. This is because it does not shrink faster than $n^{-c - 1}$, as $n^{-c} \geq n^{-c -1}$ for $n \geq 1$.
For analyzing the other function, try taking log.