1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Jiawei Wu
    Apr 20, 2023 at 5:52
  • $\begingroup$ @JiaweiWu what you say is correct. It is also true that garbled circuits are conceptually similar. Most MPC tricks tend to repeat :) $\endgroup$
    – Mr. Jones
    Apr 20, 2023 at 18:22
  • $\begingroup$ Many thanks for your answer! $\endgroup$
    – Jiawei Wu
    Apr 21, 2023 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.