5
$\begingroup$

Suppose that $\mu(n)$ is a negligible function, which means that for every $c>0$ there is some $N$ such that for all $n>N$ it holds that $\mu(n)\leq n^{-c}$.

Now, imagine that some encryption scheme, signature scheme, or some cryptographic primitive in general has an "error" (distinguishing error, forging error, etc.) of $\mu(n)$. Imagine that now I want to set up my primitive so that this error is no larger than $2^{-80}$. If I had the explicit expression for $\mu(n)$ (which is likely to be the case if I read the security proof of the given primitive) then I would solve the inequality $\mu(n)\leq 2^{-80}$ for $n$. In practice (even though this is not necessarily the case), negligible functions look pretty much like exponentials $2^{-n}$, so we know that this $n$ will be polynomial in $80$ and therefore it won't be too large.

Now think of the general case. Suppose I want to find some $n$ such that $\mu(n)\leq 2^{-\kappa}$ for some $\kappa$, let's denote the minimum of such $n$'s by $n(\kappa)$. We know that such value must exist simply because $\mu$ tends to zero as $n$ approaches infinity. Moreover, since $\mu$ is negligible, intuition on the definition says that $n(\kappa)$ shouldn't be too large in terms of $\kappa$ (e.g. if $\mu(n) = 2^{-n}$ then $n(\kappa) = \kappa$). My question is: how do we actually prove this?

Here's my question, extracted from the motivation above:

Let $\mu$ be a negligible function, and let $n(\kappa)$ be the smallest $n$ such that $\mu(n)\leq 2^{-\kappa}$. Prove that $n(\kappa)$ does not grow too fast as $\kappa\to\infty$.

Part of the question requires to specify precisely what is meant by "too fast". I would love some statement like "$n(\kappa)$ is polynomial in $\kappa$", but I'm not sure how to prove this.

I believe this property is important as this is one of the reasons why we choose negligible functions (besides being closed on additions and multiplication by polynomials): it allows us to get small error probabilities without increasing the security parameter too much.

Any insights on this are welcome.

$\endgroup$
  • $\begingroup$ I don't think you can get something very explicit. The definition of negligible itself is not very explicit, so I would expect that the best you can get here is something like "for every $c$ there is a $\kappa$ such that $n(\kappa)\leq \ldots$". I need to work the math harder to figure out the exact expression, but this is my intuition. $\endgroup$ – Cristina Mar 10 '18 at 15:22
  • $\begingroup$ Hmmm, yes, I was also expecting that. I just thought this question might have been studied before, and a more satisfactory solution could exist. $\endgroup$ – Daniel Mar 10 '18 at 15:23
2
$\begingroup$

The function $n^{-\log(n)}=2^{-\log(n)^2}$ is negligible, but $n(\kappa)$ for it is $2^{\sqrt{\kappa}}$ which is not polynomial in $\kappa$.

If we look at the functions $\mu_c(n)=n^c$, their $n_c(\kappa)$ is $2^\frac{\kappa}{c}$, so if $\mu$ is negligible, its $n(\kappa)$ must be smaller than those (at least for big enough $\kappa$, this is ok since you asked for the asymptotics). This means that $n(\kappa)$ is subexponential, i.e., $n(\kappa)=2^{o(\kappa)}$.

$\endgroup$
  • $\begingroup$ True. But then what can we really say about $n(\kappa)$? Sounds like there is nothing really interesting we can say about it. $\endgroup$ – Daniel Mar 12 '18 at 18:42
  • $\begingroup$ @Daniel I edited my answer to include the asymptotics of $n(\kappa)$ $\endgroup$ – Florian Bourse Mar 13 '18 at 9:05
1
$\begingroup$

Functions like $f(n) = 2^{-n^{0.01}}$ are negligible, but if you want to get $f(n) < 2^{-\kappa}$ for this function then you need to set $n > \kappa^{100}$. So in general you can make negligible functions that require $n(\kappa) = n^c$ for any $c$ you like.

I'm fairly sure $n(\kappa)$ should always be polynomial, but don't have a proof.

$\endgroup$
  • $\begingroup$ Thanks! That makes sense. Actually, you made me notice an error I had in my question (which I just fixed). $n$ is not logarithmic in $\kappa$, but polynomial (at least it should). It would be great to get a proof of this fact. $\endgroup$ – Daniel Mar 10 '18 at 17:04
  • $\begingroup$ Thinking about this... it seems very hard to ensure this property! After all, why does it have to be the case that $n(\kappa)$ is polynomial? If one were to argue by contradiction, using the negation of being polynomial doesn't fit that much with the properties of $\mu$ $\endgroup$ – Daniel Mar 11 '18 at 0:42

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.