1 Introduction

A secret-sharing scheme is a mathematical object that disperses a secret element into n shares. Combined, the shares determine the secret, but individual shares, and limited subsets of them, contain no information about the secret. In linear secret-sharing schemes (LSSS), given several secret-shared elements, linear operations on the secrets correspond to linear operations on the shares. LSSS are the cornerstone of information-theoretic multiparty computation (MPC) protocols, but they also have applications in other domains of cryptography.

LSSS and MPC are typically defined over finite fields (e.g., the secret and the shares are elements of the same finite field), which have a rich algebraic structure. A natural question is whether we can extend some of these techniques to other structures, such as rings \(\mathbb {Z}/p^k\mathbb {Z} \) where \(k>0\) is an integer and p is a prime. This question is not only motivated in theory: some results [3, 18] show that MPC over \(\mathbb {Z}/{2}^k\mathbb {Z} \) with \(k=32\) or \(k=64\) can offer many practical benefits compared to fields, partly due to the compatibility of binary arithmetic in modern hardware. Feasibility of LSSS and MPC over these rings, as well as theoretical benefits, were already demonstrated back in 2003 based on black-box secret sharing [14].

Recently, MPC directly over these rings has been shown, in both the cryptographic dishonest majority setting [12] as well as the information-theoretic setting [2], by extending and generalizing existing techniques over fields. Both of these approaches use a single LSSS defined over \(\mathbb {Z}/p^k\mathbb {Z}\): additive secret sharing and a variant of Shamir’s secret sharing, respectively. It is natural to wonder whether techniques for other LSSS can be extended to these rings, to obtain desirable properties such as good asymptotic complexity.

In this work, we study the lifting of linear codes defined over finite fields to Galois rings, which are a natural generalization of both finite fields and our rings of interest \(\mathbb {Z}/p^k\mathbb {Z}\). In a way, Galois rings are analogues of finite fields: informally, a Galois ring is to \(\mathbb {Z}/p^k\mathbb {Z}\), what a finite field is to the prime field \(\mathbb {F}_{p}\). Therefore, to extend existing techniques over finite fields to work over \(\mathbb {Z}/p^k\mathbb {Z}\), it is necessary to consider Galois rings. As shown in Sect. 3, lifting preserves the essential properties of linear codes (distance, dual distance) that make them suitable as LSSS.

However, extending the theory of LSSS to Galois rings is not straightforward, due to the reduced structure and the presence of non-invertible elements. Thus, a priori it is not clear if properties of LSSS over fields carry over when considering these constructions over Galois rings. The above leads to the following question: Can we obtain “good” LSSS over a Galois ring? More precisely, we focus on realizing families of LSSS indexed by n, the number of shares, with privacy and reconstruction thresholds arbitrarily close to n/2, and with the information rate tending to a positive constant. The most widely known construction of LSSS over fields, Shamir secret sharing, does not satisfy the rate condition as it is based on polynomial interpolation and therefore the shares have to be at least \(\log (n)\) in length. This issue was addressed over fields in the work of [10], using non-trivial results on random codes.

The above question is relevant for MPC that is asymptotically optimal, i.e., secure multiplication that has a total communication complexity linear in the number of players  [16]. For information-theoretic MPC we typically care about arithmetic secret-sharing schemes, or synonymously, LSSS with multiplicativity: given two secret-shared elements, their product is a linear function of the pairwise products of shares. However, as we shall demonstrate with a counterexample in Sect. 3, multiplicativity does not directly lift.

True linear complexity is hard to achieve, and in fact conjectured to be impossible in the maximal adversary case \(n = 2 t + 1\) for the single-circuit setting.Footnote 1 Many state-of-the-art protocols such as [5, 21] state a linear complexity, but the complexity is given in the number of field elements communicated. If the field is fixed and the number of players tends to infinity, this obscures a \(\log (n)\) factor in the bit-complexity of the protocol. Over fields, this asymptotic factor does not affect the complexity for practical ranges of parameters, since the field size is usually much larger than the number of players. However, for our rings \(\mathbb {Z}/p^k\mathbb {Z}\) this issue is more pressing, since the comparable requirement is that \(p > n\) rather than \(p^k > n\) [2], thus leading to a \(\log (n)\) factor immediately if for example \(p=2\). Removing this \(\log (n)\) overhead is thus worthwhile and in fact highly desired, since it would achieve a constant complexity per party: even if more parties join the computation, the communication per party does not increase.

1.1 Our Contributions

We show that some of the results for LSSS over a finite field \(\mathbb {F}\) also hold over a Galois ring R that contains \(\mathbb {F}\) as a residue field, by arbitrarily lifting the associated code over \(\mathbb {F}\) to R, and showing that certain relevant properties are preserved.

First, in Sect. 3, we show that we can obtain explicit good families of linear codes over Galois rings. In what follows, R is a large enough Galois ring.

Theorem 1 (informal)

There exists an explicit family of R-linear codes over R with \(|R|=O_{\varepsilon }(1)\) such that its relative distance is at least \(\frac{1}{2}-\varepsilon \) and relative dual distance is at least \(\frac{1}{2}-\varepsilon \). In particular, there exists an explicit family of self-dual codes over R with relative distance at least \(\frac{1}{2}-\varepsilon \).

It is well-known that any linear code over a field with good parameters yields a good linear secret-sharing scheme [25], and it is straightforward to show this also holds over Galois rings. However, to get the arithmetic secret-sharing schemes that we need, we also need good parameters for the square of the code. We demonstrate with a counterexample that these parameters are not preserved by arbitrary lifts.

We work around this issue by showing a dedicated lift for \(p > 2\) that preserves self-orthogonality in Sect. 3.1. For \(p = 2\) we secret-share elements using both C and \(C^\perp \), at the expense of increasing the share size by a factor of two. Both of these approaches rely on techniques from [13] to obtain arithmetic secret sharing via a code and its dual, and we demonstrate in Sect. 4 that these extend to Galois rings. We capture the asymptotic result in the following theorem.

Theorem 2 (informal)

There exists a family of R-arithmetic secret-sharing schemes \(\varSigma _1, \varSigma _2, \dots \) over R with \(|R|=O_{\varepsilon }(1)\) such that the number of players \(n(\varSigma _i) \rightarrow \infty \), and the schemes have \(t(\varSigma _i) \ge (1/2 - \varepsilon ) n(\varSigma _i)\)-privacy and \(r(\varSigma _i) \ge (1/2 - \varepsilon ) n(\varSigma _i)\)-reconstruction.

To illustrate the power of our results on arithmetic secret sharing, we apply them to the problem of communication-efficient honest-majority MPC over \(\mathbb {Z}/p^k\mathbb {Z} \). This problem has only recently been studied in [2], but the authors were more concerned with feasibility rather than achieving optimal communication complexity. In particular, their protocol is based on the (no longer state-of-the-art) protocol of [4], which has \(O(n^2 \log (n))\) complexity in the number of parties. Here, the \(\log (n)\) factor comes from polynomial interpolation, as discussed above. Plugging in our LSSS we immediately remove this \(\log (n)\) factor and obtain true quadratic complexity for the adversary regime of \(t < (1/2 - \varepsilon )n\), analogously to the work of [10] over fields.

We further improve the complexity, for three different regimes:

  1. 1.

    (Section 5) For passive security, we present a protocol that obtains an amortized communication complexity of O(n) bits per multiplication gate.

  2. 2.

    (Section 6) For active security with abort, we present a protocol with an amortized communication complexity of O(n) bits per multiplication gate.

  3. 3.

    (Section 7) For full active security with guaranteed output delivery, we obtain an amortized communication complexity of \(O(n\log (n))\) bits for the offline phase and O(n) bits for online phase. This solves the open problem from [2].

The last protocol is the most involved, since we adapt the protocol of [6] to work over Galois rings. Here we achieve linear complexity only in the online phase, as we still rely on polynomial interpolation to efficiently verify multiplication triples in the preprocessing phase. This matches the state-of-the-art over fields until the very recent result of [22]. However, since their protocol also uses the constructions of [6], our techniques can be combined with theirs to achieve linear complexity for the preprocessing phase.Footnote 2

1.2 Overview of Our Techniques

We mainly use elementary (arbitrary) liftings from codes C over a finite field \(\mathbb {F} \) to a Galois ring that contains \(\mathbb {F} \) as its residue field, and \(\mathbb {Z}/p^k\mathbb {Z} \) as a subring. This way we leverage results from codes over fields directly. For example, since there exist explicit families of codes with asymptotically good distance and dual distance over a finite field \(\mathbb {F} \), we also obtain explicit families of codes with asymptotically good distance and dual distance over R.

Once we obtain arithmetic secret sharing over R we can use it to get MPC over \(\mathbb {Z}/p^k\mathbb {Z} \). Our general template to obtain an MPC protocol is to first develop protocols over R itself, and since \(\mathbb {Z}/p^k\mathbb {Z} \) is a subring of R, we can supply inputs in \(\mathbb {Z}/p^k\mathbb {Z} \) and then evaluate a circuit over R to securely obtain the correct output in \(\mathbb {Z}/p^k\mathbb {Z} \)Footnote 3 \(^{,}\)Footnote 4

Our passively secure protocol over R follows the template of [17], which consists of preprocessing so-called “double-sharings” and then using them to compute secure multiplications in the online phase. Since our construction of arithmetic secret sharing does not come directly from a code, we abstract the underlying technique to work on arbitrary arithmetic secret-sharing schemes. We do not have access to Vandermonde matrices over R directly, but we fix this by moving to an extension of Galois rings without amortized overhead using the “tensoring trick” from [9] together with the interpolation theorems from [2].

To get our actively secure protocol with abort, we make the simple but powerful observation that our protocol above is already actively secure up to additive attacks, i.e., the only attack that an adversary may carry out is to add a chosen value to the outputs of multiplications that is independent of the inputs. We obtain our actively secure protocol with abort by compiling our passively secure protocol with the recent work of [3], preserving linear complexity.Footnote 5

Finally, for our actively secure protocol with guaranteed output delivery we use our arithmetic secret-sharing scheme as a building block and extend the protocol of [6], which is defined over a field in the \(t < n/2\) regime. We show the check of authentication tags generalizes to our setting, and show how to compute the authentication tags (based on “twisted sharings”) using our secret-sharing scheme. We also adapt the batch verification of triples.

1.3 Related Work

Honest majority MPC over rings has been already studied in [14] via black-box secret sharing, but their computational overhead is rather large. This problem was not revisited until very recently, with the work of [2], which presented efficient constructions using Galois rings, showing their potential benefits in the theory of MPC. They provide a protocol for multiplication with \(O(n \log n)\) bits of total communication per gate, for the \(t < n/3\) setting. This \(\log (n)\) factor comes from using Shamir’s scheme, and removing it requires codes with good distance of the square, or asymptotically good families of reverse multiplication-friendly embeddings, which as we illustrate in Example 2 are out of reach of our elementary lifting methods. Both were very recently claimed by [15], and illustrated with protocols for the \(t < n/3\) setting. The tools developed in the present work enable up to honest majority, so are therefore complementary. Also, the recent work of [3] considers honest majority MPC over \(\mathbb {Z}/{2}^k\mathbb {Z} \), but they achieve only security with abort and they do so with a communication complexity of \(O(n\log (n))\) for both online and offline phases.

