Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

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$).

share|improve this answer
add comment

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.

share|improve this answer
    
I feel compelled to comment that in more general contexts, you should replace the pair of words (set, function) with something more appropriate, such as (vector space, linear map). I didn't include this in my answer since I thought it would only confuse things. –  Hurkyl Aug 8 '12 at 13:53
    
I think $\lambda_d$ is used instead of $\lambda_0$ because for larger $d$ you might need a larger $\lambda_d$ so the property still holds. Introducing the (more clear) $\exists \lambda_d$ quantor might make this notation superfluous, though. –  Paŭlo Ebermann Feb 8 '13 at 21:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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