# How to build a secure multiparty computation protocol using oblivious transfer as a blackbox?

The following statements seems to be a consensus in cryptography community.

Oblivious tranfer is a complete primitive for secure multiparty computation (SMC).

But I cannot find any explicit construction. What I want is a general method to construct SMC from OT with as few assumptions as possible, especially without the computational assumption so that it applies to information-theoretical security.

MPC is considered in many settings and flavors, so for simplicity, let's consider a 2-player, semi-honest MPC over $$\mathbb{F}_2$$ (the bit field).

Sharing the inputs, opening the output, and evaluating XOR gate should proceed as usual (via simple XOR secret sharing -- no need for OT). Alice and Bob can evaluate an AND gate on secret shared inputs $$[x],[y]$$ for $$x,y\in \mathbb{F}_2$$ as follows:

1. Alice chooses a random bit $$b$$ and accepts it as its secret share of $$[x\cdot y]$$
2. Alice prepares a 1 out of 4 OT protocol where the entry corresponding to $$[x]_A[y]_A$$ (Alice's secret shares) is set to $$b\oplus 1$$ and all other entries are set to $$b$$.
3. Bob inputs $$[x]_B[y]_B$$ into the OT protocol and accepts the output of the OT, $$c$$, as its output bit.

It is easy to see that $$b\oplus c = 1 \iff xy =1$$

• So the secret sharing works as $[x]_A + [x]_B = x$, and $b,c$ are just the secret shares of $z = x \cdot y$ ?（The plus and multiplication are in $\mathbb{F}_2$) Is this exactly the idea of Yao's garbled circuit protocol? Apr 20, 2023 at 5:52
• @JiaweiWu what you say is correct. It is also true that garbled circuits are conceptually similar. Most MPC tricks tend to repeat :) Apr 20, 2023 at 18:22