2026-05-04

Work in progress. This note is a work in progress with many loose ends and unfinished sentences.

Multi-Party Computation

My goal here is to present semi-honest linear MPC in its most general algebraic form.

The assumption here is that the MPC will compute a coSNARK which makes computational soundness externally verifiable. In this setting adversarial resistance is less important and we can work in the more efficient passive security setting.

A linear secret sharing scheme is a method to store a secret value from a space $Z$ over a number of parties by handing each a secret share from a space $U$ . We adapt the definitions from CCXY18, ACD⁺20:

Informaly, a secret sharing scheme assigns shares to participants such that the shares encode a secret. To ensure privacy, which we will define later, there is an element of randomness in this assignment. In the linear version the secrets and shares come from linear spaces, or more generally modules over some ring and decoding is a linear operation.

Definition 1. (Linear Secret Sharing) Let $R$ be a ring, let $U$ and $Z$ be $R$ -modules, and let $n \geq 1$ . An $n$ -party $R$ -linear secret-sharing scheme with share alphabet $U$ and secret module $Z$ consists of an $R$ -submodule $C \subseteq U^{n}$ together with a surjective $R$ -module homomorphism $\psi:C \rightarrow Z$ .

The elements of $C$ are the valid share vectors, and $\psi(c)$ is the secret encoded by $c$ . A sharing $\lbrack z\rbrack$ of a secret $z \in Z$ is sampled from the fiber $\psi^{- 1}(z)$ . When the fibers are finite, the default distribution is uniform.

The language of rings and modules may seem a unfamiliar to cryptographers more acustomed to fields and vector spaces, but this generalization is practically useful as we can work over computer native data types.

Example. (3-party sharing of bytes) Take $R = U = Z = {\mathbb{Z}}/2^{8}{\mathbb{Z}}$ , the ring of unsigned bytes, and $C = R^{3}$ with $\psi(c) = c_{0} + c_{1} + c_{2}$ . To share a secret $z$ we draw $r_{0},r_{1}\overset{\ \$}{\leftarrow}R$ and take $\lbrack z\rbrack = \left( r_{0},r_{1},z - r_{0} - r_{1} \right)$ .

Informally, a subset of parties $\mathcal{A} \subseteq \lbrack n\rbrack$ is a reconstructing set if the assigned subset of shares $c_{\mathcal{A}}$ corresponds to a unique secret $z \in Z$ for any sharing $c \in C$ . We can formalize this by observing that share the selection map $\pi_{\mathcal{A}}$ is a linear map which ‘forgets” the subspace $\ker\pi_{\mathcal{A}}|_{C}$ . If this is contained in the subspace $\ker\psi$ ignored by reconstruction, then the secret is unique.

Definition 2. (Reconstruction) A set $\mathcal{A} \subseteq \lbrack n\rbrack$ is a reconstructing set if $\ker\pi_{\mathcal{A}}|_{C} \subseteq \ker\psi$ .

We say that $\mathcal{S}$ has $r$ -reconstruction if for all $\mathcal{A} \subseteq \lbrack n\rbrack$ with $|\mathcal{A}| \geq r$ , $\mathcal{A}$ is a reconstructing set.

Similarly, a subset of parties $\mathcal{A} \subseteq \lbrack n\rbrack$ is a privacy set if for any sharing $c \in C$ , the shares $c_{\mathcal{A}}$ reveal no information about the secret. This is taken in the information-theoretic sense: given knowledge of a prior distribution of the secret, learning $c_{\mathcal{A}}$ does not change the posterior distribution. As $\pi_{\mathcal{A}}$ and $\psi$ are both linear, it is sufficient to require that $c_{\mathcal{A}}$ is compatible with every value of $z$ .

Definition 3. (Privacy) A set $\mathcal{A} \subseteq \lbrack n\rbrack$ is a privacy set if the product morphism $\left( \pi_{\mathcal{A}},\psi \right):C \rightarrow \pi_{\mathcal{A}(C)} \times Z$ is surjective.

We say that $\mathcal{S}$ has $t$ -privacy if for all $\mathcal{A} \subseteq \lbrack n\rbrack$ with $|\mathcal{A}| \leq t$ , $\mathcal{A}$ is a privacy set.

We also introduce a notion of efficiency, the rate

Definition 4. (Rate) Given a LSSS with secret space $Z$ and share space $U$ , its rate is $\rho = \frac{\log|Z|}{n \cdot \log|U|}.$ The inverse $\rho^{- 1}$ is known as the information ratio.

Intuitively, the information ratio is the total storage size of the secret shares as a multiple of the size of the secrets. It is bounded by requirements on reconstruction and privacy. Notably there are schemes with $|Z| > |U|$ , e.g. vector secret sharing.

