0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.