What (Where) is the formal definition of Multiparty Computation? [closed]

Question

I'm just curious where we can see a (original) formal definition of MPC. What (Where) is the formal definition of MPC?

We have a bunch of tools to build a MPC protocol. Is oblivious transfer (or OT-extension) a part of MPC?

Answer 1

The wikipedia page on Multiparty Computation (MPC) would be a good start. It gives a good introduction to the topic, and it will mention the relation with Oblivious Transfer.

I would say that, in general,

MPC studies the development of protocols that allow a set of $n$ parties $P_1,\ldots,P_n$, where each $P_i$ has a private input $x_i$, to compute a function $(z_1,\ldots,z_n) = f(x_1,\ldots,x_n)$ of these inputs in such a way that party $P_i$ only learns the value $z_i$.

If you want a more precise definition you would have to define, among other things, the terms I have written in bold. Some of the definitions can be found in the book Secure Multiparty Computation and Secret Sharing by Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen. Even though this book is for a particular type of MPC, which is Information-Theoretic MPC, most of the definitions apply for the general case.

Intuitively:

• A party is just some computer program running some code. It is typically formalized as a Turing machine, but it's precised by an interactive Turing machine in order to model the networking.
• A protocol is just a set of rules that the parties follows. Think of it as the source code of the program itself. It indicates the parties what to do at what times in order to achieve the desired result
• A party only learns $z_i$ if anything it has learned from the protocol can be simulated from only its input $x_i$ and the output $z_i$. This is much harder to precise, and it is typically done via de Universal Composability framework (read the book I referenced above, for instance).

Now, Oblivious Transfer (OT) is just a particular function to be computed, and an OT protocol is simply an MPC protocol that allows for secure computation of this function. The function can be described as $f(b,(m_0,m_1)) = (m_b,\lambda)$, where $\lambda$ simply means that the corresponding party gets no output.

Moreover, although a protocol for OT is an MPC protocol that only works for this specific function, it can be proven that you can build a general purpose MPC protocol (i.e. a protocol for any function) from an OT protocol. Therefore, in some sense, OT and MPC are "the same" (more precisely, they are equivalent, in some specific sense).