Example. (Additive Sharing) For any ring $R$ (in fact, any group) and $n > 0$ , there exist an additive sharing $R$ -LSSS with $n$ -reconstruction and $(n - 1)$ -privacy given by $Z = U = R$ and $\psi(\mathbf{u}) = \sum_{i}u_{i}$ .

Example. (Shamir Sharing) Consider

Lemma 5. (Embedding) Given an $R$ -LSSS with secret space $Z$ and an injective linear map $p:Y \rightarrow Z$ , there exists an $R$ -LSSS with secret space $Y$ .

Proof. Since $p^{- 1}$ is surjective the composition $p^{- 1} \circ \psi$ is a surjective homomorphism which forms the reconstruction map for an $R$ -LSSS with secret space $Y$ , share space $U$ and code space $C$ .

Lemma 6. (Concatenation) Given $R$ -LSSSs with secret spaces $Y,Z$ , we can construct an $R$ -LSSS with secret space $Y \times Z$ .

Proof. Follows from taking the direct product of $Z$ , $U$ , $C$ and $\psi$ .

From this lemma follows that given an $R$ -LSSSs for $Z$ , we can construct an LSSS with secret space $Z^{n}$ for any $n$ .

Secret Computation

Local Realizability

In MPC we not want to share secrets, we also want to do computations on them and obtain a secret sharing of the result. Sometimes this can be done locally, by doing operations on the shares directly without communicating with the other parties.

Definition 7. (Local Realizability) Given sharing schemes $\left( Z_{i},C_{i},\psi_{i} \right)$ and a map $f:Z_{1} \times \cdots \times Z_{k} \rightarrow Z$ we say that $f$ is locally realizable if there exists a target scheme $(Z,C,\psi)$ and a map $g:U_{1} \times \cdots \times U_{k} \rightarrow U$ such that, for all $c_{i} \in C_{i}$ we have $\psi\left( \hat{g}(c_{1},\ldots,c_{k}) \right) = f\left( \psi_{1}\left( c_{1} \right),\ldots,\psi_{k\left( c_{k} \right)} \right)$ , where $\hat{g}$ is $g$ applied coordinatewise.

Lemma 8. A realizable map necessarily degrades the code proportional to the polynomial degree of the map.

Lemma 9. (Affine is free) Any affine map $f:$

Example. (Replicated Sharing) Given a ring $R$ , there exists a 3-party $R$ -LSSS with $2$ -reconstruction and $1$ -privacy given by $Z = R$ , $U = R^{2}$ , and

$\begin{aligned} C & = \operatorname{span}\left\{ \begin{pmatrix} (1,0) \\ (0,0) \\ (0,1) \end{pmatrix},\begin{pmatrix} (0,1) \\ (1,0) \\ (0,0) \end{pmatrix},\begin{pmatrix} (0,0) \\ (0,1) \\ (1,0) \end{pmatrix} \right\} \\ \psi(a,b,c) & = a_{0} + b_{0} + c_{0.} \end{aligned}$

Put differently, to share a secret $z$ , create additive shares $z_{0},z_{1},z_{2}$ such that $z = z_{0} + z_{1} + z_{2}$ , and then give each party two shares: party one receives $\left( z_{0},z_{1} \right)$ , party two receives $\left( z_{1},z_{2} \right)$ and party three $\left( z_{2},z_{0} \right)$ . Given such a sharing of two secrets $a$ , $b$ each party

Given sharings of two secrets

$x = x_{0} + x_{1} + x_{2}\quad\text{ and }\quad y = y_{0} + y_{1} + y_{2},$

each party can locally compute one additive share of the product:

$\begin{aligned} p_{0} & = x_{0}y_{0} + x_{0}y_{1} + x_{1}y_{0}, \\ p_{1} & = x_{1}y_{1} + x_{1}y_{2} + x_{2}y_{1}, \\ p_{2} & = x_{2}y_{2} + x_{2}y_{0} + x_{0}y_{2.} \end{aligned}$

These satisfy

$p_{0} + p_{1} + p_{2} = \left( x_{0} + x_{1} + x_{2} \right)\left( y_{0} + y_{1} + y_{2} \right) = x \cdot y.$

Thus $p_{0},p_{1},p_{2}$ are additive shares of $x \cdot y$ , but

Example. (Reed–Solomon)

Preprocessing Arithmetic Circuits

Bea92 presents a protocol for evaluation an arithmetic circuits of binary addition and multiplication gates by using preprocessed randomness. In CWB18 this is generalized to arbitrary multivariate polynomial gates.

Definition 10. (Beaver Tuples) Let $Z_{1},\ldots,Z_{k},Z$ be $R$ -algebras. Given a polynomial map $f:Z_{1} \times \cdots \times Z_{k} \rightarrow Z$ , construct a polynomial expansion of $f$ around an arbitrary point $r$ as

$f(r + \delta) = \sum_{\alpha}g_{\alpha}(r) \cdot \delta^{\alpha}$