On the other hand, there are several other works in the context of honest-majority MPC over fields. We have already mentioned the work of Ben-Sasson et al.  [6], that proposes a protocol in the honest-majority setting with guaranteed output delivery and near-linear communication complexity, and constitutes the basis of our protocol in Sect. 7. More recently, the protocol of [22] improves upon the protocol in [6] by introducing a novel method for verifying the correctness of multiplication triples. In the setting of security with abort the line of research is richer, with many protocols proposed in the last few years that aim at providing concrete practical efficiency. For example, an efficient general compiler from active security up to additive attacks to active security is presented in [11], which improves upon the methods built in [24]. The work of [26] also improves upon [24] by extending it using similar ideas as the batch triple check presented in [6]. Also, very recently, an efficient method to achieve actively secure three party computation was presented [8], building on top of the distributed zero knowledge proof techniques introduced in [7]. Although the authors of this work do consider an extension of their protocol to the ring \(\mathbb {Z}/{2}^k\mathbb {Z} \), but it is unlikely to be efficient in practice as they make use of a Galois ring of a degree that is roughly equal to the security parameter.

2 Preliminaries

2.1 Linear Codes over Finite Fields

Let \(\mathbb {F}_{q} \) be the finite field with q elements, and let \(\mathbb {F}_{q} ^n\) be the \(\mathbb {F}_{q} \)-vector space consisting of n copies of \(\mathbb {F}_{q} \). A code \(C\subseteq \mathbb {F}_{q} ^n\) is a set of row vectors in \(\mathbb {F}_{q} ^n\). The rate of C is defined as \(\frac{\log _q |C|}{n}\). For a vector \(\mathbf{x}= (x_1, \dots , x_n)\) its Hamming weight is the number of nonzero coordinates: \(w_H(\mathbf{x}) = | \{ i \in [n] \;|\;x_i \ne 0 \} |\), where we write \([n] := \{1, \dots , n\}\). If \(\mathbf{y}=(y_1,\ldots ,y_n)\in \mathbb {F}_{q} ^n\) is another vector, the Hamming distance between \(\mathbf{x}\) and \(\mathbf{y}\) is the number of coordinates in which they differ \(d(\mathbf{x},\mathbf{y})=|\{i \in [n] \;|\;x_i\ne y_i\}| = w_H(\mathbf{x}- \mathbf{y})\). The minimum distance of a code C is defined as \(d(C)=\min _{\mathbf{x}\ne \mathbf{y}\in C}d(\mathbf{x},\mathbf{y})\).

In the following, let \(C \subseteq \mathbb {F}_{q} ^n\) be a linear subspace; we then say C is a linear code. The dimension of C is the dimension of C as a vector space. If C has \(k = \dim (C)\) and \(d = d(C)\), we say C is a [nkd]-linear code over \(\mathbb {F}_{q} \). A matrix G is a generator matrix for C if its rows form a basis for C. The dual code of C is defined as \(C^{\perp }=\{\mathbf{x}\in \mathbb {F}_{q} ^n \;|\;\forall \mathbf{y}\in C : \mathbf{x}\mathbf{y}^T=0 \}\). One can see that \(C^{\perp }\) is a linear code with dimension \(n-\dim _{\mathbb {F}_{q}}(C)\). The dual distance of C is defined as the minimum distance of \(C^\perp \), and is denoted as \(d^\perp (C)\).

In this paper, we are mostly concerned with the minimum distance d and dual distance \(d^{\perp }\) of a linear code C. For applications to secret sharing, we want both of these to be large, since they imply \((n-d+1)\)-reconstruction and \((d^\perp -1)\)-privacy for secret-sharing scheme associated to the code. There is a large body of works dedicated to determining the achievable distance and dual distance of a code. In this work, we are particularly interested in the asymptotic behavior of d and \(d^{\perp }\). To characterize this asymptotic behavior, we look at the relative distance \(\delta =\frac{d}{n}\) and relative dual distance \(\delta ^{\perp }=\frac{d^\perp }{n}\).

Definition 1

A family \(C_1,C_2,\ldots \) of linear codes over a fixed finite field, where each \(C_i\) has parameters \([n_i,k_i,d_i]\) and dual distance \(d^{\perp }_i\), is said to have relative distance \(\delta \) and relative dual distance \(\delta ^{\perp }\) if the following holds:

$$\begin{aligned}&1. \lim _{i\rightarrow \infty }n_i=\infty \\&2. \liminf _{i\rightarrow \infty }\frac{d_i}{n_i}\ge \delta , \quad \liminf _{i\rightarrow \infty }\frac{d^{\perp }_i}{n_i}\ge \delta ^{\perp }. \end{aligned}$$

We stress that we study this asymptotic behaviour only for a family of codes defined over the same finite field.

In general, there are two ways to construct a family of codes with large relative distance and relative dual distance. One way is through a random argument that gives a family of codes reaching the Gilbert-Varshamov bound. For a finite field \(\mathbb {F}_{q} \) with \(q < 49\), this Gilbert-Varshamov Bound is the best lower bound known. When \(q \ge 49\) is a square, there exists an explicit construction of algebraic geometric codes outperforming the random codes, i.e., there exists a family of algebraic geometric codes attaining the celebrated Vlăduţ-Drinfeld bound [19]. We skip the details of these codes and refer the interested reader to [28]. The family of algebraic geometric codes attaining the celebrated Vlăduţ-Drinfeld bound meets the following condition.

Proposition 1

Let q be any prime power. Then there exists an explicit family of codes over a fixed finite field \(\mathbb {F}_{q^2}\) with relative distance \(\delta \) and relative dual distance \(\delta ^{\perp }\) as long as \(\delta \) and \(\delta ^{\perp }\) satisfy

$$\begin{aligned} \delta +\delta ^{\perp }\le 1-\frac{2}{q-1}. \end{aligned}$$
(1)

A similar result holds for self-dual codes [27], i.e., there exists an explicit family of self-dual codes reaching the Vlăduţ-Drinfeld bound.

Proposition 2

Let \(\varepsilon > 0\) be any small constant. Then, for any \(q \ge 2/\varepsilon \) there exists an explicit family of codes over a fixed finite field \(\mathbb {F}_{q^2}\) such that its relative distance \(\delta \ge \frac{1}{2}-\varepsilon \) and its relative dual distance \(\delta ^{\perp }\ge \frac{1}{2}-\varepsilon \). Moreover, there exists an explicit family of self-dual codes over a fixed finite field \(\mathbb {F}_{q^2}\) with relative distance \(\delta \ge \frac{1}{2}-\varepsilon \).

2.2 Galois Rings

Galois rings are a natural analogue to finite fields: roughly, Galois rings are to \(\mathbb {Z}/p^k\mathbb {Z}\) what finite fields are to prime-order fields \(\mathbb {F}_{p}\). As such, these rings have rich structure and they share many properties with finite fields. In fact, Galois rings are a strict generalization of finite fields, since setting \(k=1\) one obtains exactly the finite fields.

Definition 2

Let p be a prime number and let k be a positive integer. Let \(g(Y)\in (\mathbb {Z}/p^{k}\mathbb {Z})[Y]\) be a monic polynomial such that its reduction modulo p is an irreducible polynomial in \(\mathbb {F}_{p} [Y]\). The ring

$$ R:= (\mathbb {Z}/p^{k}\mathbb {Z})[Y]/\left( g(Y)\right) $$

is called a Galois ring.

Proposition 3

\(R\) has the following properties:

  1. 1.

    It is a local ring, i.e. it has a unique maximal ideal \((p)\subsetneq R\). We have that \(R/(p)\cong \mathbb {F} := \mathbb {F}_{p^h}\), where h denotes the degree of g.

  2. 2.

    The Lenstra constant of \(R\) is \(p^h\), which gives the maximum number of interpolation points in Shamir’s (because the pairwise differences must be invertible)

  3. 3.

    For any prime p, positive integer k, and positive integer h there exists a Galois ring as defined above, and any two of them with identical parameters pkh are isomorphic. We may therefore write \(R = \mathsf {GR}(p^k, h)\).

  4. 4.

    If e is any positive integer, then R is a subring of \(\hat{R}= \mathsf {GR}(p^k, h \cdot e)\). There is a polynomial \(\hat{g} \in R[X]\) that is irreducible modulo p, such that \(\hat{R}= R[X]/(\hat{g}(X))\). There is a natural R-module isomorphism \(R^e \rightarrow \hat{R}\).

Remark 1

Also, we have a natural ring embedding \(\mathbb {Z}/p^{k}\mathbb {Z}\hookrightarrow R\), given by mapping \(x\mapsto x \bmod {g(Y)}\). Moreover, there is another way to uniquely represent the elements of \(R\). Since \(R/(p)\cong \mathbb {F} \), let \(\xi \) be a non-zero element of order \(p^h-1\) in \(R\) and define the subset

$$\begin{aligned} \mathcal {I}=\{0,1,\xi ,\ldots ,\xi ^{p^h-2}\} \subset R \; .\end{aligned}$$
(2)

Then, any element \(a\in R\) can be uniquely written as

$$ a=a_0+a_1p+a_2p^2+\cdots +a_{k-1}p^{k-1} \text { where } a_0,\ldots ,a_{k-1}\in \mathcal {I}\; .$$

This decomposition also allows us to define “division by powers of p”. Indeed, notice that given an element \(a=a_0+a_1p+a_2p^2+\cdots +a_{k-1}p^{k-1}\in R\) and a positive integer u, we have that \(p^u\) divides a if and only if \(a_i=0\) for all \(i<u\). If this is the case, we then define \(a/p^u:= a_u+a_{u+1}p+\dots + a_{k-1}p^{k-u-1} \in \mathsf {GR}(p^{k-u}, h)\); notice that \(a/p^u \equiv a_u \pmod {p}\). If u is maximal and a is non-zero in \(R\), then \(a/p^u \in R^*\).

Finally, Item 1 of Proposition 3 gives rise to the canonical map \(\pi : R \rightarrow \mathbb {F} \) (“reduction modulo p”), which we shall frequently use. It is easy to see that \(\pi |_{\mathcal {I}}\) is bijection, and in particular we have a one-to-one correspondence between \(\mathcal {I}\) and \(\mathbb {F}_{p^h} \). Given \(x \in R\) we shall also write \(\overline{x} = \pi (x)\).

3 Codes over Galois Rings

In this section, we show how to obtain codes over Galois rings. Although there is a large body of works dedicated to linear codes, most of it only deals with codes over finite fields. For the purpose of asymptotically good secret-sharing schemes, we need a family of codes over Galois rings whose rate and relative distance tends to a positive constant.

We obtain such codes by arbitrarily lifting linear codes defined over some finite field \(\mathbb {F} \), such as the ones from Proposition 1, to a Galois ring whose residue field is \(\mathbb {F} \). We show that the lifted codes have at least the same distance and dual distance as the original codes, hence using Proposition 1 we obtain a good family of codes over Galois rings of arbitrary characteristic \(p^k\).

