# Multi-party Computation notes.

$$\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\box#1{\delim[{#1}]} \gdef\floor#1{\delim\lfloor{#1}\rfloor} \gdef\bbox#1{\delim{\llbracket}{#1}{\rrbracket}} \gdef\set#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}}$$

A Secure Multi-Party Computation Scheme (MPC) allows a set of parties $\set P$ to compute a function over inputs while keeping the inputs secret.

MPC is a family of related protocols, with slightly different security guarantees. You can compare this to proving protocols being zero-knowledge or not, except in MPC there are more dimensions.

## Properties of MPC schemes

• Arithmetization

• Boolean. Including bitvectors.
• Ring. Often $ℤ_{2^k}$ for $k∈\{8,16,32,64\}$ to use computer native integers.
• Field.
• Mixed. Efficient switching between different schemes.
• Network

• Synchronous: Any message not arriving on time means the sender is corrupt.
• Asynchronous: Eventually delivered. Messages between parties can get arbitrarily delayed and arrive out of order.
• Corruption capacity.

• Threshold: The protocol provides it's guarantees as long as $≤ t$ parties are corrupt.
• Non-threshold: The protocol is robust against specific subsets of parties colluding. (An adversary structure).
• Note: Threshold is a special case where the adversary structure contains all subsets of $\set P$ of size $≤ t$.
• Corruption power:

• Cryptographically secure. Security relies on cryptographic hard problems.
• Unconditional secure. Security derives from information-theoretic arguments. (Note: This assumes secure communication channels between parties.)
• Statistically secure. There is a non-zero error probability.
• Perfectly secure. The protocol is always secure.
• Input privacy:

• Nothing about the inputs can be learned from observing the messages.
• Nothing about the inputs can be learned from the state of a single party?
• Nothing about the inputs can be learned from protocol deviation by a single party?
• Correctness:

• Colluding parties can affect the outcome. (In what way?)
• Output manipulation is detected and the protocol will abort.
• Output manipulation is detected and corrected, the output will always be correct.

Semi-honest. All parties follow the protocol correctly but are curious. This means that while they will not deviate from the defined steps of the protocol, they may try to learn additional information from the data they observe during the execution of the protocol.

Malicious-security.

Question: Does this mean a single malicious actor can affect the outcome undetected, but never learn the secret?

Semi-honest three party computation.

https://en.wikipedia.org/wiki/Secure_multi-party_computation

I'm considering a series of MPC protocol following [AFL+16], MZ17, MR18. These are called ABY protocols as they convert between arithmetic, binary and Yao representations. I will skip the Yao representation as it is not necessary for completeness and only adds better performance for

## Linear Secret Sharing Schemes

A Secret Sharing Scheme (SSS) is a set of two protocols:

Distribution
Reconstruction
In Distribution, a dealer takes a secret s and distribute it to n parties. In Reconstruction, a subset of the parties reveal their secret shares in order to learn the secret s. It is guaranteed that if disallowed sets of parties will not be able to learn anything about the original secret.

A Secret Sharing Scheme is associated to an Access Structure, this is the set of sets of parties which can recover the secret (or equivalently the set of sets of parties which cannot access the secret). Access structures are always monotonically increasing, i.e. if you add a party to a set which can access the secret then the bigger set can also access the secret. There are a number of different methods to perform secret sharing.

In multi-party computation we are usually interested in so-called Linear Secret Sharing Schemes (LSSSs) as they allow parties to locally compute linear functions of their secrets for free.

SHAMIR SECRET SHARING
In Shamir Secret Sharing the number of parties which can be adversarial t is a threshold of the total number of parties n. In multi-party computation protocols one usually has either t<n/2 or t<n/3. Shamir is a form of LSSS, and usually the one used to introduce concepts in introductory courses.

REPLICATED SECRET SHARING
Another popular LSSS scheme is called Replicated Secret Sharing, this is less efficient (usually) than Shamir Sharing for threshold structures. However, with Replicated Secret Sharing one is able to represent any access structure.

FULL THRESHOLD SECRET SHARING
The simplest secret sharing scheme is one in which all parties need to come together to recover the secret. This form of sharing is the basis of almost all multi-party computation protocols in the dishonest majority setting. In this secret sharing each party P_i has a value x_i with the actual secret being x = x_1 + ... + x_n.

https://wiki.mpcalliance.org/Shamir%20Secret%20Sharing.html