where $r$ and $\delta$ are vectors, $\alpha \in {\mathbb{N}}^{k}$ sums over all the monomial degrees and $\delta^{\alpha}$ is the monomial $\prod_{i}\delta_{i}^{\alpha_{i}}$ .

Given a schemes $\mathcal{A}$ , $\mathcal{B}$ , and a random $r\overset{\ \$}{\leftarrow}Z_{1} \times \cdots \times Z_{k}$ , then $\left( \lbrack r\rbrack_{\mathcal{A}},\left( \left\lbrack g_{\alpha}(r) \right\rbrack_{\mathcal{B}} \right)_{\alpha} \right)$ is a Beaver tuple for $f$ .

Beaver Tuples can be used to evaluate arbitrary maps.

Protocol 11. (Beaver Evaluation) Given $\lbrack z\rbrack_{\mathcal{A}}$ and a map $f$ the parties want to compute $\left\lbrack f(z) \right\rbrack_{\mathcal{B}}$ .

A dealer provides a Beaver tuple $\left( \lbrack r\rbrack_{\mathcal{A}},\left( \left\lbrack g_{\alpha}(r) \right\rbrack_{\mathcal{B}} \right)_{\alpha} \right)$ .
The parties compute the affine $\lbrack\delta\rbrack_{\mathcal{A}} = \lbrack z\rbrack_{\mathcal{A}} - \lbrack r\rbrack_{\mathcal{A}}$ locally.
The parties exchange shares and reveal $\delta$ to eachother.
The parties compute the affine $\left\lbrack f(r + \delta) \right\rbrack_{\mathcal{B}} = \sum_{\alpha}\left\lbrack g_{\alpha}(r) \right\rbrack_{\mathcal{B}} \cdot \delta^{\alpha}$ locally.

We now have $\left\lbrack f(r + \delta) \right\rbrack_{\mathcal{B}} = \left\lbrack f(x) \right\rbrack_{\mathcal{B}}$ .

Note that step one does not depend on $\lbrack z\rbrack_{\mathcal{A}}$ and can be done as a preprocessing step if $f$ is fixed. If the same inputs are used in multiple evaluations, a practical optimization is to re-use

The protocol preserves privacy because $\delta$ by itself does not reveal anything about $z$ . This follows from the that fact $(\delta,r)$ is a valid additive secret sharing of $z$ and $r$ is never revealed.

A special case of this is a simple folklore protocol to switch schemes and convert $\lbrack z\rbrack_{\mathcal{A}}$ to $\lbrack z\rbrack_{\mathcal{B}}$ :

Example. (Scheme conversion by masking) Consider $f(x) = x$ , then $f(r + \delta) = r \cdot \delta^{0} + 1 \cdot \delta^{1}$ so $g_{0}(r) = r$ and $g_{1}(x) = 1$ . Given $r\overset{\ \$}{\leftarrow}R$ the Beaver tuple, leaving out constants, is $\left( \lbrack r\rbrack_{\mathcal{A}},\lbrack r\rbrack_{\mathcal{B}} \right)$ .

Given shares $\lbrack z\rbrack_{\mathcal{A}}$ and a tuple, the parties compute $\lbrack\delta\rbrack_{\mathcal{A}} = \lbrack z\rbrack_{\mathcal{A}} - \lbrack r\rbrack_{\mathcal{A}}$ and reveal $\delta$ . Each party then computes $\lbrack z\rbrack_{\mathcal{B}} = \lbrack r\rbrack_{\mathcal{B}} + \delta \cdot \lbrack 1\rbrack_{\mathcal{B}}$ .

Example. (Addition?) Consider $f\left( x_{0},x_{1} \right) = x_{0} + x_{1}$ , then $f(r + \delta) = \left( r_{0} + r_{1} \right) \cdot \delta_{0}^{0}\delta_{1}^{0} + 1 \cdot \delta_{0}^{1}\delta_{1}^{0} + 1 \cdot \delta_{0}^{0}\delta_{1}^{1}$ so $g_{00}(r) = r_{0} + r_{1}$ , $g_{10}(r) = g_{01}(r) = 1$ , and $g_{00}(r) = 0$ . Given $r\overset{\ \$}{\leftarrow}R^{2}$ the Beaver tuple, leaving out constants, is $\left( \left\lbrack r_{0} \right\rbrack,\left\lbrack r_{1} \right\rbrack,\left\lbrack r_{0} + r_{1} \right\rbrack \right)$ .

But this is suboptimal as the parties can just compute this affine local! What optimization are we missing?

Another special case is for multiplication, which is how it was originally presented in Bea92:

Example. (Beaver Multiplication) Consider $f\left( x_{0},x_{1} \right) = x_{0} \cdot x_{1}$ and construct