For the particular case of self-orthogonal codes defined over a field of characteristic \(\ne 2\), we give an explicit lift that preserves self-orthogonality in Sect. 3.1. Self-orthogonal codes satisfy a multiplicative property that is needed for arithmetic secret sharing. In Sect. 4 we show how to extend existing techniques to obtain multiplication for \(p = 2\), but this comes at the cost of doubling the share size.

Let \(R = \mathsf {GR}(p^k, h)\) be a Galois ring with residue field \(\mathbb {F} = \mathbb {F}_{p^h}\). We define a linear code C of length n over R to be a free R-submodule of \(R^n\). We define its dimension as \(\dim (C) = {{\,\mathrm{rank}\,}}_R(C)\). Recall the canonical homomorphism \(\pi : R \rightarrow \mathbb {F} \). For convenience we will also write \(\pi \) for the induced map on vectors or matrices defined over R, and write \(\overline{\mathbf{x}} := \pi (\mathbf{x})\) for \(\mathbf{x}\in R^n\) and \(\overline{M}=\pi (M)\) for a matrix M over R.

Proposition 4

Let C be a linear code over R. Then the following statements hold:

  1. 1.

    \({{\,\mathrm{rank}\,}}_R C = \dim _{\mathbb {F}} \overline{C}\), where \(\overline{C} = \pi (C) \subseteq \mathbb {F} ^n\) is the reduction of C modulo p.

  2. 2.

    If \(\mathbf{c}\ne \mathbf {0} \in C\) we may write \(\mathbf{c}= p^m \mathbf{y}\), for \(0 \le m < k\) and \(\pi (\mathbf{y})\ne \mathbf {0} \in \overline{C}\).

Proof

Let us prove the first claim. Since \(C\subseteq R^n\) is a linear code, it has an R-basis \(\mathbf{e}_1,\ldots ,\mathbf{e}_t\in R^n\). Then, it is clear that \(\overline{C}\) is an \(\mathbb {F} \)-linear code spanned by \(\pi (\mathbf{e}_1),\ldots ,\pi (\mathbf{e}_t)\). If we can show that \(\pi (\mathbf{e}_1),\ldots ,\pi (\mathbf{e}_t)\) are linearly independent over \(\mathbb {F} \), then we are done. Assume this is false, so there exist \(\lambda _1,\ldots ,\lambda _k\in \mathbb {F} \) not all equal to 0 such that \(\sum _{i=1}^t \lambda _i \pi (\mathbf{e}_i)=0\). Let \(\lambda '_i=\pi ^{-1}(\lambda _i)\in \mathcal {I}\subseteq R\), then it holds that \(\sum _{i=1}^t \lambda '_i \mathbf{e}_i \in pR\), since