Note: Creating a random zero alsoa useful operation.

In an LSSS we have encoded $[x]$ such that we can locally compute $[a] + [b]$ and $c⋅[a]$.

Affine transformation:

Or generally we can compute any affine transformation of the secrets locally $\mat A⋅[\vec x]+\vec b$.

Multiplication:

Then we can do a round of multiplications as an affine bilinear algorithm:

$$\mat C ⋅ \left( \left(\mat A⋅[\vec x]+\vec a\right) ∘ \left(\mat B⋅[\vec x]+\vec b\right)\right) + \vec c$$

In the replicated scheme, multiplication converts from replicated to un-replicated form.

This can be un-done by replicating the results again.

The inverse transform, from replicated to plain shares is trivially forgetting shares.

## Multiplication

Assume the

### Shamir

Given a group $𝔾$ and $n$ shares $\vec x ∈ 𝔾^n$, we can define a linear encoding such that for values $\vec v$, randomness $\vec r$ we have:

$$\begin{bmatrix} \mat M_v \\ \mat M_r \\ \mat M_c \end{bmatrix} ⋅ \begin{bmatrix} \vec x\\ 1 \end{bmatrix} = \begin{bmatrix} \vec v \\ \vec r \\ \vec 0 \end{bmatrix}$$

Where $\mat M$ is matrix with linearly independent rows.

For example the scheme below is

$$\begin{bmatrix} 1 & 1 & 1 & 0 \\ \hline 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ \end{bmatrix} ⋅ \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ 1 \end{bmatrix} = \begin{bmatrix} v \\ r_0 \\ r_1 \end{bmatrix}$$

TODO: This $\mat M_r$ matrix is arbitrary, it can be any $2 × 3$ matrix.

## Arithmetic encoding

Given a ring $ℤ_{2^k}$ and $x∈ℤ_{2^k}$.v

$$⟦x⟧ = (x_0, x_1, x_2) \text{ s.t. } x = x_0 + x_1 + x_2$$

Each paricipant receives two shares $(x_i, x_{i+1})$.

Note that each value has $2^{2⋅k}$ valid encodings.

Zero. A share for zero can be generated by producing three random numbers $r_i$ and computing

$$⟦0⟧ = (r_0 - r_1, r_1 - r_2, r_2 - r_0)$$

This can be done locally if each participant has a pseudo-random number generator for $r_i$ and $r_{i+1}$, so at least 3 participants are required for security.

Encoding. To encode a cleartext value $n$

$$⟦n⟧ = (n, 0, 0)$$

Idea: Since $3^{-1}$ always exists in $ℤ_{2^k}$ we could do $(n,n,n)/3$.

Mixed addition. Adding a cleartext value $a ∈ ℤ_{2^k}$ can be done by adding $(x_0 + a, x_1, x_2)$.

Mixed multiplication. Multiplying by a cleartext value $a ∈ ℤ_{2^k}$ can be done by adding $(a⋅x_0, b⋅x_1, c⋅x_2)$.

Addition. The sum of two shares can be computed locally

$$⟦x⟧ + ⟦y⟧ = (x_0 + y_0, x_1 + y_1, x_2 + y_2)$$

Multiplication. For multiplication $⟦z⟧ = ⟦x⟧ ⋅ ⟦y⟧$ we need to find a $(z_0, z_1, z_2)$ such that

\begin{aligned} z_0 + z_1 + z_2 &= \p{x_0 + x_1 + x_2} ⋅ \p{y_0 + y_1 + y_2} \\ &= x_0 ⋅ y_0 + x_1 ⋅ y_0 + x_2 ⋅ y_0 \\ &+ x_0 ⋅ y_1 + x_1 ⋅ y_1 + x_2 ⋅ y_1 \\ &+ x_0 ⋅ y_2 + x_1 ⋅ y_2 + x_2 ⋅ y_2 \\ \end{aligned}

the terms can be grouped such that each party can compute one share $z_i$ locally given $x_i, x_{i+1}, y_i, y_{i+1}$:

\begin{aligned} z_0 &= x_0 ⋅ y_0 + x_0 ⋅ y_1 + x_1 ⋅ y_0 \\ z_1 &= x_1 ⋅ y_1 + x_1 ⋅ y_2 + x_2 ⋅ y_1 \\ z_2 &= x_2 ⋅ y_2 + x_2 ⋅ y_0 + x_0 ⋅ y_2 \end{aligned}

