1
$\begingroup$

If I have a probability which is > negl(n), i.e., non-negligible, will be this probability raised to the power of n also non-negligible?

$\endgroup$
3
$\begingroup$

No and yes, depending on what do you mean by $n$.

Take $f(x)=1/2$ for example. It is a non-negligible function, but $g(x)=(f(x))^x=(1/2)^{x}$ is negligible, i.e. for every positive integer $c$, there exists an integer $N_c$ such that for all $x > N_c$,

$$|g(x)|<{\frac {1}{x^{c}}}.$$

If you mean a constant $n$, then $g(x)=(f(x))^n=(1/2)^n$ is non-negligible.

$\endgroup$
  • $\begingroup$ Thank you very much for the answer! I try to prove an assertion by contradiction. I assumed that a function is not one-way, i.e. Pr[Invert(n)] > negl(n). When counting the probability of a contradicting distinguisher I got Pr[Invert(n)]^n. So I try to understand if it's non-negligible? If it is then my proof is okay. According to your answer, as n is a constant, then it should be non-negligibe. But i am not sure. $\endgroup$ – JenyaKh Jun 7 '18 at 15:09
  • $\begingroup$ Just judging from the information you provided, If $n$ is a constant, then yes it is non-negligible. However, double check your proof because in proofs $n$ is often a security parameter that is not a constant. $\endgroup$ – Changyu Dong Jun 7 '18 at 15:29
  • $\begingroup$ Okay. Thank you again! In my case {0, 1}^n is a domain of the one-way function. So I will just hope that n can be considered constant. $\endgroup$ – JenyaKh Jun 7 '18 at 15:33

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.