1
$\begingroup$

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!

2 Answers 2