As a potential optimization, we can also trade multiplications for additions using:

\begin{aligned} z_0 &= \p{x_0 + x_1} ⋅ \p{y_0 + y_1} - x_1 ⋅ y_1 \\ z_1 &= \p{x_1 + x_2} ⋅ \p{y_1 + y_2} - x_2 ⋅ y_2 \\ z_2 &= \p{x_2 + x_0} ⋅ \p{y_2 + y_0} - x_0 ⋅ y_0 \\ \end{aligned}

Each node $i$ can now communicate share $i$ to node $i-1$ so that all nodes have a full complement of shares again. Before we do this we add a freshly generated share of zero to scramble the values and make sure node $i-1$ learns nothing about share $i+1$.

Multplication For a two-party setting from B91 as in PSSY20. First the parties generate random shares $a, b$ and $c = a⋅b$, then

$$z_i &= (x_i + a_i)⋅(y_i + b_i) - (x_i + a_i)⋅b_i - a_i⋅(y_i + b_i) + c_i$$

Two party multiply?

\begin{aligned} z_0 + z_1 &= \p{x_0 + x_1} ⋅ \p{y_0 + y_1} \\ &= x_0 ⋅ y_0 + x_1 ⋅ y_0 \\ &+ x_0 ⋅ y_1 + x_1 ⋅ y_1 \\ \end{aligned}

### Generalization

This multiplication method can potentially work for different number parties $n$ and collusion resistance $k$. The above is presented using $3$ shares, $3$ parties and a collusion resistance of $1$ (i.e., $≥ 2$ parties need to collude to steal the secret). We can represent this scheme by share allocation as

$$\ps{\ps{0, 1}, \ps{1,2}, \ps{2,0}}$$

We can also design a $10$ party scheme with collusion resistance of $2$ using $5$ shares:

$$\ps{ \ps{0, 1}, \ps{0, 2}, \ps{0, 3}, \ps{0, 4}, \ps{1, 2}, \ps{1, 3}, \ps{1, 4}, \ps{2, 3}, \ps{2, 4}, \ps{3, 4} }$$

Question: What other scemes are possible? I.e. can we create allocations of shares such that no union of $k$ shares contains all shares, but each pair of shares occurs in at least one allocation.

Question: Can we design a $9$ node scheme with collusion resistance of $3$ using $9$ shares by applying the 3-share scheme recursively? Or does the top level re-sharing for multiplication leak too much?

### Inversion

Question: Can we do inversion using Hensel lifting in $\log_2 k$ rounds?

$$y' = y ⋅ \p{2 - x ⋅ y}$$

Computed in $ℤ_2 ⊂ ℤ_{2^2} ⊂ ℤ_{2^4} ⊂ ℤ_{2^8} ⊂ ⋯ ⊂ ℤ_{2^k}$, so round complexity $\log_2 k$ but communication complexity only $2⋅k$.

### Bit shift right

We want to compute

https://github.com/KaTeX/KaTeX/issues/3561

$$\left\llbracket x \right\rrbracket$$

### Binary encoding

Use the above arithmetic procedure to create $ℤ_{2^1} = 𝔽_2$. Now create a vector of $k$ such elements $𝔽_2^k$ to create a $k$-bit bitvector. We can apply the arithmetic addition and multiplication operations of $𝔽_2$ elementwise to the vector to construct xor and and operations, denoted with $⊕$ and $∧$ respectively. These elementwise operation happen in parallel such that, e.g. $x = x_0 ⊕ x_1 ⊕_2$ and the shares of $z = x ∧ y$ are computed as

\begin{aligned} z_0 &= (x_0 ∧ y_0) ⊕ (x_0 ∧ y_1) ⊕ (x_1 ∧ y_0) \\ z_1 &= (x_1 ∧ y_1) ⊕ (x_1 ∧ y_2) ⊕ (x_2 ∧ y_1) \\ z_2 &= (x_2 ∧ y_2) ⊕ (x_2 ∧ y_0) ⊕ (x_0 ∧ y_2) \end{aligned}

The communication complexity is exactly the same as due to parallelization the same number of rounds is required and the size of $ℤ_{2^k}$ is the same as $𝔽_2^k$.

Note that any cleartext permutation of the vector indices can be applied locally.

Note that negation, $¬$, is the same as xoring with the all-ones vector, and other bolean operations can be constructed from $¬, ⊕, ∧$.

