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

Jiawei Wu

4/19/24, 10:48 AM

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.

1 + 0

oblivious-transfer

multiparty-computation

Score:1

Crypto

Mr. Jones

4/19/24, 7:03 PM

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:

Alice chooses a random bit $b$ and accepts it as its secret share of $[x\cdot y]$
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$.
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$

+ 3

Jiawei Wu

4/20/24, 5:52 AM

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?

Mr. Jones

4/20/24, 6:22 PM

@JiaweiWu what you say is correct. It is also true that garbled circuits are conceptually similar. Most MPC tricks tend to repeat :)

Jiawei Wu

4/21/24, 7:11 AM

Many thanks for your answer!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

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.