$$ \pi \left( \sum _{i=1}^t \lambda '_i \mathbf{e}_i\right) =\sum _{i=1}^t \lambda _i \pi (\mathbf{e}_i)=0. $$

It follows that \(\sum _{i=1}^t p^{k-1}\lambda '_i \mathbf{e}_i=0\) and \(p^{k-1}\lambda '_1,\ldots ,p^{k-1}\lambda '_t\) are not all zero. This contradicts the claim that \(\mathbf{e}_1, \dots , \mathbf{e}_t\) form a basis of C.

We turn to the second claim. Let G be a \(t\times n\) matrix over R whose rows form a basis \(\mathbf{e}_1,\ldots ,\mathbf{e}_t\) of C. We may represent \(C=\{\mathbf{x}G: \mathbf{x}\in R^t\}\). We call G the generator matrix of C, which gives a linear isomorphism between \(R^t\) and C. Let \(\mathbf{c}=\mathbf{x}G\) be any nonzero codeword in C. Since G is an isomorphism, \(\mathbf{x}\) is also a nonzero vector. By Remark 1, we write \(\mathbf{x}=p^m \mathbf{x}_1\) with \(0 \le m < k\) and \(\mathbf{x}_1\ne \mathbf {0}\in \mathcal {I}^t\). This follows that \(\mathbf{c}=p^m \mathbf{x}_1G\). Let \(\mathbf{y}=\mathbf{x}_1G\) and the desired result follows as \(\pi (\mathbf{y})=\pi (\mathbf{x}_1) \pi (G)\in \overline{C}\) is a nonzero codeword.    \(\square \)

Lemma 1

Let \(C \subseteq R^n\) be a linear code. We have \(d(C) \ge d(\overline{C})\).

Proof

Let G be the generator matrix of C. Since C is a linear code, it suffices to bound the weight of its codewords. For any \(\mathbf{c}\ne \mathbf {0} \in C\), by Proposition 4 we can write \(\mathbf{c}=p^m \mathbf{y}\) for some \(\overline{\mathbf{y}} \ne \mathbf {0}\in \overline{C}\) and \(m<k\). Note that \(\overline{\mathbf{y}}\) is a nonzero codeword of \(\overline{C}\). Thus, \(w_H(\mathbf{c})\ge w_H(\mathbf{y})\ge d(\overline{C})\). The proof is completed.    \(\square \)

Example 1

It is hopeless to control the minimum distance without the freeness assumption. Consider the code \(\overline{C}:= \langle (1,1,\dots ,1) \rangle \) of two elements code over \((\mathbb {F}_2)^n\), with distance n. We can lift the code to \(\mathbb {Z}/2^2\mathbb {Z}\) as \(C:= \langle (1,1,\dots ,1),(2,0,\dots ,0) \rangle \) which is non-free, because of the bad element \((2,0,\dots ,0)\). Then \(d(C)=1 \ll d(\overline{C})=n\).

Like for codes over a field, we can similarly define the dual code over \(R\). The dual code of C is defined as \(C^{\perp }=\{\mathbf{c}\in R^n \;|\;\mathbf{c}\mathbf{y}^T=\mathbf {0}\text { for all } \mathbf{y}\in C \}\).

Lemma 2

Assume that \(C\subseteq R^n\) is a t-dimensional \(R\)-linear code. Then, \(C^{\perp }\subseteq R^n\) is a \((n-t)\)-dimensional \(R\)-linear code. Moreover, the minimum distance of \(C^{\perp }\) is lower bounded by the minimum distance of the dual code of \(\overline{C}\).

Proof

Let G be the generator matrix of C. Every element in \(C^{\perp }\) is a solution to the linear equation \( G \mathbf{x}^T=\mathbf {0}\) over \(R\), and vice versa. This implies that \(C^{\perp }\) is the kernel \(\ker (G)\) of the \(R\)-linear map \(G\mathbf{x}^T\). The image \({{\,\mathrm{im}\,}}(G)\) of \(G\mathbf{x}^T\) is C, a free module of \(R^n\) with rank t. The homomorphism theorem of modules states that \(R^n/\ker (G)\cong {{\,\mathrm{im}\,}}(G)\). Thus, the kernel is also free and has rank \(n-t\). By our definition, \(\ker (G)\) is a linear code of dimension \(n-t\) over R.

It remains to lower bound the minimum distance of \(C^{\perp }\). Given any codeword \(\mathbf{c}\ne \mathbf {0} \in C^{\perp }\), we have \(G\mathbf{c}^T=\mathbf {0}\). Moreover, by Remark 1, we can write \(\mathbf{c}=p^m\mathbf{y}\) for \(0 \le m < k\) and \(\mathbf{y}\ne \mathbf {0}\in \mathcal {I}^t\). Reducing modulo p gives \(\overline{G}\overline{\mathbf{y}}^T=0\) over \(\mathbb {F}_{p^h} \). This implies that \(\overline{\mathbf{y}}\) is a nonzero codeword in the dual code of \(\overline{C}\). Then, the desired result follows.    \(\square \)

We now define the square of a linear code C over \(R\). Given \(\mathbf{x}= (x_1, \dots , x_n)\), \(\mathbf{y}= (y_1, \dots , y_n) \in R^n\) denote their componentwise (Schur) product as \(\mathbf{x}*\mathbf{y}= (x_1 y_1, \dots , x_n y_n) \in R^n\). The square code \(C^{*2}\) is defined as \({{\,\mathrm{span}\,}}_{R}\{\mathbf{x}*\mathbf{y}\in R^n \;|\;\mathbf{x},\mathbf{y}\in C\}\). We emphasize that this square code \(C^{*2}\) is an R-module but not necessarily a free R-module. We say C is t-strongly multiplicative if the minimum distance d(C), its dual distance \(\mathrm {d^\bot }(C)\) and the distance of the square \(d(C^{*2})\) are at least t.

One may wonder whether strong multiplication is preserved when lifting. Unfortunately, our next example shows that we can have poor distance of the square code \(C^{*2}\) even if \(\overline{C}^{*2}\) is a square code with large distance.

Example 2

Let \(C_1\) and \(C_2\) be linear code over \(\mathbb {F}_{p^h} \) such that \(C_1^{*2}\) and \(C_2^{*2}\) have distance \(d_1\) and \(d_2\) respectively. Let \(S=GR(p^3,h)\) and C be a code over S defined as \(C=\left\{ \left( \pi ^{-1}(\mathbf{c}_1),p\,\pi ^{-1}(\mathbf{c}_2)\right) \;|\;\mathbf{c}_1\in C_1,\mathbf{c}_2\in C_2\right\} \). It is clear that \(\overline{C}=\left\{ \left( \mathbf{c}_1,0\right) \;|\;\mathbf{c}_1\in C_1\right\} \) whose square code has minimum distance \(d_1\). On the other hand, since \(C_2^{*2}\) has distance \(d_2\), let \(\mathbf{y}_2\in C_2^{*2}\) be a codeword with weight \(d_2\). Then, we have that \((\mathbf {0},p^2\pi (\mathbf{y}_2))\in C^{*2}\), and therefore the minimum distance of \(C^{*2}\) is at most \(d_2\). The desired result follows if we pick \(d_2\) to be a small number and \(d_1\) to a big number.

Unlike the distance and dual distance of the lifted code, strong multiplication does not automatically carry over. We now give a brief argument for uniformity, which shall be important when using our codes for secret sharing later on.

Lemma 3

Let \(C \subseteq R^n\) be a submodule, and let \(U \subseteq [n]\) be an index set with \(|U| \le d(C^{\perp }) - 1\). Then the projection \(C_U\) of C onto the coordinates of U equals the whole space \(R^{|U|}\).

Proof

We argue by contradiction. Note that \(C_U\) is also an R-module, so we may write \(C_U=\sum _{i=1}^{t}R\mathbf{x}_i\) with \(t\le |U|\). Here, \(C_U\) may be non-free. Let M be an \(t\times |U|\) matrix whose rows are \(\mathbf{x}_1,\ldots ,\mathbf{x}_t\). Recall \(\overline{M} = \pi (M)\) is the reduction of M modulo p.

We first show that if \(|C_U|<R^{|U|}\), then the rank of \(\overline{M}\) is less than |U|. It is obvious if \(t<|U|\). When \(t=|U|\), since \(|C_U|<R^{|U|}\), \(\mathbf{x}_1,\ldots ,\mathbf{x}_t\) are linearly dependent over R. Therefore, there exist \(\lambda _1,\ldots ,\lambda _t\in R\), not all equal to 0, such that \(\sum _{i=1}^{t}\lambda _i \mathbf{x}_i=0\). Let m be maximal such that \(p^m\) divides all of \(\lambda _1,\ldots ,\lambda _t\). Then, we have \(\sum _{i=1}^{t}\frac{\lambda _i}{p^m} \mathbf{x}_i=0\). This implies that \(\sum _{i=1}^{t}\pi (\frac{\lambda _i}{p^m})\pi (\mathbf{x}_i)=0\) over \(\mathbb {F} \) where \(\pi (\frac{\lambda _1}{p^m}),\ldots ,\pi (\frac{\lambda _t}{p^m})\in \mathbb {F} \) are not all zero. Therefore, \(\pi (\mathbf{x}_1),\ldots ,\pi (\mathbf{x}_t)\) are linearly dependent and the rank of \(\overline{M}\) is less than |U|.

Let \(\mathbf{c}^T\) be the nonzero solution to \(\overline{M}\mathbf{c}^{T}=\mathbf {0}\) over \(\mathbb {F} \). Then, we have \(M p^{k-1} \pi ^{-1}(\mathbf{c})^T=\mathbf {0}\) over R. Extend \(p^{k-1}\pi ^{-1}(\mathbf{c})^T\) to a vector \(\mathbf{c}'\) in \(R^n\) by setting i-th component with \(i\notin U\) to be zero. Clearly, \(\mathbf{c}'\) is a codeword of the dual code \(C^{\perp }\). However, \(w_H(\mathbf{c}')=w_H(\mathbf{c})\le |U|\) and a contradiction occurs.    \(\square \)

3.1 Constructing a Self-orthogonal Code over R

By a judicious choice of lift, we show that for \(p \ge 3\) we can preserve self-orthogonality of a code over \(\mathbb {F} \) when lifting to R.

Theorem 3

Assume that there is a [ntd] self-orthogonal code C over the finite field \(\mathbb {F}_{p^h} \) with dual distance \(d^{\perp }\) and \(p\ge 3\). Then, there is a [ntd] self-orthogonal code \(C_k\) with dual distance \(d^{\perp }\) over the Galois ring \(\mathsf {GR}(p^k, h)\) for any positive integer k. Moreover, given an explicit generator matrix of C the generator matrix of \(C_k\) is explicit.

Proof

We lift the self-orthogonal code C increasing k step by step. For each step, we specify the lifted code by its generator matrix. Define \(R_k:=\mathsf {GR}(p^k, h)\). By Definition 2, \(R_k\) contains \(\mathbb {Z}/p^k\mathbb {Z} \) as a subring, and its residue field is \(\mathbb {F}_{p^h} \).

Our first step is to lift self-orthogonal code from \(\mathbb {F}_{p^h} \) to \(R_2=\mathsf {GR}(p^2, h)\). Let C be an [ntd] self-orthogonal code over \(\mathbb {F}_{p^h} \) and \(\overline{G}=\begin{pmatrix} \overline{I}&\overline{A} \end{pmatrix}\)Footnote 6 be the generator matrix of C. Due to the bijection between \(\mathcal {I}\) and \(\mathbb {F}_{p^h} \), we could find a matrix \(G=\begin{pmatrix} I&A \end{pmatrix}\) with \(G \in \pi ^{-1}(\overline{G})\) whose entries are in \(\mathcal {I}\). Self-orthogonality of C implies that

$$\begin{aligned} GG^T=AA^T+I=\overline{A}\times \overline{A}^T+\overline{I}=0 \pmod p. \end{aligned}$$

That means that all the entries in \(GG^T\) are elements in the ideal \(pR\). By Remark 1, we can find a matrix \(S_1\) over \(\mathcal {I}\) such that \(I+AA^{T}=pS_1 \pmod p^2\). It is clear that we can choose \(S_1\) to be symmetric. Note that 2 is a unit in \(R_k\) as \(p\ne 2\) and we can define \(A_1=A+2^{-1}pS_1A\). Let \(G_1=\begin{pmatrix} I&A_1 \end{pmatrix}\) and let \(C_1\) be the code whose generator matrix is \(G_1\). Obviously, \(G_1\) is defined over \(R_2\). Next, we show that \(C_1\) is indeed a self-orthogonal code over \(R_2\). To see this, we have

$$\begin{aligned} G_1G_1^{T}= & {} I+AA^T+\frac{p}{2}(S_1AA^T+AA^TS_1)\\= & {} pS_1+\frac{p}{2}S_1(pS_1-I)+\frac{p}{2}(pS_1-I)S_1\\= & {} pS_1-pS_1 =0 \pmod {p^2}. \end{aligned}$$

The first equality follows from the fact that \(S_1\) is a symmetric matrix. It remains to bound the minimum distance of \(C_1\). Observe that the reduced code of \(C_1\) is C. By Lemma 1, the distance of \(C_1\) is lower bounded by that of C. We can apply the same argument to its dual distance by observing that the generator matrix of \(C_1^\perp \) is \(\begin{pmatrix} -A_1^T&I\end{pmatrix}\), whose reduction modulo p, the matrix \(\begin{pmatrix} -A^T&I\end{pmatrix}\), is the generator matrix of \(C^\perp \), and therefore \(C_1\) is free. Now, \(C_2\) is a self-orthogonal code over \(R_2\) satisfying all the claims in our theorem. In a same manner, we can the lift code \(C_2\) to a code \(C_3\) over \(R_3\). By induction, we obtain a code \(C_k\) over \(R_k\) for any \(k\ge 1\) satisfying all the claims in our theorem.    \(\square \)

Note that a self-dual code is also a self-orthogonal code. Theorem 3 together with Proposition 2 gives the following.

Corollary 1

Let \(\varepsilon > 0\) be any small constant, k any positive integer and \(p^h \ge \frac{4}{\varepsilon ^2}\) be any square with p an odd prime. Then there exists an explicit family of self-dual codes over Galois ring \(\mathsf {GR}(p^k, h)\) with relative distance \(\delta \ge \frac{1}{2}-\varepsilon \).

3.2 Code and Dual Code over R

In our last subsection, we constructed a self-orthogonal code C over the Galois ring \(\mathsf {GR}(p^k, h)\) with \(p\ge 3\), by lifting a self-orthogonal code over the finite field \(\mathbb {F}_{p^h} \). We may use these to construct an arithmetic secret-sharing scheme, as we will see in Section 4. However, our technique only works for \(p \ge 3\), and of course especially for MPC purposes the case \(p = 2\) is also very interesting. The existence of asymptotically good self-orthogonal codes over these rings is not yet known. To get around this obstacle, we replace the self-orthogonal code with code and its dual code in our secret-sharing scheme. This will incur the cost of doubling the share size, and hence doubling the communication complexity of the MPC protocols build on top of it.

The following is dedicated to lifting a code together with its dual code from the finite field \(\mathbb {F}_{p^h} \) to the Galois ring \(\mathsf {GR}(p^k, h)\). Our lifting technique maintains the minimum distance of our code and its dual code.

Theorem 4

Assume that there is a [ntd] linear code C over the finite field \(\mathbb {F}_{p^h} \) with dual distance \(d^{\perp }\). Then, there is a [ntd] linear code \(C_k\) with dual distance \(d^{\perp }\) over the Galois ring \(\mathsf {GR}(p^k, h)\), for any integer k. Moreover, the generator matrices of \(C_k\) and its dual code are explicit as long as the generator matrix of C is explicit.

Proof

Let G and H be the generator matrix and parity check matrix, respectively, of C. Note that H is also the generator matrix of \(C^{\perp }\), the dual code of C over \(\mathbb {F}_{p^h} \). We have \(GH^T=0 \pmod p\) and thus \(GH^T=pM \pmod {p^2}\), for some matrix M defined over \(\mathbb {F}_{p^h} \). Since G is a generator matrix of C, its rank is t. There exists \((n-t)\times n\) matrix \(A_1\) such that \(GA^T_1=-M \pmod p\). It follows that \(G(H+pA_1)^T=GH^T+pGA^T_1=0 \pmod {p^2}\).

Let \(C_2\) be the linear code over \(\mathsf {GR}(p^2, h)\) with generator matrix G. We claim that the dual code \(C_2^{\perp }\) of \(C_2\) has generator matrix \(H+pA_1\). By Lemma 2, the dual code \(C_2^{\perp }\) has dimension \(n-t\). To see this, we first note that \(H+pA_1\) has rank \({{\,\mathrm{rank}\,}}_{\mathbb {F}_{p^h}}(H)=n-t\) due to Proposition 4. Moreover, any codeword generated by \(H+pA_1\) is a solution to \(G\mathbf{x}=0\) over \(R_2\) since \(G(H+pA_1)^T=0 \pmod {p^2}\).

These two facts lead to the conclusion that \(H+pA_1\) is indeed the generator matrix of \(C_2^{\perp }\) over \(\mathsf {GR}(p^2, h)\). The distance and dual distance comes from Lemma 1 and Lemma 2. In the same manner, one can show that \(C_k\) is a linear code over \(\mathsf {GR}(p^k, h)\) with generator matrix G for any \(k\ge 1\). In the meantime, by Lemma 1 the minimum distance and dual distance of \(C_k\) are lower bounded by d and \(d^{\perp }\) respectively. The dual code of \(C_k\) is specified by its generator matrix \(H+pA_1+\cdots +p^{k-1}A_{k-1}\).    \(\square \)

Theorem 4 combined with Proposition 2 gives the following result.

Theorem 5

Let \(\varepsilon > 0\) be any small constant and \(p^h \ge \frac{4}{\varepsilon ^2}\) be any square. There exists an explicit family of codes over the Galois ring \(\mathsf {GR}(p^k, h)\) with relative distance \(\delta \ge \frac{1}{2}-\varepsilon \) and relative dual distance \(\delta ^{\perp }\ge \frac{1}{2}-\varepsilon \) for any integer k.

4 Arithmetic Secret-Sharing over Galois Rings

In this section we construct an arithmetic secret-sharing scheme over a Galois ring R starting from an R-linear code C together with its dual \(C^\perp \), by extending techniques from [13]. In this section, let \(R = \mathsf {GR}(p^k, h)\), and suppose \(C \subseteq R^{n+1}\) is a linear code with distance d and dual distance \(d^\perp \). We first provide a brief overview of the techniques, before fixing the slightly heavier notation in Sect. 4.1 that we use to write the protocols in the remaining sections of this paper.

As for nomenclature, note that the difference between arithmetic and linear secret sharing is that the former is an LSSS with multiplication. We say an LSSS has multiplication if there exists a multiplication operator \(*\) on shares, such that given secrets x and y with respective share vectors \((x_1,\ldots ,x_n)\) and \((y_1,\ldots ,y_n)\) then the product \(x\cdot y\) is linearly determined by the \(*\)-products of shares \(x_1 *y_1, \dots , x_n *y_n\). Here we are explicit about the operator \(*\) because in the arithmetic secret-sharing scheme that we construct, the shares are not elements of R, but rather each share is given by 2 elements in R. These pairs of R-elements form an R-algebra with the operator \(*\), which we define below.

Informally, a secret-sharing scheme has t-privacy if for any share vector, any t coordinates are independent of the secret, and it has r-reconstruction if any r coordinates of a share vector jointly determine the secret. For a full formalization of an arithmetic secret-sharing scheme over R, we refer to the full version of our paper [1].

Via Massey’s construction [25] we may obtain an LSSS from a code over a field with good parameters, and this generalizes to Galois rings, as follows. To share \(s\in R\), we sample a codeword \(\mathbf{c}=(s,c_1,\ldots ,c_n)\in C\) uniformly at random and let \(c_i\) be the i-th share. Due to properties of the dual distance \(d^{\perp }\), we can show that for any subset \(T\subseteq [n]\) with \(|T|\le d^{\perp }-2\) and \(s\in R\), \(\{(c_i)_{i\in T}: (s,c_1,\ldots ,c_n)\in C\}=R^{|T|}\). This implies \((d^{\perp }-2)\)-privacy. From the minimum distance of C it follows that the LSSS has \((n-d+1)\)-reconstruction.

To use a secret-sharing scheme for MPC, we need the multiplicative property. The LSSS constructed above has multiplication if and only if its square code \(C^{*2}\) has minimum distance \(d(C^{*2})\ge 1\). Unfortunately, the codes from Theorem 5 do not satisfy this property. However, by simultaneously secret-sharing values in C and in the dual code \(C^\perp \), we can obtain multiplication with the following construction from [13].

To secret-share \(s\in R\), we sample a codeword \(\mathbf{x}=(s,x_1,\ldots ,x_n)\in C\) and a codeword \(\mathbf{y}=(s,y_1,\ldots ,y_n)\in C^{\perp }\) uniformly at random. The i-th share is now a pair \((x_i, y_i)\). The privacy of this scheme is \(\min \{d-2,d^{\perp }-2\}\) and it is \(\min \{n-d+1,n-d^{\perp }+1\}\)-reconstruction. Now suppose we have another secret-shared element \(u\in R\) shared as \(\mathbf{x}'=(u,x'_1,\ldots ,x'_n)\in C\) and \(\mathbf{y}'=(u,y'_1,\ldots ,y'_n)\in C^\bot \). For the product su, we see that \(\sum _{i=1}^{n} x_iy'_i=-su\) (and also \(\sum _{i=1}^{n} y_ix'_i=-su\)).

4.1 Formalization

We now formalize the scheme and define the notation which we shall use in the remaining sections. Recall C is of length \(n+1\). Let \(\widetilde{C}\subseteq R^n\) denote the projection of C onto its last n coordinates, and similarly for \(\widetilde{C^\perp }\subseteq R^n\). Let \(\psi :\widetilde{C}\rightarrow R\) be the R-module homomorphism given by \(\psi (x_1,\ldots ,x_n) = x\) where \(x\in R\) is the unique element such that \((x,x_1,\ldots ,x_n) \in C\). Note that this map is well-defined if \(d \ge 2\). Similarly define \(\psi ':\widetilde{C^\perp }\rightarrow R\) as \((x'_1, \dots , x'_n) \mapsto x'\). We equip \(R \oplus R\) with the product \((a,b)\star (c,d) = (a d, b c)\); this defines an R-algebra which we denote A.

Consider the R-submodule of \(A^n\) given by

$$D = \{((x_1,x_1'),\ldots ,(x_n,x_n')) \;|\;\mathbf{x}\in \widetilde{C}, \mathbf{x}'\in \widetilde{C^\perp },\psi (\mathbf{x}) = \psi '(\mathbf{x}')\}\subseteq A^n,$$

and define the map \(\psi :D\rightarrow R\) by \(((x_1,x_1'),\ldots ,(x_n,x_n'))\mapsto \psi (\mathbf{x}) (= \psi '(\mathbf{x}'))\). We may think of D as the space of consistent sharings, and \(\psi \) as the map that reconstructs the secret. For \(s\in R\) we write \([s]\) to denote an element of D that maps to s under \(\psi \).

When we use the secret-sharing scheme in the protocol, we also occasionally need to operate on publicly known values. Let be a fixed publicly known sharing of \(1 \in R\). A public value \(x \in R\) can be associated with the canonical sharing \(x \theta \in D\).

Now consider the R-module homomorphism \(\phi :R^n\rightarrow R\) given by \(\phi (\mathbf{x}) = -\sum _{i=1}^nx_i\). Define the R-submodule of \(A^n\) given by

$$M = \{((x_1,x_1'),\ldots ,(x_n,x_n')):\phi (\mathbf{x}) = \phi (\mathbf{x}')\}\subseteq A^n,$$

which intuitively corresponds to redundant additive shares. The reason why we have the redundancy will be made clear in a moment, but at a high level it exists due to the fact that additive shares of the product of two \([\cdot ]\)-shared secrets can be obtained in two different ways. As we did with D, we define the R-module homomorphism \(\phi :M\rightarrow R\) given by \(((x_1,x_1'),\ldots ,(x_n,x_n'))\mapsto \phi (\mathbf{x})( = \phi (\mathbf{x}'))\), and for \(s\in R\) we write \(\langle s\rangle \) to denote an element of M that maps to s under \(\phi \).

For \(\textit{\textbf{x}},\textit{\textbf{y}}\in A^n\) we define \(\textit{\textbf{x}}*\textit{\textbf{y}}\) as the point-wise product of these vectors (under the product in A, which is \(\star \)). We define

$$D^{*2} = \mathsf {span}_R\{\textit{\textbf{x}}*\textit{\textbf{y}}\;|\;\textit{\textbf{x}},\textit{\textbf{y}}\in D\}\subseteq A^n,$$

which corresponds at a high level to the operations we performed in the previous paragraphs to obtain additive shares of the product of two secrets.

Proposition 5

Let \(\textit{\textbf{x}},\textit{\textbf{y}}\in D\). Then \(\textit{\textbf{x}}*\textit{\textbf{y}}\in M\) and moreover \(\phi (\textit{\textbf{x}}*\textit{\textbf{y}}) = \psi (\textit{\textbf{x}})\cdot \psi (\textit{\textbf{y}})\).

Proof

Write \((x_i, x'_i)\) and \((y_i, y'_i)\) for the i-th entry of \(\textit{\textbf{x}}\) and \(\textit{\textbf{y}}\), respectively, for \(i = 1, \dots , n\). The i-th entry of \(\textit{\textbf{x}}*\textit{\textbf{y}}\) is \((x_i y'_i, x'_i y_i)\), via the \(\star \)-product. There exists \((x_0, x_1, \dots , x_n) \in C\) and \((y'_0, y'_1, \dots , y'_n) \in C^\perp \), hence \(\sum _{i=1}^n x_i y'_i = -x_0 y'_0 = -\psi (\mathbf{x}) \psi (\mathbf{y}')\). Similarly, there exists \((x'_0, x'_1, \dots , x'_n) \in C\) and \((y_0, y_1, \dots , y_n) \in C^\perp \), hence \(\sum _{i=1}^n x'_i y_i = -x'_0 y_0 = -\psi (\mathbf{x}') \psi (\mathbf{y})\). The claim follows.    \(\square \)

In terms of shares, we may write the proposition above as \([x]*[y] = \langle x\cdot y\rangle \). We obtain the following properties.

Theorem 6

The scheme above \((n-d+2)\)-reconstruction and \((d(\overline{C}^{\perp }) - 2)\)-privacy.

Proof

is a well-defined R-module homomorphism. Also is surjective, since by Lemma 3 the projection of C onto the zero-th coordinate (corresponding to the secret) is surjective. The map \(\phi : D^{*2} \rightarrow Z\) is surjective and satisfies .

If \(U \subseteq \{0, \dots , n\}\) is an index set of cardinality \(d(\overline{C}^{\perp }) - 2\) then projecting C onto \(\{0\} \cup U\) is uniform by Lemma 3, and privacy follows. If \(\textit{\textbf{x}}\in D\) has \(\textit{\textbf{x}}_U = \mathbf {0}\) for \(|U| = n-d+2\) then since the only codeword in C with weight \(\le n-(n-d+2) + 1 = d - 1\) is \(\mathbf {0}\), we have , and reconstruction follows.    \(\square \)

As a corollary, by instantiating these codes with the ones we obtained in Corollary 1, we get our main result.

Theorem 7

Let \(\varepsilon > 0\), and let h be an integer such that \(p^h \ge \frac{4}{\varepsilon ^2}\). Then there exists a family of R-ASSS \(\varSigma _1, \varSigma _2, \dots \) with \(R = \mathsf {GR}(p^k, h)\), such that the number of players \(n(\varSigma _i) \rightarrow \infty \), and the schemes have \(t(\varSigma _i) \ge (1/2 - \varepsilon ) n(\varSigma _i)\) privacy and \(r(\varSigma _i) \ge (1/2 - \varepsilon ) n(\varSigma _i)\) reconstruction.

5 Passive Security

In this and the upcoming sections, we fix \(\varepsilon > 0\) and consider the Galois ring R of degree \(h = \varOmega (\log _p(\varepsilon ^{-1}))\) over \(\mathbb {Z}/p^k\mathbb {Z} \). We consider the family of LSSS over R from Theorem 7. We reuse the notation from Sect. 4.1: fixing \(n\in \mathbb {N}\), we denote by \([x]\) the shares of a secret element \(x\in R\), and each of these shares belong to the share space \(A = R^2\). We denote by \(\langle x\rangle \) shares under the “square” secret-sharing scheme, and recall that given \([x]\) and \([y]\), the parties can perform local computation on their shares to obtain \(\langle x\cdot y\rangle \), and we denote this by \(\langle x\cdot y\rangle = [x]*[y]\). Whenever we say that parties reconstruct a secret \([x]\) (or \(\langle x\rangle \)), we mean that the parties send their shares to \(P_1\), who uses the reconstruction function to compute x and then sends x to all other parties.

To get a passively secure protocol with perfect security we use the standard approach in MPC of preprocessing some data that can be used to handle multiplication gates efficiently. We follow the template from [17], except that instead of using Reed-Solomon codes, which would lead to a complexity of \(O(n \log (n))\), we use our linear secret-sharing scheme \([\cdot ]\), allowing us to obtain complexity linear in the number of players.

The techniques from [17] consist, in general, of four main phases:

  1. 1.

    The parties generate “random double-sharings” in a preprocessing phase.

  2. 2.

    The parties use the preprocessed material to distribute inputs.

  3. 3.

    The parties compute the circuit in a gate-by-gate basis. Addition gates are computed locally. Multiplication gates make use of the double-sharings.

  4. 4.

    The output wires are reconstructed towards the parties.

Most of these techniques extend seamlessly to the R setting. The biggest issue lies in the generation of the random double-sharings, which uses a Vandermonde matrix in order to achieve linear complexity, and although these matrices do exist over \(R = \mathsf {GR}(p^k, h)\) if \(h = \varOmega (\log (n))\) [2], our goal here is to avoid this overhead. In Sect. 5.1, we show how to get around this issue by moving to a Galois ring extension.

The protocol we describe in the next few subsections proves the following theorem.

Theorem 8

For every \(n,p,k\in \mathbb {N}\), with p a prime, for every \(\varepsilon >0\) and for every arithmetic circuit C over \(R = \mathsf {GR}(p^k,h)\) with \(h = \varOmega (\log _p(\varepsilon ^{-1}))\), there exists an n-party MPC protocol that securely computes C against an unbounded semi-honest adversary corrupting up to \(t<\left( \frac{1}{2}-\varepsilon \right) \cdot n\) players with a communication complexity of \(O(k\cdot \log p\cdot h\cdot |C|\cdot n)\).

For constant \(p,k,\varepsilon \), and by embedding \(\mathbb {Z}/p^k\mathbb {Z} \) in R, we obtain the following as a simple corollary.

Theorem 9

For every \(n\in \mathbb {N}\) and for every arithmetic circuit C over \(\mathbb {Z}/p^k\mathbb {Z} \) there exists an n-party MPC protocol that securely computes C against an unbounded semi-honest adversary corrupting up to \(t<\left( \frac{1}{2}-\varepsilon \right) \cdot n\) players with an amortized communication complexity per multiplication gate of O(n).

5.1 Offline Phase

As preprocessed material the parties need many shares of the form \(([r],\langle r\rangle )\), where \(r\in R\) is uniformly random. The basic template used in the literature to achieve this comes from [17], and it uses the fact that Vandermonde matrices are good randomness extractors. However, we cannot use these matrices in our setting since they require the prime p to be at least n, which is not the case for us. Naively, one can use a Galois ring extension in which these matrices exist, as in [2], but this would lose linear complexity. There are two solutions to this problem.

One solution is instead of a hyperinvertible matrix to use the generator matrix of a [nud] linear code over R, with \(d \ge t + 1\). This yields u random elements at the cost of \(n^2\) elements of R communicated, which if the rate and distance are linear in n leads to linear complexity. By Theorem 5 we know such codes exist.

The second solution is to move to a Galois ring extension S with high enough Lenstra constant, such that there is a non-singular \(n \times n\) Vandermonde matrix. Instead of simply embedding \(R \hookrightarrow S\), we use a tensor product \(R^s \cong R \otimes _R S \cong S\), where s is the degree of the extension [2, 9]. We can take the tensor product of the secret-sharing scheme; the result is a secret-sharing scheme that can be interpreted as s parallel sharings of R. In this way \(n-t\) random elements of S can be obtained at the cost of \(n^2\) elements of S communicated. Since each random sharing of S can be interpreted as s random sharings of R, this leads to linear communication per random sharing.

5.2 Online Phase

Now we describe how the parties can securely compute any circuit assuming they have preprocessed enough random sharings \(([r], \langle r\rangle )\).

figure a

The complexity of the protocol above is dominated by the reconstructions in the multiplication gates. Each such reconstruction involves sending O(n) elements in A. Since these elements have bit-length \(O(k\cdot \log (p)\cdot h)\), the overall complexity of these reconstructions is \(O(k\cdot \log (p)\cdot h\cdot |C|\cdot n)\).

6 Active Security with Abort

Even though we present an actively secure protocol with guaranteed output delivery in Sect. 7, it is still worth mentioning that a much simpler protocol can be envisioned if one is aiming for security with abort.

Our starting observation is that the online multiplication protocol presented previously is secure up to additive attacks, as defined in [20], or, put more precisely, the only attack that an active adversary can carry out is to cause the result of the multiplication to be wrong by an additive amount that is known by him and that is completely independent of the inputs. To see why this is the case, we observe that if the preprocessed pair \(([r],\langle r\rangle )\) is correctly shared, then the only thing that the adversary can do in the online phase is broadcastingFootnote 7 an incorrect difference \(r-xy+\delta \) (assuming that \(P_1\) is corrupted), but the effect of this is that the final shares the parties get are \([xy+\delta ]\), which constitutes an additive attack. Furthermore, the preprocessed pairs can be guaranteed to be consistent by a simple extension to the preprocessing protocol in Sect. 5.1 that adds a consistency check at the end (for instance as in done in [2] or in [12]).

Very recently it was shown in [3] how to compile any protocol over rings that is secure up to additive attacks to an actively secure protocol. Given that our multiplication protocol satisfies this condition (and it can be verified that it satisfies the other conditions required by the compiler), we obtain an actively secure protocol by feeding our protocol from the previous section through the compiler from [3]. The resulting protocol has linear communication in the number of parties.

7 Active Security with Guaranteed Output Delivery

The main theorem we prove in this section is the following.

Theorem 10

For every \(n,p,k\in \mathbb {N}\), with p a prime, for every \(\varepsilon >0\) and for every arithmetic circuit C over \(R = \mathsf {GR}(p^k,h)\) with \(h = \varOmega (\log _p(\varepsilon ^{-1}))\), there exists an n-party MPC protocol that securely computes C with guaranteed output delivery against an unbounded active adversary corrupting up to \(t<\left( \frac{1}{2}-\varepsilon \right) \cdot n\) players, with negligible failure probability in \(\kappa \in \mathbb {N}\), offline communication complexity of \(O(k\cdot \log p\cdot (h\cdot |C|\cdot n\cdot \log (n) + n^7\cdot \kappa ))\), and online communication complexity of \(O(k\cdot \log p\cdot h\cdot |C|\cdot n)\).

Typically, we regard pk and \(\varepsilon \) (and therefore h) as constants, so that the only variables are nC and \(\kappa \). In this case, we see that the amortized complexity per multiplication is O(n) for the online phase, and \(O(n\log (n))\) for the offline phase. Furthermore, computation over \(\mathbb {Z}/p^k\mathbb {Z} \) can be obtained by embedding the computation into a Galois ring R of constant degree h, and adding a check of input correctness as in [2]. The following theorem is thus obtained as a corollary.

Theorem 11

For every constants \(p,k\in \mathbb {N}\), with p a prime, every constant \(\varepsilon >0\), and for every arithmetic circuit C over \(\mathbb {Z}/p^k\mathbb {Z} \) there exists an n-party MPC protocol that securely computes C with guaranteed output delivery against an unbounded active adversary corrupting up to \(t<\left( \frac{1}{2}-\varepsilon \right) \cdot n\) players, with negligible failure probability in \(\kappa \), amortized offline communication complexity of \(O(n\log (n))\) per multiplication gate and amortized online communication complexity of O(n) per multiplication gate.

The rest of this section is devoted to proving Theorem 10. We do so by adapting the protocol from [6] over fields, which we refer to as the BFO protocol, to work over a Galois ring R, while also making use of our LSSS from Sect. 4. Due to space constraints, we only detail the most essential modifications to the BFO protocol, and assume some of the terminology from [6] as given. An overview of the BFO protocol and more details can be found in the full version of this paper  [1].

In order to extend the BFO protocol to our setting while preserving its efficiency, we mostly need to adapt the preprocessing phase. Arguments regarding dispute control carry over immediately, since they are essentially combinatorial in nature. In the next sections we discuss how to adapt the preprocessing: the verification of multiplication triples is in Sect. 7.4, and the computation of the tags is sketched in Sect. 7.3. Additionally, the fact that these tags provide the required authentication features when instantiated over Galois rings is not trivial, and we discuss this thoroughly in Sect. 7.3.

We stress that our goal here is not to present a full-fledged self-contained MPC protocol, but rather to describe our novel techniques and extensions to the BFO protocol. Hence, we assume familiarity with the work of [6] and we omit most of its heavy machinery, especially everything that extends seamlessly to Galois rings. We also remark that, even though we assume the existence of a broadcast channel implicitly (as the dispute control layer requires it), our complexity analysis does not include the cost of these broadcasts, which is equal to the corresponding cost in [6] and is independent of the circuit size.

Finally, we notice that the techniques from [22], which improve the complexity of the protocol from [6] by removing an additive term of \(n^2d\), where d is the depth of the circuit, rely mostly on the batch triple check from [6], which we extend in Sect. 7.4 to the Galois ring setting. Hence, the optimizations from [22] can be also applied to Galois rings, resulting in a much more efficient protocol that does not have a quadratic communication complexity in terms of the numbers of parties and the depth of the circuit.

7.1 Different Types of Shares

From now on, we fix \(R = \mathsf {GR}(p^k,h)\) and \(S = \mathsf {GR}(p^k,\kappa )\). Notice that we may view S as an extension of R of degree \(\kappa /h\). The BFO protocol follows the template from Sect. 5, except that it has an additional mechanism to ensure that whenever the adversary cheats this can be detected and the computation can continue. This is achieved by using different types of secret-sharings (especially 2-level sharings, defined below), which create enough “redundancy” for the parties to be able to interactivelyFootnote 8 correct any error the adversary may introduce.

The multiple types of sharings considered for our extension of the BFO protocol are found below—for the intuition on these definitions we refer the reader to [6]. Note that these sharings were originally defined purely in the context of Shamir’s secret-sharing scheme. We plug in the family of LSSS over R from Theorem 7 and get a more general setting: not only because our LSSS is defined over a Galois ring, but also because it does not have information rate 1, i.e., the shares do not have the same size as the secret.

  • Single sharing. These are the sharings \([x]\) as defined using our LSSS. The secret space is R, and the share space is A. They are the analogue to the degree-t Shamir sharings from [6].

  • Square sharing. These are the shares \(\langle x\rangle \) under the “square” secret-sharing scheme. The secret space is R, and the share space is A. As in Sect. 5, they are the analogue to the degree-2t Shamir sharings from [6].

  • Twisted single sharing. These are defined with respect to a coordinate \(i\in \{1,\ldots ,n\}\). Let \(x\in A\). We denote by \(\lceil x \rfloor ^{i}\) an element \(\textit{\textbf{x}}= (x_1,\ldots ,x_n)\in D\) such that \(\psi (\textit{\textbf{x}}) = 0\) and \(x_i = x\). One may view this as a sharing of 0 such that i-th share equals \(x\).

  • Twisted square sharing. These are defined with respect to a coordinate \(i\in \{1,\ldots ,n\}\). Let \(x\in A\). We denote by \(\langle x \rangle ^{i}\) an element \(\textit{\textbf{x}}= (x_1,\ldots ,x_n)\in M\) such that \(\phi (\textit{\textbf{x}}) = 0\) and \(x_i = x\). One may view this as square sharing of 0 such that the i-th share equals \(x\).

  • Two-level single sharing. The secret space is R and the share space is \(A^n\). For \(x\in R\), we define \(\llbracket x \rrbracket \) as an \(n \times n\) matrix \((x_{i,j})_{i=1, \dots , n}^{j=1, \dots , n} \in A^{n \times n}\), such that:

    1. 1.

      The j-th share is the j-th column.

    2. 2.

      Each i-th row \(\textit{\textbf{x}}_i = (x_{i,1}, \dots , x_{i,n})\) is a vector in D, i.e., it constitutes a single sharing \([x_i]\) of some element \(x_i \in R\).

    3. 3.

      We have \(x_1 + \dots + x_n = x\).

  • Two-level square sharing. Denoted \(\langle \!\langle x \rangle \!\rangle \). It is identical to a two-level single sharing, except the rows are vectors in M, and hence constitute square sharings \(\langle x_i\rangle \).

7.2 Secret Sharing over a Galois Ring Extension

In [6], some subprotocols need a field size that is exponential in the security parameter in order to ensure negligible cheating probability. To this end, most of the protocol is defined over a smaller field, but occasionally they move to a large field extension, in a way such that the overall complexity is not negatively affected. Over fields and using Shamir secret sharing, it is straightforward to use shares defined over the base field and the extension field together, since the arithmetic is compatible. For our protocols, we use a Galois ring extension and we show that the arithmetic is compatible as well.

Let L be a Galois ring extension of R of degree r, i.e., \(L = GR(p^k, h \cdot r)\). Intuitively, the secret-sharing scheme \([\cdot ]\) (and similarly for \(\langle \cdot \rangle \)) over R can be extended to L as follows. First, fix an R-basis \(\omega _1, \dots , \omega _r\) of L. To secret-share an element \(\alpha \in L\), write \(\alpha = \sum _{i=1}^r a_i \cdot \omega _i\), and set \([\alpha ]_L := ([a_1], \dots , [a_r])\). More details can be found in the full version of this paper  [1].

7.3 Authentication Tags

In the BFO protocol, whenever some cheating is detected, parties resort to dispute control in order to partially identify the cheater. One of the critical points in which the adversary can cheat in the protocol is when sending shares in order to reconstruct shared values, since in principle any corrupt party can lie about its own share. In order to be able to detect who sent a wrong share, the parties need an additional mechanism that somehow “binds” a party to its own share. This is precisely the purpose of the two-level shares defined in Sect. 7.1: the share of each party \(P_i\) is also shared among the other parties, so the parties can check whether \(P_i\) is lying about its share by reconstructing it from the two-level shares.

Unfortunately, nothing prevents the parties to also lie in the reconstruction of the two-level shares themselves. In order to deal with this situation, authentication tags are put in place, which allow a party to announce a share and prove that it is correct, or more precisely, prove that it is the same share that was created at the beginning of the protocol, which was guaranteed to be correct.

At a high level, the tags over fields in the BFO protocol work as follows.Footnote 9 Consider a value \(s\in \mathbb {F}_{q} \) that is shared as \([s] = (s_1,\ldots ,s_n)\in \mathbb {F}_{q} ^n\) using Shamir LSSS. Player \(P_i\) holds share \(s_i\in \mathbb {F}_{q} ^n\), and to prevent him from lying about his share, \(P_i\) is given a tag \(\tau = \mu \cdot s_i + \nu \), where the key \(\mu ,\nu \in \mathbb {F}_{q} ^n\) is random and only known by some verifier \(P_j\). At the time of opening, \(P_i\) has to present a share \(s_i' = s_i + \delta \) plus a tag \(\tau ' = \tau + \Delta \), where \(\delta ,\Delta \in \mathbb {F}_{q} \) may be nonzero for the case of a corrupt \(P_i\), and the verifier \(P_j\) checks whether \(\tau ' {\mathop {=}\limits ^{?}} \mu \cdot s_i' + \nu \). This check passes if and only if \(\Delta = \mu \cdot \delta \). If \(P_i\) attempts to cheat (i.e., \(\delta \ne 0\)) and if the verifier \(P_j\) is honest, then \(P_i\) does not know the random \(\mu \), and therefore check must fail with high probability (assuming the field is large). This can be seen by using that \(\delta \ne 0\) is invertible, so \(\Delta \cdot \delta ^{-1} = \mu \), which due to the randomness of \(\mu \) cannot be satisfied.

Adapting this to our setting is not straightforward because of two reasons. First, Galois rings are not fields for \(k > 1\) and therefore the argument above does not apply directly, since \(\delta \ne 0\) need not be invertible. Fortunately, using the ideas from [2] we still can show that the equation \(\Delta = \mu \cdot \delta \) holds with negligible probability. However, the second issue is more delicate and it has to do with the fact that in our setting each share in \([s]\) is not a single Galois ring element but it is actually an element of \(A = R^2\).

We handle this second issue by extending the authentication scheme from above not only from \(\mathbb {F}_{q} \) to R, but to A. At a high level, the tag corresponding to a share \(s_i\in A\) is computed as \(\tau = \mu \star s_i + \nu \in A\), for the key \(\mu ,\nu \in A\). Cheating in this new MAC scheme corresponds to solving equations of the form \(\Delta = \mu \star \delta \), for some \(\Delta ,\delta \in A\), which intuitively cannot be satisfied since it corresponds to two similar equations over R. We develop the details in what follows.

Definition and Properties of the Tags. We use the same template as the MAC scheme from [6], which authenticates batches instead of individual values. Let \(\{(s_{j,1},\ldots ,s_{j,\kappa /h})\}_{j=1}^\ell \in (R^h)^\ell \). Recall from Proposition 3 that \(R^{\kappa /h}\cong S\), so we may think of each \((s_{j,1},\ldots ,s_{j,\kappa /h})\) as one single element \(\sigma _j\in S\). Following Sect. 7.2, we consider shares \([\sigma _j]_S\) which can be obtained by sharing each of its coordinates as \([s_{j,i}]\). By writing \([s_{j,i}] = (s_{j,i,1},\ldots , s_{j,i,n})\in D^n\) and considering the vector \((s_{j,1,w},\ldots ,s_{j,\kappa /h,w})\in A^{\kappa /h}\) for \(j\in \{1,\ldots ,\ell \}\) and \(w\in \{1,\ldots ,n\}\), which we identify with an element \(\sigma _{j,w}\in A_S\) where \(A_S = \mathsf {span}_S(A)\), we can see that \([\sigma _j]_S = (\sigma _{j,1},\ldots ,\sigma _{j,n})\in (A_S)^n\).

Notice that the S-algebra \(A_S\) can be seen simply as \(S^2\), with the product operation defined as \((\alpha ,\alpha ')\star (\beta ,\beta ') = (\alpha \cdot \beta ', \alpha '\cdot \beta )\). With this in hand we can define what it means for the shares of \(\sigma \) to be authenticated.

Definition 3

(Informal.)Footnote 10 We say that the \(\ell \cdot \frac{\kappa }{h}\) shares \(\{[s_{j,i}]\}_{j=1,i=1}^{\ell ,\kappa /h}\) are authenticated if for every pair of players \(P_u,P_v\) the following holds:

  • \(P_v\) has a random key \(\varvec{\mu }\in (A_S)^\ell \) and \(\nu \in A_S\).

  • \(P_u\) has a tag \(\tau \in A_S\)

  • \(\tau = \varvec{\mu }\odot \varvec{\sigma } + \nu \), where \(\varvec{\sigma } = (\sigma _{1,u},\ldots ,\sigma _{\ell ,u})\in (A_S)^\ell \) and \(\odot \) denotes the dot product operator.

Proposition 6 argues that the tags defined above serve their purpose, i.e. a corrupt \(P_u\) cannot lie about any of his shares \(s_{j,i,u}\) and still present a valid tag without an honest \(P_v\) detecting this. The proof follows a similar argument as the one sketched before over fields for the BFO protocol. However, we first need to show that the S-algebra \(A_S\), even though it is not a field, and not even a Galois ring, does have good properties in terms of roots of linear equations. This is shown in the following lemma, which can be seen as an analogue of Lemma 6 to the S-algebra \(A_S\), but considers multivariate polynomials of degree 1.

Lemma 4

Let \(L = \mathsf {GR}(p^k,r)\) and let \(B = L^2\) be the L-algebra with multiplication given by \((\alpha ,\alpha ')\star (\beta ,\beta ') = (\alpha \beta ', \alpha '\beta )\). Let \(\varvec{\alpha }\in B^\ell \) and \(\gamma \in B\). If \(\varvec{\alpha }\ne 0\), then \(\Pr _{\varvec{\beta }\leftarrow B^\ell }[\varvec{\alpha }\odot \varvec{\beta } = \gamma ]\le \frac{\ell }{p^r}\).

Proof

Suppose that \((\alpha _1,\ldots ,\alpha _\ell )\odot (\beta _1,\ldots ,\beta _\ell ) = \gamma \), and suppose that \(\varvec{\alpha }\ne 0\). Without loss of generality, assume that \(\alpha _1\ne 0\), so \(\alpha _1\star \beta _1 = \rho \), with \(\rho = \gamma - \sum _{j=2}^\ell \alpha _j\star \beta _j\). Let \(\pi _1, \pi _2\) be the canonical L-algebra homomorphisms \(B \rightarrow L\) of projection onto the first and second coordinate, respectively. Since \(\alpha _1 \ne 0\), for at least one of \(i = 1\) or \(i=2\) we have \(\pi _i(\alpha _1) \ne 0\). Then \(\pi _i(\rho ) = \pi _i(\alpha _1 \star \beta _1) = \pi _i(\alpha _1) \pi _i(\beta _1)\) is a nonzero polynomial of degree 1 over L (in the variable \(\pi _i(\beta _1)\)), which occurs with probability at most \(1/p^r\) according to Lemma 6.    \(\square \)

Proposition 6

(Informal) Suppose that the shares \(\{[s_{j,i}]\}_{j=1,i=1}^{\ell ,\kappa /h}\) are authenticated, and let \(P_u,P_v\) be two players, where \(P_v\) is honest. If \(P_u\) announces potentially incorrect shares \(s_{j,i,u}' = s_{j,i,u} + \delta _{j,i,u}\) and a potentially incorrect tag \(\tau ' = \tau +\Delta \), then the check \(\tau ' {\mathop {=}\limits ^{?}} \varvec{\mu }\odot \varvec{\sigma }' + \nu \) will succeed with probability at most \(\frac{1}{p^\kappa }\).

Proof

The errors \(\delta _{j,i,u}\) translate into an error vector \(\varvec{\delta }\in (A_L)^\ell \) such that the check is performed on \(\varvec{\sigma }' = \varvec{\sigma } + \varvec{\delta }\). Furthermore, \(\varvec{\delta } = 0\) if and only if \(\delta _{j,i,u} = 0\) for all \(i\in \{1,\ldots ,\kappa /h\}\) and \(j\in \{1,\ldots ,\ell \}\), so checking that the shares announced by \(P_u\) are correct amounts to checking that \(\varvec{\delta } = 0\).

It is easy to see that the check passes if and only if \(\Delta = \varvec{\mu }\odot \varvec{\delta } + \nu \). Invoking Lemma 4 completes the proof.    \(\square \)

We conclude that once the tags are in place, these can be used to prevent corrupt parties to lie about their shares whenever some fault localization is required at the dispute control layer. We refer the reader to [6] for the details about how these tags are exactly used.

Computation of the Tags. In the previous paragraphs we showed that the tags, once computed and distributed, provide the required authentication properties. However, we did not deal with the way that these tags are computed. An important contribution of [6] was showing an efficient method for the computation of these tags, which saves in communication and that is crucial for the overall efficiency.

At a very high level, their method works as follows: First, observe that the task of computing the tags can be seen as a two-party protocol between party \(P_u\) and party \(P_v\), where \(P_u\) inputs the share vector \(\varvec{\sigma }\), \(P_v\) inputs the keys \(\varvec{\mu }\in (A_S)^\ell \), \(\nu \in A_S\), and \(P_u\) gets the output \(\tau \). The idea is to use a “Mini-MPC” protocol for this computation, but to ensure efficiency of the whole protocol distributing the inputs must be done with little communication. This is where the concept of twisted shares defined in Sect. 7.1 comes into play: one of the inputs, \(\varvec{\sigma }\), is actually a share, and therefore it is already “shared”. We discuss this idea in a bit more detail in what follows, but first we begin with the crucial property of twisted shares that motivates their consideration in a first place.

Lemma 5

Let \(R = \mathsf {GR}(p^k,h)\), let \(x,y\in R\) and suppose they are shared as \([x] = (x_1,\ldots ,x_n)\in A^n\), \(\lceil y \rfloor ^{i} = (y_1,\ldots ,y_n)\in A^n\). Then \([x]*\lceil y \rfloor ^{i} = \langle \!\langle x_i\star y \rangle \!\rangle \). Furthermore, an analogous property holds for the LSSS obtained by extending to a Galois ring extension L.

Proof

By definition, \(\lceil y \rfloor ^{i}\) can be seen as \([0]\). Then, using Proposition 5, we see that \([x]*\lceil y \rfloor ^{i} = [x]*[0] = \langle 0\rangle \). Furthermore, the i-th entry of this vector is \(x_i\star y_i = x_i\star y\), which concludes the proof of the lemma.    \(\square \)

With this lemma in hand we can sketch the Mini-MPC protocol that the parties \(P_u,P_v\) use to compute the tags. First, let us assume for simplicity that \(\ell =1\) and that \(R=S\), so the MAC is simply \(\tau = \mu \star \sigma + \nu \in A\). Let \([s]\) be such that its u-th share is \(\sigma \) (recall that the tags are used to authenticate shares, so \(\sigma \) is a share of some secret). The protocol, at a high level, proceeds as follows:

  1. 1.

    \(P_v\) samples \(\mu ,\nu \in A\).

  2. 2.

    \(P_v\) distributes twisted shares of \(\mu \) and double twisted shares of \(\nu \), i.e., \(\lceil \mu \rfloor ^{u},\langle \nu \rangle ^{u}\).

  3. 3.

    The parties compute \([s]*\lceil \mu \rfloor ^{u} + \langle \nu \rangle ^{u}\), which by Lemma 5 equals \(\langle \!\langle \sigma \star \mu + \nu \rangle \!\rangle \).

  4. 4.

    The parties send these shares to \(P_u\) for reconstruction.

  5. 5.

    The correctness of the tags is verified via standard cut-and-choose techniques.

We refer the reader to protocol TagComp in [6] for the full details of the protocol to compute the tags. We remark that the core aspects of this protocol that depend on working over a field have been already addressed above, and the rest of the protocol translates directly to our setting.

Complexity Analysis. With the due modifications the resulting TagComp protocol over R has a communication complexity of \(O(k\cdot \log _2(p)\cdot (m\cdot n\cdot h + n^5\cdot \kappa ))\) for computing the tags in one single segment. Since \(m = O(|C|)/n^2\), multiplying by the \(n^2\) segments yields \(O(k\cdot \log _2(p)\cdot (|C|\cdot n\cdot h + n^7\cdot \kappa ))\).

7.4 Batched Triple Sacrifice

The task here is to compute the \(M = O(|C|)\) multiplication triples necessary for the execution of online phase. Computing them can be done in a similar way as in Sect. 5, but their correctness will not be guaranteed. As before, due to the dispute control layer, \(m = M/n^2\) triples are checked in each segment. One of the key novelties of the BFO protocol is a technique for checking these triples with a complexity that is roughly \(O(n\log (n) + \kappa )\) per triple.Footnote 11 This is achieved by dividing the m triples to be checked into batches of size \(N = n^2\) each, developing a procedure that checks these N triples with complexity \(O(N\cdot n\cdot \log (n) + n^2\cdot \kappa )\), which, by multiplying by the number of batches m/N, yields \(O(m\cdot (n\cdot \log (n) + \kappa ))\).

Before we adapt their protocol to our setting, we begin by revisiting their techniques over fields here. Consider a field \(\mathbb {F}_{q} \) with at least 2N elements, where \(N = n^2\), and let \(x_1,\ldots ,x_{2N-1}\) be different points in \(\mathbb {F}_{q} \). Suppose the parties have shares over this field where \(c_i\) is supposed to be \(a_i \cdot b_i\). The parties check their consistency as follows:

  1. 1.

    Define \(f(X),g(X)\in \mathbb {F}_{q} [X]\) to be the polynomials of degree at most \(N-1\) such that \(f(x_k) = a_k\) and \(g(x_k) = b_k\) for \(k=1,\ldots ,N\).

  2. 2.

    The parties compute shares of \(a_{k} := f(x_k)\) and \(b_k := g(x_k)\) for \(k=N+1,\ldots ,2N-1\) by taking an appropriate linear combination (over \(\mathbb {F}_{q} \)) of the shares and , respectively.

  3. 3.

    Define h(X) as the polynomial of degree at most \(2N-2\) given by \(h(X) = f(X)\cdot g(X)\), notice that it should be the case that \(c_k = h(x_k)\) for \(k=1,\ldots ,N\).

  4. 4.

    Use a passively secure multiplication protocol to compute (potentially incorrectly) \(\llbracket c_k \rrbracket := \llbracket a_k \rrbracket \cdot \llbracket b_k \rrbracket \) for \(k=N+1,\ldots ,2N-1\). Now the parties have shares of \(2N-1\) points on the polynomial h(X).

  5. 5.

    Sample a random \(\sigma \in \mathbb {F}_{q^\kappa }\) and compute shares over \(\mathbb {F}_{q^\kappa }\) of \(f(\sigma ),g(\sigma ),h(\sigma )\in \mathbb {F}_{q^\kappa }\) by taking a linear combination over \(\mathbb {F}_{q^\kappa }\) of , and , respectively.

  6. 6.

    Perform some check over these shares to verify that \(f(\sigma )\cdot g(\sigma ) = h(\sigma )\).

When extending the above protocol over rings there are several complications that appear. One immediate concern is the argument that shows that checking the polynomial equality \(f(X)\cdot g(X) = h(X)\) can be done by evaluating a random point. To show this still holds, we invoke the following lemma from [2, Lemma 2].

Lemma 6

Let \(f\in R[X]\) polynomial of arbitrary degree \({\ell >0}\). Then \(\Pr _{x\leftarrow R}[f(x) = 0]\le \frac{\ell }{p^\kappa }\), where x is drawn uniformly from R.

One issue that appears is that we do not necessarily have enough points \(x_1,\ldots ,x_{2N-1}\in R\) for interpolation over our ring R. We fix this by using a Galois ring extension L of degree \(O(\log (N)) = O(\log (n))\) for the interpolation, which introduces an overhead of \(\log (n)\) in the multiplications \(\llbracket c_k \rrbracket = \llbracket a_k \rrbracket \cdot \llbracket b_k \rrbracket \) for \(k=N+1,\ldots ,2N-1\). We remark that this is the only place of the whole protocol where the \(\log (n)\) overhead appears.

The final effect of this is that the complexity of the preprocessing phase becomes \(O(|C|\cdot (n\cdot \log (n) + \kappa ))\), which is not fully linear, but it is already better than the best protocol known for this setting [2], which has a complexity of \(O(|C|\cdot n^2\cdot \log (n))\).Footnote 12 Furthermore, our online phase is fully linear, i.e., \(O(|C|\cdot n)\). This has an interpretation in practice: in the offline phase the communication per party increases logarithmically as the number of parties gets larger, but in the online phase, this communication remains constant. This supports the rationale of the offline/online paradigm: expensive computations can be pushed to a function-independent preprocessing phase, and in the online phase where the inputs and the function are actually instantitated, the computation is cheaper.

We describe our protocol for batched triple generation in Fig. 1. It is very similar to the corresponding protocol in [6] except that in our case we use properties of Galois rings to argue about the security of the construction. The security of our construction is argued below in proposition 7. It shows that if there is at least one triple that is incorrect then it will be detected in the final check with high probability.

Fig. 1.
figure 1

Protocol for checking the correctness of several triples

Proposition 7

Let be the triples inputted to Protocol \(\mathsf {BatchedTriples}\), and suppose that \(c_i = a_i\cdot b_i + d_i\) for \(i=1,\ldots ,N\). If the honest parties output OK at the end of the protocol, then \(d_i = 0\) for all i with probability at least \(1 - \frac{1}{p^\kappa }\).

Thanks to the properties of Galois rings that we have exploited throughout the paper, the proof follows along the same lines as the corresponding proof in [6], and we will not replicate it here.

Complexity Analysis. Similar to the analysis in the field case done at the beginning of this section, the complexity of checking the m triples in one segment using BatchedTriples is \(O(k\cdot \log _2(p)\cdot m\cdot (n\cdot \log (N)\cdot h + \kappa ))\). By multiplying by the number of segments \(n^2\), and recalling that \(N = n^2\) and \(m = O(|C|)/n^2\), we obtain \(O(k\cdot \log _2(p)\cdot |C|\cdot (n\cdot \log (n)\cdot h + \kappa ))\). Furthermore, the optimization in [6] of using \(N = n^{2+c}\) where \(\kappa (n) = O(n^c)\) applies also in our case and results in a complexity of \(O(k\cdot \log _2(p)\cdot |C|\cdot n\cdot \log (n)\cdot h)\).

Remark 2

The \(\log (n)\) overhead we have in the preprocessing appears in a very specific stage, and we can even remove it assuming a functionality that produces additive shares of matrix outer products efficiently.

Optimizing the Batch Triple Verification. We can use the tools we have developed to further optimize our triple check procedure by adapting the more recent protocol of [22]. Their batch check protocol builds on top of the one we use from [6], and also makes use of polynomial interpolation, which as we have shown extends to Galois rings. This would lead to a more efficient protocol.

7.5 Putting the Pieces Together

Using the building blocks described in previous sections, we obtain a protocol over \(R = \mathsf {GR}(p^k,h)\) whose offline phase has a total communication complexity of \(O(k\cdot \log p\cdot (h\cdot |C|\cdot n\cdot \log (n) + n^7\cdot \kappa ))\). The online phase, which follows the exact same template as in [6, Section 3.4], has a total communication complexity of \(O(k\cdot \log p\cdot h\cdot |C|\cdot n)\). This proves Theorem 10.

8 Conclusions and Future Work

Our work shows that results from coding theory over fields can be leveraged to obtain corresponding results over the more general Galois rings, which include as a particular case the practically relevant ring \(\mathbb {Z}/{2}^k\mathbb {Z} \). Although not all properties automatically lift (e.g., multiplicativity), we presented techniques to overcome these issues and still get meaningful coding-theoretic tools over Galois rings, that can be applied to MPC.

We showed that information-theoretic honest-majority MPC over rings which scales well with the number of parties is possible. Our protocols have linear communication complexity, except for the offline phase of our protocol with guaranteed output delivery from Sect. 7, which has a \(\log (n)\) overhead. The complexity can be further reduced by combining our results with the work of [21].

Finally, like in [6], the communication complexity of our construction remains linear if the circuit is not too narrow. This restriction was removed in [21] for the case of \(t<n/3\), and then in [22] for the case of \(t<n/2\). As we mentioned in Sect. 7, the techniques from that paper can also be adapted to Galois rings.