$\begin{aligned} f\left( r_{0} + \delta_{0},r_{1} + \delta_{1} \right) & = \left( r_{0} + \delta_{0} \right) \cdot \left( r_{1} + \delta_{1} \right) \\ & = \left( r_{0} \cdot r_{1} \right) \cdot \delta_{0}^{0}\delta_{1}^{0} + r_{0} \cdot \delta_{0}^{0}\delta_{1}^{1} + r_{1} \cdot \delta_{0}^{1}\delta_{1}^{0} + 1 \cdot \delta_{0}^{1}\delta_{1}^{1}. \end{aligned}$

From this we find the coefficient polynomials

$\begin{aligned} g_{00}(r) & = r_{0} \cdot x_{1} & g_{01}(r) & = r_{0} \\ g_{10}(r) & = r_{1} & g_{11}(r) & = 1. \end{aligned}$

Take $\mathcal{A} = \mathcal{B}$ for simplicity. After removing duplicate and constant values, the resulting Beaver tuple is $\left( \left\lbrack r_{0} \right\rbrack,\left\lbrack r_{1} \right\rbrack,\left\lbrack r_{0} \cdot r_{1} \right\rbrack \right)$ .

Given shares of $\left\lbrack z_{0} \right\rbrack,\left\lbrack z_{1} \right\rbrack$ , using the protocol above the parties reveal $\delta_{i} = z_{i} - r_{i}$ and compute

$\left\lbrack z_{0} \cdot z_{1} \right\rbrack = \left\lbrack r_{0} \cdot r_{1} \right\rbrack + \left\lbrack r_{0} \right\rbrack \cdot \delta_{1} + \left\lbrack r_{1} \right\rbrack \cdot \delta_{0} + \delta_{0} \cdot \delta_{1.}$

In Rei⁺24 it is optimized further by arranging such that certain intermediate values and computations can be done entirely in cleartext. The key concept to make this happen is the notion of a randomized encoding with an additive component:

Definition 12. (Randomized Encoding) Let $f:X \rightarrow Y$ be a map between $R$ -modules $X,Y$ . A randomized encoding of $f$ consists of

a randomness space $A = R^{t}$ for some $t \geq 0$ ,
an encoding map $f_{\text{enc}}:X \times A \rightarrow R^{k}$ for some $k \geq 0$ ,
and a reconstruction map $f_{\text{rec}}:R^{k} \rightarrow Y$

such that for all inputs $x \in X$ and random $a\overset{\ \$}{\leftarrow}A$ we have $f_{\text{rec}}\left( f_{\text{enc}}(x,a) \right) = f(x).$

The encoding is private if $f_{\text{enc}}(x,a)$ reveals no more about $x$ than $f(x)$ itself. A component of $y = f_{\text{enc}}(x,a)$ is additive if $f_{\text{rec}}\left( y_{0},y_{1},\ldots \right) = y_{0} + f_{\text{rec}}\left( 0,y_{1},\ldots \right)$ .

Without elaborating how this is used (see Rei⁺24 for details), here is a comparison with Beaver circtuits:

Example. (16-way product) Suppose the parties have $\left\lbrack x_{1} \right\rbrack,\ldots,\left\lbrack x_{16} \right\rbrack$ and want to compute the product $x_{1} \cdot \cdots \cdot x_{16}$ . We can achieve this using a single 16-variate polynomial, a 4-ary tree of 4-ariate polynomials, and a binary tree of binary polynomials.

Construction	Rounds	Preprocessing size	Opened values
2-way Beaver	4	45	30
4-way Beaver	2	75	20
16-way Beaver	1	65535	16
Polytuples	1	149	41

References

CCXY18 I. Cascudo, R. Cramer, C. Xing, and C. Yuan. 2018. “Amortized complexity of information-theoretically secure MPC revisited.” Cryptology ePrint Archive, Paper 2018/429. https://eprint.iacr.org/2018/429

ACD⁺20 M. Abspoel, R. Cramer, I. Damgård, D. Escudero, M. Rambaud, C. Xing, and C. Yuan. 2020. “Asymptotically good multiplicative LSSS over galois rings and applications to MPC over $\mathbb{Z}/p^k\mathbb{Z}$.” Cryptology ePrint Archive, Paper 2020/1256. https://eprint.iacr.org/2020/1256

Bea92 D. Beaver. 1992. “Efficient multiparty protocols using circuit randomization.” https://doi.org/10.1007/3-540-46766-1_34

CWB18 H. Cho, D. J. Wu, and B. Berger. 2018. “Secure genome-wide association analysis using multiparty computation.” https://doi.org/10.1038/nbt.4108

Rei⁺24 P. Reisert, M. Rivinius, T. Krips, S. Hasler, and R. Küsters. 2024. “Actively secure polynomial evaluation from shared polynomial encodings.” https://eprint.iacr.org/2024/1435