Why do we always assume that the functions that the protocols can replicate are of the form $f:\{0,1\}^*\to\{0,1\}^*$?

Question

Taking into account the vast literature of secure multiparty computation and secret sharing, there is a specific assumption that is made for the calculation of a rule function. The latter function takes as inputs the individual secrets of the agents and gives as outputs individual instructions based on the rule that the agents want to mimic. Recall again that, every player $i$, of $N<+\infty$ players, holds a secret say $x_i$. All of them want to share their information in such a way that a rule function $f(x_1,x_2,\cdots,x_N)=(a_1,a_2,...a_N)$ is shaped in a certain way and every player at the end of the protocol will know only her own component $a_i=f(x_i)$ and no other information.

• Why do we assume that $f$ is a polynomial function or polynomial in time? What is the intuition behind this?
• The protocols of Rabin, Ben-or and Ben-or et al assume that $f$ is a function such that her domain and co-domain is the same, namely $f:\{0,1\}^*\to\{0,1\}^*$, but this restricts the types of functions that we can replicate with the help of the protocols isn't it? Why do we assume that this is the only family of functions that the protocols can mimic? Does this family of functions restricts the problem to polynomial functions as well? Can this assumption change?
• Also in page $79$ the protocol of Rabin and Ben-or quotes ``that $P_i$ shares $\beta_i$ using $h_i(x)$..." but where does this function $h_i$ comes from? They have not defined any such function until that point?

Answer 1

Why do we assume that f is a polynomial function or polynomial in time? What is the intuition behind this?

I trust you're already familiar with why do we use polynomial time as a baseline for essentially all of the cryptography (check Kelalaka's comments). In a nutshell, there are countless reasons why we believe this is a reasonably sound model for what we intuitively call "efficient computation". Here, in the context of MPC, it is no different: we want to be able to focus on computations that are efficient to be carried out.

this restricts the types of functions that we can replicate with the help of the protocols isn't it? Why do we assume that this is the only family of functions that the protocols can mimic? Does this family of functions restrict the problem to polynomial functions as well? Can this assumption

I'm not familiar with the exact wording in these papers, but typically whenever you refer to functions with unbounded input/output, then you are really considering these that are still computable in polynomial time with respect to the input length. Once again, this is because we model the participants of the protocol as polynomial-time machines and we would like them to be able to finish the computation.

---

In addition, there are notions of security that rely on the assumption that the adversary is computationally-bounded. For example, there are protocols whose security relies on the inability of an adversary to factor large numbers. This is possible of course given enough computation time to try all possible prime factors, but a polynomial-time adversary is not able to do this.

However, there are other notions in the context of secure multiparty computation where we can indeed tolerate adversaries who run in superpolynomial time. Protocols with perfect and statistical security (which receive the umbrella term of information-theoretic security) are designed in such a way that no adversary, no matter the number of computational resources or running time, can break the security of the protocol.

Given this, in principle, we could enable all parties (not only the adversary) to run in superpolynomial time, but then the question becomes what is really gained by doing this. Basically, I cannot think of meaningful non-polynomial functions we would like to compute.