TODO: This applies to any kind of vectorization.

## Conversion

### Projection

i.e. arithmetic to binary.

Generically we can trivially convert from $ℤ_{2^k}$ to $ℤ_{2^h}$ as long as $h ≤ k$. Taking $\box{a}_b$ to mean $a$ modulo $b$.

$$z = \box{\sum_i x_i}_b = \sum_i \box{x_i}_b$$

### Lifting

i.e. binary to arithmetic

This is more challenging as we need to account for wraparound.

Question: Is there some polynomial we can construct and use Hensel lifting on?

### Two's complement encoding

Given $\mathrm{bits}: ℤ_{2^k} → 𝔽_2^k$ the function mapping an number in $ℤ_{2^k}$ to a bitvector in $𝔽_2^k$ representing that number in two's complement.

Given arithemtic shares $⟦x⟧ = (x_1, x_2, x_3)$ we can compute the two's complement encoding of each share locally as

\begin{aligned} ⟦\mathrm{bits}(x_0)⟧^{\mathsf B} &= (\mathrm{bits}(x_1),0,0) \\ ⟦\mathrm{bits}(x_1)⟧^{\mathsf B} &= (0, \mathrm{bits}(x_1),0) \\ ⟦\mathrm{bits}(x_2)⟧^{\mathsf B} &= (0, 0, \mathrm{bits}(x_2)) \end{aligned}

These can then be (locally) randomized by adding a random $r ∈ 𝔽_2^k$.

To finish constructing $⟦\mathrm{bits}(x)⟧$ we need to sum these shares. But this is an arithmetic sum that we need to execute over bitvectors in twos complement repesentation. This can be done using any kind of adder circuit. Minimal depth circuits are preffered to reduce the round complexity.

Note that two's complement is only one method of encoding and others can be used as long as the addition circuit is modified accordingly.

Q: Do encodings other than two's complement have better complexity for the adder circuit? How would Gray code addition work?

## References

• B91 Donald Beaver (91). Efficient Multiparty Protocols Using Circuit Randomization.
• MRZ15 Payman Mohassel, Mike Rosulek, and Ye Zhang (2015). Fast and Secure Three-party Computation: The Garbled Circuit Approach.
• AFL⁺16 Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara (2016) High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority.
• MZ17 Payman Mohassel and Yupeng Zhang (2017). SecureML: A System for Scalable Privacy-Preserving Machine Learning.
• MR18 Payman Mohassel and Peter Rindal (2018). ABY3: A Mixed Protocol Framework for Machine Learning.
• CRS19 Harsh Chaudhari, Rahul Rachuri, and Ajith Suresh (2019). Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning.
• BCPS19 Megha Byali, Harsh Chaudhari, Arpita Patra, and Ajith Suresh (2019). FLASH: Fast and Robust Framework for Privacy-preserving Machine Learning.
• PS20 Arpita Patra and Ajith Suresh (2020). BLAZE: Blazing Fast Privacy-Preserving Machine Learning.
• PSSY20 Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame (2020). ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation.

Books: https://www.mpcalliance.org/learn

https://securecomputation.org/docs/pragmaticmpc.pdf https://www.cs.virginia.edu/~evans/pragmaticmpc/pragmaticmpc.pdf

https://ebooks.iospress.nl/volume/applications-of-secure-multiparty-computation

https://www.zellic.io/blog/mpc-from-scratch/

https://github.com/nillion-oss/nillion-oss.github.io/blob/main/sum-of-products-lsss-non-interactive.pdf

https://wiki.mpcalliance.org/protocols.html

Making robust against miscomputation:

https://eprint.iacr.org/2020/1330.pdf https://eprint.iacr.org/2020/592.pdf https://eprint.iacr.org/2023/1744.pdf

https://medium.com/partisia-blockchain/beavers-trick-e275e79839cc

https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf

https://iacr.org/archive/crypto2007/46220565/46220565.pdf

https://eprint.iacr.org/2020/134.pdf

https://eprint.iacr.org/2021/841.pdf

https://wiki.mpcalliance.org/protocols.html

https://www.zellic.io/blog/mpc-from-scratch/

https://eprint.iacr.org/2020/300

https://eprint.iacr.org/2019/131

https://eprint.iacr.org/2020/1330

Shamir multi-sharing

https://dl.acm.org/doi/pdf/10.1145/129712.129780

Remco Bloemen
Math & Engineering
https://2π.com