I have an intuitive idea of this, but I am not sure if I am formally interpreting it correctly. In the scenario I am considering, each party is identified by a sequence of $n$ bits and I have $2^{n}$ parties. If I say that an adversary can control a polynomial number of parties, what does it mean formally? Is it with respect to $n$, $2^{n}$ or what? How do you explicit it as a function?

My idea is that, since the number of parties is exponential with respect to $n$ (in particular, it is $2^{n}$), then, saying that the adversary controls a polynomial number of parties means that it controls a number of parties that is polynomial with respect to $n$. It can be $2 \cdot n$, $n^{2}$ or any polynomial function of $n$ (it should be possible to express it in general as $poly(n)$).

Is this correct?

  • 1
    $\begingroup$ Usually in complexity theoretical cryptography when we say "polynomial in x" we mean "polynomial in the length of x" which means "polynomial in $1^n$" in cryptography. $\endgroup$
    – SEJPM
    May 17, 2020 at 14:40
  • $\begingroup$ Thanks a lot. It seems to be equivalent to what I assumed then. $\endgroup$
    – Lorenzo
    May 17, 2020 at 14:55


Your Answer

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

Browse other questions tagged or ask your own question.