Linear Secret Sharing Schemes
$$ \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\ceil#1{\delim\lceil{#1}\rceil} \gdef\bbox#1{\delim{\llbracket}{#1}{\rrbracket}} \gdef\norm#1{\delim\|{#1}\|_{\max}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\setn#1{\mathcal{#1}} \gdef\T{\mathsf{T}} \gdef\Z{\mathrm{Z}} $$
Thank you Daniel Kales, Roman Walch and others from TACEO for many pointers and explanations.
- Derive generic construction from first principles.
- Polynomial interpretation as Shamir secret sharing.
- Multi-secrets.
- CRT interpretation.
$$ \mathsf{encode}: \mathsf{secret}^k → \mathsf{shares}^n $$
$$ \mathsf{decode}: \mathsf{secret}^k → \mathsf{shares}^n $$
An $n$-party secret sharing scheme is a pair of functions encode and decode between $n$ parties. Where an entity (not necessarily a party) with a value $a$ can encode this to secret shares $s_0, …, s_{n-1}$ and distribute these to the $n$ parties. Given (a subset of) shares, the decode procedure reconstructs the original value.
Given a ring $𝕂$, usually $ℤ_{2^k}$ or some prime field $𝔽$.
Environment: We assume perfect synchronous private communication channels between all entities. In practice this is created using end-to-end encrypted connections.
Generic construction
Todo. This is similar to the generalization to Monotone/Extended Span Programs (MSP/ESP) Feh98 JSL21. CDM00. In CFIK03 it is stated they are in 1-1 correspondence with LSSSs, like I attempting here. The CFIK03 paper seems to have a good concise overview.
In CDN15 § 6.3 this is presented (though in field version). In particular it shows that any scheme leads to some form of multiplication when parties locally pair-wise multiply there shares that they have. See GCEPs on page 167 for a general presentation.
- Q. How does this generalize to rings?
- Q. How does this generalize to packed secrets?
- Q. How does this generalize to mixed encoding? (i.e. inputs a, b are in different schemes).
Q. What do adversary structures like $\mathcal Q_2$ mean intuitively?
- KW93 M. Karchmer, A. Wigderson (1993). On span programs.
- Feh98 Serge Fehr (1998). Span programs over rings and how to share a secret from a module.
- CDM00 Ronald Cramer, Ivan Damgård, Ueli Maurer (2000). General Secure Multi-party Computation from any Linear Secret-Sharing Scheme.
- CFIK03 Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz (2003). Efficient Multi-party Computation over Rings.
Given a commutative ring $𝕂$ such a $ℤ/qℤ$. An $n$-party affine $s$-multi secret sharing scheme over $𝕂$ has a cleartext values in $𝕂^s$ and secrets in the set of tuples $\setn S = \prod_{i∈[0,n)} \setn S_i$ where $\setn S_i$ is the set of possible shares of party $i$. There is a randomized injective protocol $\mathsf{encode}_{r}: 𝕂^s → \setn S$ and a surjective function $\mathsf{decode}: \setn S → 𝕂^s$. Given $a ∈ 𝕂^s$, denote with $[a]$ an arbitrary element of $\setn S$ such that $\mathsf{decode}([a]) = a$.
The set of secrets $\setn S$ has operations to add two secrets and multiply secrets by an element of $𝕂^s$ such that $\setn S$ forms a $𝕂^s$-module. It is also has an affine action of $𝕂^s$ (i.e. scalar addition).
Assume (argument TBD) that $\setn S$ is a free module. This means it has a basis and can be represented as $𝕂^k$ for some $k$. Let's also assume $k=n$, $\setn S = 𝕂^n$ and $\setn S_i = 𝕂$. Given a basis on $\setn S$ we can represent secrets $[a] ∈ \setn S$ as elements in $𝕂^n$.
To do. These assumptions are overly restrictive and exclude replicated schemes where $\setn S_i = 𝕂^k$ for some $k$.
The $\mathsf{decode}$ function is a surjective linear map as for every element in $\setn S$ there is a pre-image and $\mathsf{decode}([a] + [b]) = a+b$ and $\mathsf{decode}(c ⋅ [a]) = c⋅ a$ for any $a,b,c ∈ 𝕂$. In the basis it is represented by a full-rank decoding matrix $\mat D ∈ 𝕂^{s × n}.$ such that
$$ a = \mathsf{decode}([a]) = \mat D ⋅ [a] $$
The null-space $\ker \mat D$ has dimension $n - s$. This null-space allows for multiple valid encodings of the same secret and hence provides the randomness required for secrecy. It is however useful set aside a subspace of dimension $n_c$ to be held zero, leaving dimension $n_r = n - s - n_c$. Picking a basis for the random and zero subspaces results in a matrix
To do. Even if $𝕂^n$ has a basis this does not guarantee $\ker \mat D$ has a basis. In fact, this appears not the case for additive sharing in $ℤ_{2^k}$.
$$ \begin{bmatrix} a \\ r \\ 0 \end{bmatrix} = \begin{bmatrix} \mat D \\ \mat R \\ \mat C \end{bmatrix} ⋅ [a] $$
where $\mat R ∈ 𝕂^{n_r × n}, \mat C ∈ 𝕂^{n_c × n}$. We can now specify the $\mathsf{encode}_r$ operation as solving the above equation for some $a$ and $r ∈ 𝕂^{n_r}$. The scheme is fully specified by $(𝕂, \mat D, \mat R, \mat C)$.
Q. What are the conditions for this to be solvable? For example the additive scheme with an even number of parties is not invertable in $ℤ_{2^k}$.
Note. It is not strictly necessary that randomness and constants are linearly separable, but this is what all protocols seem to do.
To do. Derive the threshold the scheme provides, and any mallicious resistance.
Q. There should be some requirement that the entries in $\mat D$ are all non-zero, or else there is degeneracy and fewer shares are required to learn about some secret. One way to approach define this might be to insist that each share value can set change any secret value. A similar argument applies to $\mat R$. Q. Does it matter if a combination of rows or columns has zeros? Q What are sufficient and minimal constraints of $\mat D, \mat R, \mat C$ to make schemes unconditionally secure with some threshold?
Q. Given an $n$-party scheme with $n$ shares we can recursively deal the shares with a $m$-party scheme to obtain $n⋅m$ shares. What are the properties of such recursive schemes? What sort of isomorphisms follow from it?
Concrete schemes
Additive sharing
A simple protocol to share a single secret $a$ among $n$ parties is to create $n$ random values $x_0, x_1, …, x_{n-1}$ such that $a = x_0 + x_1 + ⋯ + x_{n-1}$. This can be represented using the decoding matrix
$$ \mat D = \begin{bmatrix} 1 & 1 & 1 & ⋯ & 1 \end{bmatrix} $$
One basis for $\ker \mat D$ is the $(n-1) × n$ matrix:
$$ \mat R = \begin{bmatrix} 1 & 0 & 0 & ⋯ & -1 \\ 0 & 1 & 0 & ⋯ & -1 \\ 0 & 0 & 1 & ⋯ & -1 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & ⋯ & -1 \\ \end{bmatrix} $$
Q. In $ℤ_{2^{16}}$ there is no $\mat D^+$ for even values of $n$. In those cases it is not possible to construct an encoding that has $\mat R ⋅ \vec y = \vec 0$. Does this imply there is less entropy? How do we define the encode operation?
Shamir secret sharing
First introduced in Sha79, applied to MPC in BGW88, and generalized to multi-secrets in FY92. See also AL11 for a detailed description. Given a ring $𝕂$, the protocol works implicitly with polynomials in $𝕂[X]$. The protocol is specified by a set of secret and share evaluation points $\vec s, \vec x ⊂ 𝕂$ and such that all evaluation points are distinct. The multi-secret is represented as a polynomial $P ∈ 𝕂[X]$ such that each party's share $y_i = P(x_i)$ and the secrets are stored as $a_i = P()$
Recall the Vandermonde matrix $\mat V_{\vec x}$ for an evaluation basis $\vec x$ such that if $\vec c$ are the coefficients of a polynomial $P ∈ 𝕂[X]$ then $\vec y = \mat V_{\vec x} ⋅ \vec c$ computes the evaluations such that $y_i = P(x_i)$. This can also be seen as a transformation from monomial (coefficient) basis to an evaluation basis. It is given by
$$ \mat V_{\vec x} = \begin{bmatrix} 1 & x_0 & x_0^2 & x_0^3 & ⋯ \\ 1 & x_1 & x_1^2 & x_1^3 & ⋯ \\ 1 & x_2 & x_2^2 & x_2^3 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{bmatrix} $$
Consequently $\mat V_{\vec x}^{-1}$, which always exists if $𝕂$ is a field, transforms from evaluations to coefficients. We can use this to convert from the share evaluation basis to the secret evaluation basis. This gives our decoding matrix as $\mat D = \mat V_{\vec s} ⋅ \mat V_{\vec x}^{-1}$. We can compute the entries of the decoding matrix directly using the Lagrange interpolation formula:
$$ \mat D_{ij} = \mathrm{L}_j(s_i) = \prod_{k ∈ [0,n) ∖ j} \frac{s_i - x_k}{x_j - x_k} $$
This matrix exists if each $x_i - x_j$ is invertible in $𝕂$. They are non-zero by the requirement of distinctness, so the matrix always exists when $𝕂$ is a field. Unfortunately in the computationally interesting rings $ℤ_{2^k}$ there are no solutions with more than two points $x_i$.
A particularly useful basis for $\ker \mat D$ can be constructed by selecting the high coefficients.
$$ \begin{bmatrix} \mat D \\ \hline \mat R \\ \mat C\end{bmatrix} = \begin{bmatrix} \mat V_{\vec s} \\ \hline \begin{array}{cc} 0 & I & 0 \\ 0 & 0 & I \end{array} \end{bmatrix} ⋅ \mat V_{\vec x}^{-1} $$
By setting $\vec c = \vec 0$ we can restrict the degree of $P(X)$, which is the key to BGW Multiplication. Let $n_c$ be the size of $\vec c$, then
$$ \deg P ≤ n - n_c - 1 $$
Q. Can BGW multiplication be made to work with values of $\vec c$ other than $\vec 0$?
Q. Does this generalize to confluent Vandermonde matrices? I.e. we also include evaluations over formal derivatives of $P$ in our basis. (See Hermite interpolation)
Note. It is not possible to represent the additive scheme as a Shamir scheme. Consider the $n=2$ case, the Lagrange interpolation formula for $\mat D$ implies the unsolvable system
$$ \begin{aligned} 1 &= \frac{s_0 - x_1}{x_0 - x_1} & 1 &= \frac{s_0 - x_0}{x_1 - x_0} \end{aligned} $$
Useful Protocols
Dealing secrets
To input a value $\vec a$ the dealer who has the value generates shares $\vec y$ and distributes them to the parties. Note that the dealer can be one of the parties. Some protocols use this to distribute a share $y_i$ as a secret $[y_i]$, known as shares-of-shares.
Todo. Elaborate how this works for multi-secrets. Could set only the desired values and set the others to zero. Then add the secrets.
Dealing non-secret values
If a non-secret value $a$ needs to be input the trivial solution is to broadcast it to all parties. The value can then be used as cleartext in the protocols. But if the value is only used additively (i.e. it is not multiplied by a secret), it can also be dealt as a secret $[a]$. In GSZ20 it is observed that since this value is not really secret, we can use the $n_r$ degrees of freedom in the randomness to instead fix $n_r$ of the shares $y_i$ to constant values (typically zero) already known to those parties. This saves $n_r$ messages compares to plaintext broadcast.
To do. Explicit formulas.
Revealing secrets
An efficient protocol to open or reveal a secret is to send all shares to a single entity
Randomness generation
From DN07, BH08. It starts with the observation that for a suitable matrix $l×n$ matrix $\mat M$ (such as a Vandermonde matrix), we can generate $l ≤ n$ secret random values using only $n^2 - n$ messages with malicious security against $n - l$ adversaries. The protocol proceeds as follows.
- Each party $i$ picks a random number $r_i ∈_R 𝔽$ and secret shares it, creating $[r_i]$. This requires $n^2 - n$ messages.
- Each party locally computes $[\vec r'] = \mat M ⋅ [\vec r]$.
The vector $[\vec r']$ now has $l$ independent uniform random values. A variant of this protocol has the parties simultaneously compute $[\vec r]$ and $[\vec r]_{\deg < \frac n2}$, where the latter is a low degree Shamir secret encoding in the BGW sense.
This requires $\mat M$ to be hyper-invertable, meaning that each square submatrix is invertible. In CDN15 p. 186 it is claimed this is known as a 'regular matrix' and 'maximum distance seperable (MDS) matrix' in other fields.
Q. Are 'every square submatrix is invertible' and 'every submatrix is full-rank' equivalent? See CDN15 p 186. A. Yes. The $←$ case is trivial, for the other direction pick any maximal size square submatrix in the submatrix, this is invertible and hence the non-square matrix is full rank.
Q. How to generate all MDS matrices? Vandermonde ($x_i^j$), Cauchy ($\p{x_i - x_j}^{-1}$), and circulant matrices ($x_{i+j}$) are examples. Are MDS matrices closed under matrix or elementwise multiplication? Are the other transformations we can do that perserve the MDS property?
https://en.wikipedia.org/wiki/MDS_matrix
Local randomness generation
Simply set $y_i = r_i$ to create random $[r]$. Assumes semi-honest. Needs more nuance of there are constraints.
Replicated version party $i$ has key to PRNG $i$ and $i+1$.
Converting between $𝕂$-schemes
Given two different affine schemes $\mathcal A$, $\mathcal B$ over the same ring $𝕂$. We want to convert a secret $[a]_{\mathcal A}$ to $[a]_{\mathcal B}$. In CCD88, CDN01 the double-randomness protocol is introduced that works as follows:
- The parties generate a random secret $r$ simultaneously in both schemes $[r]_{\mathcal A}$, $[r]_{\mathcal B}$.
- The parties compute $[a + r]_{\mathcal A} = [a]_{\mathcal A} + [r]_{\mathcal A}$.
- The parties open this value to reveal $\p{a + r}$.
- The parties compute $[a]_{\mathcal B} = \p{a + r} - [r]_{\mathcal B}$.
Note that the first step can be done efficiently in batch as a preprocessing step. In GSZ20 (see also Esc23) it is observed that for step 3 it is more efficient to let a single party do the decoding and use secret sharing to deal $\p{\vec a + \vec r}$.
This is notably used in CCD88, DN07 with Shamir schemes to convert from a high-degree to a low-degree polynomials.
Note. This is very generic and the schemes don't need to be MPC schemes, as long as they are affine. This allows it to be used for conversion between, say a homomorphic encryption scheme and elliptic curves.
Idea: local conversion between $𝕂$-schemes?
Assuming single-secret linear schemes $\mathcal A$ and $\mathcal B$ with decoding vectors $\vec d_{\mathcal A}$ and $\vec d_{\mathcal B}$. Given a secret $\box{a}_{\mathcal A}$ as shares $a_i$ such that $a = \sum_i a_i ⋅ d_{\mathcal A,i}$. We want to obtain shares $a_i'$ such that $a = \sum_i a_i' ⋅ d_{\mathcal B,i}$. One way to do this locally is have every party compute
$$ a_i' = \frac{d_{\mathcal A,i}}{d_{\mathcal B,i}} ⋅ a_i $$
assuming the fraction exists in $𝕂$. If it doesn't, we still have a little more freedom left to try as the order of the shares does not need to correspond between $\mathcal A$ and $\mathcal B$. We can pick a permutation of shares $σ$ and compute
$$ a_{σ(i)}' = \frac{d_{\mathcal A,i}}{d_{\mathcal B,σ(i)}} ⋅ a_i $$
this can still be computed locally.
$$ \vec a = \mat D ⋅ \vec s $$
In the general case we want to find a matrix $\mat M$ such that $\mat D_{\mathcal B} ⋅ \mat M = \mat D_{\mathcal A}$. Then
$$ \vec s = \mat D_{\mathcal A} ⋅ \vec a = \mat D_{\mathcal B} ⋅ \p{\mat M ⋅ \vec a} = \mat D_{\mathcal B} ⋅ \vec a' $$
If $\mat M$ is diagonal, or can be permuted into diagonal, then this can be done locally.
Converting between any schemes
Given sets $𝕂, 𝕃$ with secret sharing schemes $\mathcal K, \mathcal L$, and a function $f:𝕂 → 𝕃$, we want to convert $[a]_{\mathcal K}$ to $[f(a)]_{\mathcal L}$. Here is a template for a protocol:
- Each party computes $y_i' = f_i(y_i)$ and inputs $[y_i']_{\mathcal L}$.
- The parties compute $[a]_{\mathcal L} = \mathsf{decode}_{\mathcal K}([y_0']_{\mathcal L},[y_1']_{\mathcal L},…,[y_{n-1}']_{\mathcal L})$.
The key idea here is that $\mathsf{decode}_{\mathcal K}$ is computed in $\mathcal L$.
Q. When $𝕂 = 𝕃$ and the schemes are AMSSs, does $\mathsf{decode}_{\mathcal K}$ become a locally computable operation?
Converting between additive $ℤ_{2^k}$ and $ℤ_2^k$
Given $ℤ_{2^k}$ additive secret sharing scheme $\mathcal A$ and $ℤ_2^k$ scheme $\mathcal B$. Take twos-complement encoding $\mathsf{bits}_k: ℤ_{2^k} → ℤ_2^k$ and an $n$-input $k$-bit binary adder circuit $\mathsf{adder}_{nk}$.
- Each party computes $y_i' = \mathsf{bits}_k(y_i)$ and inputs $[y_i']_{\mathcal B}$.
- The parties compute $[a]_{\mathcal B} = \mathsf{adder}_{nk}([y_0']_{\mathcal B},[y_1']_{\mathcal B},…,[y_{n-1}']_{\mathcal B})$.
Converting between $ℤ_2^k$ and $ℤ_{2^k}$
Convert individual bits $[b_i]_{\mathcal A}$ and compute the sum $\sum_{i ∈ [0,k)} [b_i]_{\mathcal A}⋅2^i$.
Double randomness between rings?
Q Given secrets $[s], [r]$ over a ring $ℤ_m$. Is there a protocol to compute and reveal $\floor{\frac{s + r}{m}}$?
Given LSSSs with different moduli $m$ and $k$, and a secret $[s]_m$.
- Parties generate double randomness $[r]_m$, $[r]_k$ where $r ∈ [0,m)$.
- Parties compute $[s + r]_m$.
- Parties reveal $(s+r) \mod m$ and $q = \floor{\frac{s + r}{m}}$.
- Parties input $[s + r]_k$.
- Parties compute $[s+r]_k - [r]_k - q ⋅ m$.
Q. How much does $k$ reveal? Note that $k∈\ps{0,1}$ since $s + r < 2⋅p$, so it can not be more than one bit.
Note. The end result will be $s$ reduced modulo $q$, but this is intentional.
Intra-share matrix multiplication
BGW matrix multiplication
We would like a secure protocol for applying an arbitrary $n×n$ matrix to the secret shares:
$$ \vec y' = \mat M ⋅ \vec y $$
Each output share can depend on each input share, so it is clear some form of communication is required here. We can use secret sharing to create shares of each share, and then use the linearity of the encoding to compute each output share, and reveal this value to the party that should hold it.
One way to achieve this is to secret share each
- Each party $i$ shares it's share $y_i$ as a secret $[y_i]$, we now have $[\vec y]$.
- Each party locally computes $[\vec y'] = \mat M ⋅ [\vec y]$.
- The parties reveal $[y_i']$ to party $i$.
to do. Step 3 is unnecessary and only one round is required. See EKR18 § 3.3.
Q Does this generalize to other decoding matrices than ones constructed by Shamir?
Multiplication protocols
While affine transformations are trivially locally computed in all LSSSs, to compute arbitrary functions we also need the ability to multiply two secret values $[a]$, $[b]$ to get $[a⋅b]$.
A number of protocols exists, but they all share a perculiar feature: They first execute a round of communication to bring the parties in a specific state. This state is then consumed when do the multiplication.
Beaver multiplication triples
Bea91 presents a method to pre-compute a multiplication also known as circuit randomization. Generate random secrets $[a]$ and $[b]$ and pre-compute their product $[a⋅b]$ using any protocol. Then during the 'live' phase where the parties have $[x]$ and $[y]$ and want to compute $[x⋅y]$, they do the following:
- Compute $[x + a]$ and $[y + b]$ locally.
- Reveal $\p{x+a}$ and $\p{y+b}$ it to all parties.
- Compute $[x⋅y] = \p{x + a}⋅[y] - \p{y + b}⋅[a] + [a⋅b]$ locally.
The only live communication is revealing two secrets to all parties, which requires $2⋅(n^2 -n)$ messages. Note that the secrecy of the protocol depends on the triplet $([a], [b], [a⋅b])$ being used only once. A fresh triplet is required for each multiplication.
Q. Can this be adapted to allow for efficient dot-products like most other protocols? I.e. can we take a linear or affine combination of products with communication complexity in the size of the result? This likely also implies consuming correspondingly fewer triples.
Note. Some papers instead compute $[x⋅y] = \p{x + a}⋅\p{y + b} - \p{x + a}⋅[b] - \p{y + b}⋅[a] + [a⋅b]$ which also works, but requires one more multiplication.
Note. The dotproduct protocol in PSSY20 seems to do the sharing after computing the (intermediate) product. The intermediate is also linear, allowing them to aggregate it for efficient dot-products.
To do. It seems that in PSSY20 this is generalized by considering the state where $\p{x+a}$ is cleartext and $[a]$ secret it's own linear secret sharing scheme. They also extend it to 3,4 and $n$-way multiplication by preprocessing (many) more shares, e.g. $[a],[b],[c],[a⋅b],[b⋅c],[a⋅c],[a⋅b⋅c]$ for the 3-way case.
Q. Can any arithmetic circuit be computed one-round using LSSSs?
Replicated sharing
From BW98, Mau06, MR18. Consider an $3$-party additive secret sharing scheme such that the secret value is the sum of the shares, $a = a_0 + a_1 + a_2$, then the product of two secrets is
$$ \begin{aligned} a ⋅ b &= \p{a_0 + a_1 + a_2} ⋅ \p{b_0 + b_1 + b_2} \\ &= \phantom{+} \p{a_0 + a_1} ⋅ \p{b_0 + b_1} - a_1 ⋅ b_1 \\ &\phantom{=} + \p{a_1 + a_2} ⋅ \p{b_1 + b_2} - a_2 ⋅ b_2 \\ &\phantom{=} + \p{a_2 + a_0} ⋅ \p{b_2 + b_0} - a_0 ⋅ b_0 \\ \end{aligned} $$
If party $i$ knows the secret shares of $i$ and $i+1$ it can compute the $i$-th row of this product. Since these rows summed together produce the product value, they constitute valid shares for $[a⋅b]$. This leads to the following protocol (indices are taken modulo $n$):
- Party $i$ sends its shares $a_i, b_i$ to party $i-1$.
- Party $i$ computes $c_i = \p{a_i + a_{i+1}}⋅\p{b_i + b_{i+1}} - a_{i+1}⋅b_{i+1}$.
It is important to note that the first step reduces the treshold, as now any two parties can recover the secret where before all three where required.
Note. We can view the regular state and the replicated state as two different secret sharing schemes. A multiplication operation converts a replicated state into a regular one. The replication protocol re-establishes the replicated state.
Q. What re-randomization is required?
To generalize this to $n$ parties with a threshold of $t$ we need to find a number of shares $k$ and an assignment to parties such that for every combination $(i,j)$ of shares at least one party has those two shares, and no fewer than $t$ parties combined have all the shares. A combinatorial search gives the following as the smallest $t=3$ solution, it requires $10$ parties and $5$ shares assigned as:
$$ \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} $$
These are the edges of the $K_5$ graph. Similarly the $3$-party scheme is generated by the $K_3$ graph. Generally the full graph $K_k$ generates a replication protocol with
$$ \begin{aligned} n &= \frac{k⋅\p{k-1}}{2} & t &= \ceil{\frac{k}{2}} \end{aligned} $$
$$ \begin{array}{c|} k & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline n & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \\ t & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5\\ \end{array} $$
Q. How does this relate to JSL21 § B.2? They cite in the intro Mau06 as the originator and [KRSW18], [SW19] and call the replication protocol 'KRSW'.
Todo. In Mau06 and others each party deals their partial result to all parties, which are then summed. This has different communication complexity then the AFL⁺16 MR18 protocol where each party adds randomized zero and shares with their neighbor. The summation of terms is implicitly performed on decoding. This is distinct enough to consider them separate variants (like BGW88 and CCD88 below).
Shamir multiplication
Consider a Shamir secret sharing schemes with $\vec s$ and $\vec x$. The parties have secrets $[a]$ and $[b]$ and wish to compute the product $[c] = [a⋅b]$. If they locally multiply shares such that $c_i = a_i ⋅ b_i$ they have constructed a polynomial
$$ P_c(X) = P_a(X)⋅P_b(X) \mod \Z_{\vec x}(X) $$
where $\Z_{\vec x}$ is the zero polynomial such that $\Z_{\vec x}(X) = \prod_{x ∈ \vec x} \p{X - x}$. To get the correct results we instead need to end up with a $P_c(X)$ such that
$$ P_c(X) = P_a(X)⋅P_b(X) \mod \Z_{\vec s}(X) $$
In BGW88, CCD88 it is noted this can be achieved by reducing the degrees of $P_a$ and $P_b$ such that their product is lower degree than $\deg \Z_{\vec x} = n$. Denote with $[–]_d$ the Shamir scheme restricted to degree at most $d$. Then elementwise multiplication of shares $[a]_k$, $[b]_l$ results in $[a⋅b]_{k+l}$ if $k+l < n$.
In BGW88, FY92, AL11 degree reduction to $d$ is achieved using the intra-share matrix multiplication protocol with the matrix $\mat M$ given by
$$ \mat M = \mat V_{\vec x} ⋅ \operatorname{diag}(\overbrace{1, 1, …, 1 }^{d+1}, \overbrace{0, 0, …, 0}^{n - d - 1}) ⋅ \mat V_{\vec x}^{-1} $$
In CCD88 and DN07 the degree reduction is instead achieved under the scheme conversion protocol.
Q. Instead of degree reduction, can we use other constraints on the scheme? The degree reduction aims to avoid the effects of the modular reduction, other schemes will instead need to correct for it. This seems like a linear problem.
Q. Is there any way this can be made to work for non-Shamir schemes?
The minimum and maximum degree for an $n$-party Shamir scheme with $s$ secrets and threshold $t$ is
$$ s + t - 2 ≤ d ≤ n - 1 $$
The number of minimum degree secret factors that can be multiplied before the product exceeds the degree capacity of the parameters is
$$ \floor{\frac{n - 1}{s + t - 2}} $$
Some optimal small-$n$ parameter choices are:
$$ \begin{array}{c|c:cc:ccc:} n & 2 & 3 & 3 & 4 & 4 & 4 & 5 & 5 & 5 & 5\\ s & 1 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 & 4\\ t & 2 & 2 & 2 & 2 & 3 & 2 & 2 & 3 & 2 & 2\\ \hline d_{\min} & 1 & 1 & 2 & 1 & 3 & 3 & 1 & 2 & 2 & 4 \\ d_{\max} & 1 & 2 & 2 & 3 & 3 & 3 & 4 & 4 & 4 & 4 \\ n_{\mathrm{mul}} & 1 & 2 & 1 & 3 & 1 & 1 & 4 & 2 & 2 & 1 \\ \end{array} $$
Q. What if we have an $s$-multi secret where we want to multiply all $s$ against the same value, encoded as a $s=1$ secret? We can alternatively encode it as a $s=2$ secret with the constraint that both are identical. This constraint acts much like a degree reduction. Then in the $n=4, t=2$ case we could multiply an $s=2$ secret times an (repeated) $s=1$ secret.
To do. Extensions like multi-variate polynomials, Hermite interpolation and recursive Shamir schemes.
References
- Sha79 Adi Shamir (1979). How to Share a Secret.
- CCD88 David Chaum, Claude Crépeau, Ivan Damgård (1988). Multiparty unconditionally secure protocols.
- BGW88 Michael Ben-Or, Shafi Goldwasser, Avi Wigderson (1988). Completeness theorems for non-cryptographic fault-tolerant distributed computation.
- Bea91 Donald Beaver (1991). Efficient Multiparty Protocols Using Circuit Randomization.
- FY92 Matthew Franklin, Moti Yung (1992). Communication complexity of secure computation.
- BW98 Donald Beaver, Avishai Wool (1998). Quorum-based multi-party computations.
- CDN01 Ronald Cramer, Ivan Damgård, Jesper B. Nielsen (2001). Multiparty Computation from Threshold Homomorphic Encryption.
- DN07 Ivan Damgård, Jesper Buus Nielsen (2007). Scalable and Unconditionally Secure Multiparty Computation.
- BH08 Zuzana Beerliová-Trubíniová, Martin Hirt (2008). Perfectly-Secure MPC with Linear Communication Complexity.
- AL11 Gilad Asharov, Yehuda Lindell (2011). A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation
- CDN15 Ronald Cramer, Ivan Bjerre Damgård, Jesper Buus Nielsen (2015). Secure Multiparty Computation and Secret Sharing.
- 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.
- MR18 Payman Mohassel and Peter Rindal (2018). ABY3: A Mixed Protocol Framework for Machine Learning.
- EKR18 David Evans, Vladimir Kolesnikov, Mike Rosulek (2018). A Pragmatic Introduction to Secure Multi-Party Computation.
- GS20 Vipul Goyal, Yifan Song (2020). Malicious Security Comes Free in Honest-Majority MPC.
- CGG⁺20 Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, Gabriel Kaptchuk (2020). Fluid MPC: Secure Multiparty Computation with Dynamic Participants.
- GSZ20 Vipul Goyal, Yifan Song, and Chenzhi Zhu (2020). Guaranteed Output Delivery Comes Free in Honest Majority MPC.
- JSL21 Robin Jadoul, Nigel P. Smart, Barry Van Leeuwen (2021). MPC for $\mathcal Q_2$ Access Structures over Rings and Field.
- Esc23 Daniel Escudero (2023). An Introduction to Secret-Sharing-Based Secure Multiparty Computation.
- PSSY20 Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame (2020). ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation.
- MRZ15 Payman Mohassel, Mike Rosulek, and Ye Zhang (2015). Fast and Secure Three-party Computation: The Garbled Circuit Approach.
- MZ17 Payman Mohassel and Yupeng Zhang (2017). SecureML: A System for Scalable Privacy-Preserving 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.
https://pdf.sciencedirectassets.com/271602/1-s2.0-S0166218X05X03134/1-s2.0-S0166218X05002428/main.pdf
D. Beaver, A. Wool, , Advances in Cryptology—EUROCRYPT ’98, Lecture Notes in Computer Science, vol. 1403, Springer, Berlin, 1998, pp. 25–35.
- ACD⁺19 Mark Abspoel, Ronald Cramer, Ivan Damgård, Daniel Escudero, and Chen Yuan (2019). Efficient Information-Theoretic Secure Multiparty Computation over $\mathbb{Z}/p^k \mathbb{Z}$ via Galois Rings.
https://eprint.iacr.org/2018/260.pdf https://eprint.iacr.org/2021/1025.pdf
- EIP00 Michele Elia, J. Carmelo Interlando, and Reginaldo Palazzo Jr. (2000) Computing the reciprocal of units in Galois rings.