6
$\begingroup$

In the field of Cryptography and Computation Complexity there is a notion of negligible function.

I have some difficulties in understanding intuition behind this notion. The following are some definitions from Chapter 9. Cryptography from the textbook Computation Complexity. A modern approach by Arora and Barak with extensive use of negligible function. There my question after every definition about negligible function.

Before proceeding further, we make a simple definition that will greatly simplify notation throughout this chapter.

Definition of negligible function. a function $\epsilon : \mathbb{N} \rightarrow [0,1]$ is called negligible if $\epsilon(n)=n^{-\omega(1)}$.

Because negligible functions tend to zero very fast as their input grows, events that happen with negligible probability can be safely ignored in most practical and theoretical settings.

So far so good, it's just the definition of negligible function, the only point is why do we need to care about this function if it "can be safely ignored".

The notion of computational secure function.$k \in_R \{0,1\}^n, x \in_R \{0,1\}^m, Pr [A(E_k(x))=(i,b) s.t. x_i=b] \leq \frac{1}{2}+\epsilon(n)$.

Less intuitive usage of negligible function. As I understood, in general, $A$ can with probability 0.5 guess uniformly distributed $x_i$, therefore it makes sence to expected lower bound of success to be $\leq \frac{1}{2}$, however it's $\leq \frac{1}{2} + \epsilon(n)$, it we can "safely ignore" $\epsilon(n)$ why to mention it, and the second point is it possible to run $A$ some fixed finite number of times to get probability infinitely close to 1?

Definition of one-way function. $x\in_R\{0,1\}^n, y=f(x), Pr[A(y)=x' s.t. f(x')=y] < \epsilon(n)$

In this case, the usage of negligible function is very intuitive, the success probability is upper bounded by negligible function $\epsilon(n)$. I am not sure how it's correlated with existence of computationally secure encryption scheme (of course =0 is preferable by encryption scheme), however if $\epsilon(n)$ can be safely ignored than it's ok.

The problem is I am not quite understand why do we need negligible function. By mentioning few definition I tried to be more specific about what exactly I don't understand.

I would appreciate if anyone can shed the light on the usage of negligible function

$\endgroup$
5
$\begingroup$

If you repeat an Algorithm $A$ with negligible probability $\epsilon(n)$ of success for an input of length $n$ the number of times until the first success happens is a geometrically distributed random variable $S$. The expected value of $S$ is

$$\mathbb{E}(S) = \frac{1}{\epsilon(n)} = n^{\omega(1)} \quad .$$

So an attacker using $A$ polynomial many times (say $p(n)$) can't have non negligible probability of success, which we'll see by comparing expected values. Let $A'$ be the algorithm which repeats $A$ $p(n)$ times and the random variable which represents the number of times $A'$ has to be repeated until the first success shall be named $S'$. Then:

$$\mathbb{E}(S) \leq p(n) \mathbb{E}(S')\quad,$$

so a non negligible success probability for $A'$ would mean a non negligible probability for $A$, since the product of two polynomials is again polynomial. So allowing negligible probabilities does no harm (at least for polynomial bounded adversaries).

This is essentially contains an indirect proof that $p(n)\epsilon(n)$ is still negligible for any polynomial $p$, which can also be proven directly: $p$ is dominated by its largest exponent, so $p(n)\in \mathcal O(n^c)$ for some $c \in\mathbb{N}$. On the other hand $\epsilon(n)\in o(n^{-d})$ for all $d\in\mathbb{N}$. Define $d'=d-c$ and you'll get $\epsilon(n)\in o(n^{-(d'+c)})$ for all $d'\in\mathbb{N}$. So $p(n)\epsilon(n)\in o(n^{-(d'+c)})\mathcal O(n^c)=o(n^{-d'})$ for all $d'\in\mathbb{N}$, which is again negligible.

If you insist on a probability of $0$ (or $\frac{1}{2}$ in the case of distinguishers) many applications become (nearly) impossible. Consider a cryptographic hash function $h$ and an unknown argument $x$. The probability of finding a preimage $x'$ s.t. $h(x')=h(x)$ taken over all $x$ can't be $0$, because testing all possible inputs will lead to success eventually. You could however choose to limit the probability with $2^{-n^{\Omega(1)}}$ or similar and call only those functions negligible. But most of the time only unbounded adversaries or efficient (i.e. polynomially bounded) adversaries are considered, so the different notions wouldn't matter, as an efficient adversary can break none and and unbounded can break both.

$\endgroup$
  • 1
    $\begingroup$ "... testing all possible inputs will lead to success eventually" - but that would take exponential time. On the other hand, if you try only polynomially many inputs, your success probability will be negligible. That's why you have to contend with some small success probability. Negligible functions are the largest class of functions closed under "polynomial reductions", so in some sense it's a very liberal notion of security. $\endgroup$ – Yuval Filmus Apr 6 '13 at 15:39
  • $\begingroup$ @frafl, thank you very much for the great answer, I get the idea in general, and will appreciate for details. 1) major question - How to show from the definition of the negligible function that it's closed under polynomials (sorry I don't see it), may be different definition might help. 2) minor question - how come $\mathbb{E}(S)=\frac{1}{\epsilon(n)}$? Could you please show the full computation? Thank you! $\endgroup$ – com Apr 7 '13 at 7:13
  • $\begingroup$ @frafl: 1) you are right, "closed under polynomials" is $p(\epsilon(n))$, and I see why. The question why $p(n) \epsilon(n)$ is negligible? 2) understood, thanks! $\endgroup$ – com Apr 7 '13 at 12:27
  • $\begingroup$ @frafl, great, I wish I could say you "thank you" personally, very intuitive proof. One minor point I still cannot get, when I start from the end $o(n^{-d'})=o(n^c)o(n^{-(d'+c)}) \in O(n^c)o(n^{-(d'+c)})$ so the former function is slightly bigger that $o(n^{-d'})$ is it true? $\endgroup$ – com Apr 7 '13 at 17:16
  • $\begingroup$ @tam: No: $O()$ means "grows at most as fast as" and $o()$ "grows slower than", so $o(ab)=O(a)o(b)=o(b)O(a)$. However I think $f\in o(ab)\rightarrow f \in o(a)o(b)$, because $f\cdot(ab)^{-1}\in o(1)$ and so is $\sqrt{f\cdot(ab)^{-1}}\in o(1)$, therefore $f\cdot(ab)^{-1}\in o(1)o(1)$ and $f\in o(a)o(b)$. $\endgroup$ – frafl Apr 7 '13 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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