Trouble understanding the theory behind negligible functions and their applications in cryptography

Question

I was formally taught that:

$\epsilon$ is a function $\epsilon\colon \mathbb{Z^{\geq0}}\rightarrow \mathbb{R^{\geq0}}$ and if $\exists$d: $\epsilon$ ($\lambda$) $\geq \frac{1}{\lambda^{d}}$ then $\epsilon$ is non-negligible, and if $\forall$d, $\lambda \geq \lambda_{d}$: $\epsilon (\lambda) \leq \frac{1}{\lambda^{d}}$ then $\epsilon$ is negligible.

Now I'm having a hard time understanding a few things:

1) When $\epsilon$ is non-negligible, this means that our pseudo-random generator doesn't work well, correct? Essentially, this is to say that some adversary can predict our "random" key with probability greater than $1/2$?

2) What does $\epsilon:\mathbb{Z^{\geq0}}\longrightarrow \mathbb{R^{\geq0}}$ mean? I'm just starting to get into math theory, and I understand other functions that follow the same procedure (i.e. $E\colon M\times K \longrightarrow C$ for encryption, message space, key space, and ciphertext E, M, K, and C, respectively) but this one makes little sense to me.

3) What are $\lambda_d$, $\lambda^d$, and $\epsilon (\lambda)$?

Also, external resources are always welcome.

Thank you!

Answer 1

A function is negligible if it is "small enough" to all practical purposes. For example, if you have a procedure that can $\epsilon$-distinguish between the output of a PRNG and random bits, then one can boost this procedure (by repeating it) and get a $1/2$-distinguisher, as you mention. This boosting only works if $\epsilon$ is non-negligible, since you are only allowed to repeat the original distinguisher polynomially many times. This is the intuition behind the definition.

In order to formally define when a function $\epsilon$ is negligible, we first narrow down our interests to functions that take as input a non-negative integer $\lambda$ (the security parameter) and output a non-negative real number $\epsilon(\lambda)$. This is the meaning behind the notation $\epsilon \colon \mathbb{Z}^{\geq 0} \longrightarrow \mathbb{R}^{\geq 0}$. The security parameter $\lambda$ is a parameter that the performance of the cryptosystem is measured against - for example, a distinguisher should run in time polynomial in $\lambda$.

A function $\epsilon$ is non-negligible if $\epsilon(\lambda) = \Omega(\lambda^{-d})$ for some $d \geq 0$. Equivalently, there is some $d \geq 0$ such that for large enough $\lambda$, it is the case that $\epsilon(\lambda) \geq \lambda^{-d}$. We say that $\epsilon$ has inverse polynomial growth ($\lambda^d$ is the polynomial in question; it is a polynomial in $\lambda$). Even more formally, there is some $d \geq 0$ and some $\lambda_0 \in \mathbb{Z}$ such that for all $\lambda \geq \lambda_0$, it is the case that $\epsilon(\lambda) \geq \lambda^d$. For some reason, your definition uses the somewhat misleading $\lambda_d$ (the notation is misleading since it doesn't really depend on $d$).

Answer 2

To answer question 2....

The expression

$$f : A \to B$$

means "$f$ is a function with domain $A$ and codomain $B$", and is commonly read as "$f$ is a function from $A$ to $B$".

The expressions

$$ \mathbb{Z}^{\geq 0} \qquad \qquad \mathbb{R}^{\geq 0} $$

denotes the sets of non-negative integers and non-negative real numbers respectively.

So, the phrase

$$ \epsilon : \mathbb{Z}^{\geq 0} \to \mathbb{R}^{\geq 0}$$

is expressing the fact that $\epsilon$ is being used to denote a function that converts non-negative integers into non-negative real numbers.

At the risk of stating the obvious, for question 3...

$\lambda$ appears to be used to denote a non-negative integer. The expression

$$ \lambda^d $$

probably means the value you get by raising it to the $d$-th power, and the expression

$$ \epsilon(\lambda) $$

means the value you get when plugging $\lambda$ into the function $\epsilon$. I agree with the other answer that $\lambda_d$ is probably a typo and $\lambda_0$ was meant, where $\lambda_0$ also expresses an integer value. (and you've probably omitted a $\exists \lambda_0$ somewhere)

As for what these are being used for, that would depend on whatever you're reading.