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?


1 Answer 1


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.

  • $\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, 2018 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$ Jun 7, 2018 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, 2018 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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