Join Log in
Score:2
Hunger Learn avatar Crypto

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

ua flag
Hunger Learn

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?
98
0 + 0
kelalaka avatar
in flag
kelalaka
If you don't restrict, then the adversary time will be too complicated. We model the adversary to be polynomial-time, too. If we don't how the adversary can lose in any game?
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
So we need the polynomial time assumption only for the adversary? And since we assume that the adversaries are finite in number say $t$, then any $n>2t+1$ protocol can be executed by secure multiparty computations in finite horizon time? But, why polynomials? what is the intuition?
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@kelalaka also in game theory, the function $f$ represents a signal or a strategy that is correlated, what is the intuition behind the assumption that $f$ is a polynomial function?
0
Reply
kelalaka avatar
in flag
kelalaka
https://iacr.org/publications/dl/ann2014.html
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
@kelalaka could you explain what this link is?
1
Reply
kelalaka avatar
in flag
kelalaka
[Why do we focus on polynomial time, rather than other kinds of time?](https://crypto.stackexchange.com/a/62463/18298)
0
Reply
Score:2
Daniel avatar Crypto
ru flag
Daniel

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.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.