Multiparty 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 MultiParty 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 zeroknowledge 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.
 Nonthreshold: 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 informationtheoretic arguments. (Note: This assumes secure communication channels between parties.)
 Statistically secure. There is a nonzero 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.
Semihonest. 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.
Malicioussecurity.
Question: Does this mean a single malicious actor can affect the outcome undetected, but never learn the secret?
Semihonest three party computation.
https://en.wikipedia.org/wiki/Secure_multiparty_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 multiparty computation we are usually interested in socalled 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 multiparty 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 multiparty 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 unreplicated form.
This can be undone by replicating the results again.
The inverse transform, from replicated to plain shares is trivially forgetting shares.
Multiplication
Beaver Triples
Assume the
Replicated shares
Shamir
Additive MPC
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 pseudorandom 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 $i1$ 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 $i1$ learns nothing about share $i+1$.
Multplication For a twoparty 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 3share scheme recursively? Or does the top level resharing 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$.
https://en.wikipedia.org/wiki/Hensel's_lemma#Quadratic_lifting
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 allones 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?
Two's complement decoding
References
 B91 Donald Beaver (91). Efficient Multiparty Protocols Using Circuit Randomization.
 MRZ15 Payman Mohassel, Mike Rosulek, and Ye Zhang (2015). Fast and Secure Threeparty Computation: The Garbled Circuit Approach.
 AFL⁺16 Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara (2016) HighThroughput SemiHonest Secure ThreeParty Computation with an Honest Majority.
 MZ17 Payman Mohassel and Yupeng Zhang (2017). SecureML: A System for Scalable PrivacyPreserving 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 Privacypreserving Machine Learning.
 PS20 Arpita Patra and Ajith Suresh (2020). BLAZE: Blazing Fast PrivacyPreserving Machine Learning.
 PSSY20 Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame (2020). ABY2.0: Improved MixedProtocol Secure TwoParty 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/applicationsofsecuremultipartycomputation
https://assets.cambridge.org/97811070/43053/copyright/9781107043053_copyright_info.pdf
https://www.zellic.io/blog/mpcfromscratch/
https://github.com/nillionoss/nillionoss.github.io/blob/main/sumofproductslsssnoninteractive.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/partisiablockchain/beaverstricke275e79839cc
https://web.mit.edu/6.857/OldStuff/Fall03/ref/ShamirHowToShareASecret.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/mpcfromscratch/
https://eprint.iacr.org/2020/300
https://eprint.iacr.org/2019/131
https://eprint.iacr.org/2020/1330
Shamir multisharing
https://dl.acm.org/doi/pdf/10.1145/129712.129780