2
$\begingroup$

While studying Yao's garbled circuits I was mentioned that correlated randomness played some part in MPC. I looked for online documentation but everything I've found is far too complicated for me to understand.

Could anyone briefly explain the role (and functioning) of correlated randomness?

$\endgroup$
2
$\begingroup$

Correlated randomness and garbled circuits are two different approaches to achieve secure multiparty computation. They have nothing to do directly with each other.

Highly multi-party protocols like SPDZ, TinyOT, etc., which are secure against a dishonest majority, are based on correlated randomness. Protocols in this paradigm have two phases.

  1. In the first phase, the parties do a specialized MPC for the following task: it takes no inputs, but samples $(r_1, \ldots, r_n)$ from some agreed-upon distribution, and outputs $r_i$ to party $P_i$. The outputs of this phase are called the correlated randomness. Since this phase doesn't use any specific inputs of the parties, it can be done well beforehand.

  2. In the second phase, the parties consume their correlated randomness to perform MPC of a desired function $f$, on their chosen inputs for $f$. This phase is often information-theoretically secure (assuming the security of the first phase).

The absolute simplest correlated randomness is a multiplication triple (proposed by Beaver in 1991). Let $[s]$ denote a situation where the parties have a secret-sharing of $s$. The details of the secret sharing are not too important -- you can imagine simple additive secret sharing or Shamir secret sharing. The only important property is additive homomorphism: from $[s],[t]$ it is possible to compute $[s+t]$ (cheaply, usually without interaction).

  1. The correlated randomness consists of $[a],[b],[c]$ where $a,b$ are random field elements and $c=ab$. These values are called a multiplication triple. I won't elaborate on the parties generate a multiplication triple, I just want to focus on how random values like this can be used for MPC.

  2. Later suppose the parties have secret shares $[x]$ and $[y]$ and they want to multiply them to learn $xy$. This is a multiplication of chosen inputs. How can they use the multiplication triple, which uses random values that are unrelated to the multiplication they really care about?

    • Parties compute $[x+a]$ and $[y+b]$ (using additive homomorphic properties of the secret sharing) and publicly open them as $d=x+a$ and $e=y+b$. Since $a$, $b$ are random and unknown to any party, opening $d$ and $e$ reveals nothing about $x,y$ (but this "one-time pad" means that this particular multiplication triple can be used only once in this way).
    • Note that $xy = (d-a)(e-b) = de - ae - da + ab$. But parties know $e,d$ in the clear and they have secret shares of $a, b,$ and $ab$. So they can use the homomorphic properties of the sharing scheme to compute $de - e[a] - d[b] + [c]$ and open it. The result is the $xy$ they care about.

This (and other tricks) are roughly how correlated randomness is used for MPC. For a very good overview of this protocol paradigm, I highly recommend Claudio Orlandi's excellent tutorial video about the topic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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