Linear sharing

There are two main approaches to the multi-party computation: garbling circuits and linear sharing. Garbling circuits are not viable in our case (they are 2 party), so we use the linear sharing approach. There are few different flavors of the sharing; we use SPDZ, but most of ours constructions probably can be switched to other kinds of linear sharing.

We work over a prime field of large size, denoted ​$\mathbb{F}_p$.

Linearly shared variable is represented as ​$[x]$, which denotes the share $x_i$ for a party $i$ (i.e. any formula involving shared values is read by substituting $[x]$ by $x_i$ for a point of view of $i$-th party).

In SPDZ, the "true" value $x$ is reconstructed just as a sum of shares $x = \underset{i=0}{\overset{n-1}{\sum}} x_i$.

The value can be "opened", which means that the parties reveal their shares to eachother. It can be done either with or without first commiting to the share - in the latter case, the parties which open their share later can, potentially, change the result. We always assume that the open functionality does not commit to the shares, unless stated explicitly.

In SPDZ, each shared value ​$[x]$ is normally accompanied with the independently shared value $[\lambda x]$​, for a globally chosen unique shared MAC key $[\lambda]$. This is used for the integrity checks. We do not use it in the current protocol because we need to produce a zk-proof anyways, and integrity validation does not work in case all parties do collude.

We do it (but do not spell it out explictly) in computations in the offline phase, to ensure that every part of correlated randomness is distributed as required.

Public values can be multiplied by shared values naively: $y \times [x] = y[x]$, and public value $y$ can be turned into the shared value by setting $y_0 = y$, $y_i = 0 \text{ for } i>0$ . This conversion is assumed in the cases where public value needs to be treated as shared (say, they are added).