Efficient Information-Theoretic Multi-party Computation over Non-commutative Rings

Abstract

We construct the first efficient, unconditionally secure MPC protocol that only requires black-box access to a non-commutative ring R. Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir’s secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (IEEE Transactions on Information Theory, 2013). When the center of the ring contains a set $A = \{\alpha _0, \ldots , \alpha _n\}$ such that $\forall i \ne j, \alpha _i \,-\, \alpha _j \in R^*$, the resulting secret sharing scheme is strongly multiplicative and we can generalize existing constructions over finite fields without much trouble.

Most of our work is devoted to the case where the elements of A do not commute with all of R, but they just commute with each other. For such rings, the secret sharing scheme cannot be linear “on both sides” and furthermore it is not multiplicative. Nevertheless, we are still able to build MPC protocols with a concretely efficient online phase and black-box access to R. As an example we consider the ring $\mathcal {M}_{m\times m}(\mathbb {Z}/2^k\mathbb {Z})$, for which when $m > \log (n+1)$, we obtain protocols that require around $\lceil \log (n+1)\rceil /2$ less communication and $2\lceil \log (n+1)\rceil$ less computation than the state of the art protocol based on Circuit Amortization Friendly Encodings (Dalskov, Lee and Soria-Vazquez, ASIACRYPT 2020).

In this setting with a “less commutative” A, our black-box preprocessing phase has a less practical complexity of $\mathsf {poly}(n)$. We fix this by additionally providing specialized, concretely efficient preprocessing protocols for $\mathcal {M}_{m\times m}(\mathbb {Z}/2^k\mathbb {Z})$ that exploit the structure of the matrix ring.

E. Soria-Vazquez—Work partially done while at Aarhus University, Denmark.

1 Introduction

Multiparty Computation, or MPC for short, is a collection of techniques that enable a set of mutually distrustful parties $P_1,\ldots ,P_n$ to securely compute a given function f on private inputs $x_1,\ldots ,x_n$, while revealing only the output of the computation. Security is formalized by considering an adversary that corrupts t of the parties, and aims at learning as much as possible from the honest parties’ inputs either by only seeing the messages corrupt parties send/receive without changing their behavior (passive adversary), or by arbitrarily deviating from the protocol specification (active adversary). Security requires that the adversary does not learn anything about the honest parties’ inputs beyond what is possibly leaked by the output of the computation. MPC protocols exist in a wide variety of settings, and some very interesting ones are the settings in which $t<n/2$ and the stronger one in which $t<n/3$. It is well known that in these scenarios, MPC protocols whose security is completely independent of the hardness of any computational problem can be devised, and with the lack of these computational problems typically more efficiency is gained. These protocols are called information-theoretic protocols.

Many information-theoretic protocols exist in the $t<n/2$ and $t<n/3$ regimes, for which computation is primarily represented as an arithmetic circuit whose gates involve additions and multiplications over a finite ring. Traditionally, this ring has been restricted to be a finite field, since the lack of zero divisors simplifies protocol design and opens for a vast literature of algebraic tricks which can ensure that an active adversary does not cheat during the protocol. A recent line of work [ACD+19, DLS20, CRX19, ED20] designs protocols that operate over non-field rings, namely $\mathbb {Z}_{2^k}$ (integers modulo $2^k$), and Galois ring extensions $\mathsf {GR}(2^k,d)$ of these. The use of these rings is well motivated in practice due to their direct compatibility with hardware and their natural affinity with binary-based protocols like binary decomposition, secure comparison or secure truncation for fixed-point arithmetic. It is not hard to generalize the techniques presented in [ACD+19] to more general commutative rings, as long as the so-called Lenstra constant¹ of the ring is large enough. However, in spite of the recent progress in the design of MPC protocols over non-field rings, non-commutative rings have been mostly overlooked in the literature.

Studying non-commutative rings is a well motivated theoretical question, since it explores what are the minimal assumptions required on an algebraic structure so that MPC protocols can be naturally defined over it. Furthermore, there are some non-commutative rings that are very suitable for practical applications. For instance, matrix rings are very useful for applications based on linear algebra, which include statistics as well as the training and evaluation of different kinds of machine learning models. Another example are quaternion rings, which are particularly advantageous for describing rotations in a three-dimensional space. Due to this feature, quaternions are a useful tool in the domains of computer graphics, robotics and aerospace, including satellite navigation.

Motivated by the above, in this work we attack the question of designing efficient information-theoretic MPC protocols which work directly over not-necessarily-commutative finite rings.

1.1 Theoretical Contributions

First, we observe that feasibility results for MPC have been established already since the 80s (e.g. [BGW88]), so in principle we could make use of any existing MPC protocol that allows computing any function in order to emulate arithmetic over any given ring R. However, we notice that this requires white-box access to the representation of elements in R, and moreover, it is unlikely to lead to efficient protocols if there is no certain “compatibility” between the ring R and the domain used for the underlying MPC protocol. For example, if R is a matrix ring over the integers modulo a prime, and the domain of computation of the given protocol is $\mathbb {Z}_{2}$, then there is a large overhead incurred in emulating each single addition and multiplication modulo a prime using binary circuits.

Given the above, we propose efficient unconditionally secure MPC protocols over rings containing big enough exceptional sets A which satisfy some additional commutativity properties. Our most general results only requires black-box access to the ring, which we start by precisely defining.

Definition 1

We say that a protocol has black-box access to a ring R, or simply that it is black-box, if it only requires black-box access to the ring operations and the elements of a particular exceptional set A. Furthermore, we assume that it is efficient both to sample elements from R and to invert elements from $R^*$.

Our protocols are based on a generalization of Shamir’s linear secret sharing scheme to non-commutative rings. Prior to our work, Quintin, Barbier and Chabot [QBC13] showed how to construct Reed Solomon codes over rings that do not need to be commutative. By reinterpreting their results under the lenses of linear secret-sharing schemes (LSSS’s), we first obtain the following result.

Theorem 1

([Theorem 4, restated). Let R be a ring such that Z(R) contains an exceptional set of size at least $n\,+\,1$ and let $t<n/3$. Then, we can define a Shamir-style strongly multiplicative linear secret sharing scheme over R.

This is discussed in Sect. 3. Given a ring satisfying the hypothesis of the previous theorem, we can adapt the perfectly secure protocol by Beerliova and Hirt [BTH08].

Corollary 1

(Corollary 2, restated). Let R be a ring such that Z(R) contains an exceptional set of size at least 2n. Let $\mathcal {A}$ be an active adversary corrupting $t < n/3$ parties. There exists a perfectly secure, black-box MPC protocol with an amortized communication complexity of O(n) ring elements per gate.

While interesting, the previous result leaves out of the picture several non-commutative rings. For example, the centre of the ring of matrices over $\mathbb {Z}_{2^k}$, which is widely used in applications involving linear algebra, like machine learning, has a Lenstra constant of 2, which is not large enough to apply the results highlighted above. We fix this by relaxing the commutativity requirements for the elements of the exceptional set: instead of requiring this exceptional set to be a subset of the centre of the ring, we only ask the elements of the exceptional set to commute with each other. It is in this setting that the previous results on Reed-Solomon codes [QBC13] do not help us as much. The resulting code (i.e. secret sharing scheme) is not linear “on both sides”, but rather only when multiplied by scalars either on the left or on the right. Even more disastrously, the left-or-right LSSS that we obtain is not multiplicative, which rules out standard techniques to achieve unconditionally secure MPC. Considering all of this, most of our work relates to proving the following Theorem:

Theorem 2

(Informal). Let R be a ring and $A = \{\alpha _0, \ldots , \alpha _n\} \subseteq R$ an exceptional set such that $\forall \alpha _i, \alpha _j \in A, \alpha _i \cdot \alpha _j = \alpha _j \cdot \alpha _i$. Let $\mathcal {A}$ be an active adversary corrupting t parties. For $t < n/2$ and $t < n/3$, there exist efficient, information-theoretically secure, black-box MPC protocols over R. The amortized communication complexity of their online phase is O(n) ring elements per gate.

The black-box online phase of our protocol is described in Sect. 4, while the black-box offline phase is presented in Sect. 5.1.

1.2 Concretely Efficient Protocols for $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$

Beyond their theoretical interest, our techniques also have relevance in the context of concretely efficient MPC. As an example for this, we provide constructions for the important ring $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, the ring of m $\times$ m matrices with entries modulo $2^k$, which improve upon the concrete efficiency of the online phase of the state of the art protocols in the same setting but without black-box access to R. As mentioned before, the centre of this ring does not have a large enough exceptional set, so the MPC techniques based on the multiplicativity of Shamir secret sharing (which are quite efficient) cannot be applied.

Given this, our approach is to make use of the black-box protocol from Theorem 2. First, we show that, whenever $m \ge \log (n+1)$, the hypothesis of this theorem is satisfied. This is due to the fact that $\mathsf {GR}(2^k,m)$ is a (commutative) subring of R and the Lenstra constant of $\mathsf {GR}(2^k,m)$ is precisely $2^m$. Second, we show how to replace the black-box preprocessing from Theorem 2, which achieves only $\mathsf {poly}(n)$ communication complexity, by a more tailored preprocessing protocol for $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$. This is done in Sect. 5.2. Finally, we also show in the full version of this work how to do efficient error-correction of Shamir shares in this setting.

By following Theorem 2 we obtain a very efficient online phase, as described by the (generic) protocols we provide in Sect. 4. For this part of the protocol execution, the fact of having a secret sharing scheme directly over R is a significant efficiency advantage: each share of a secret is a single element of R, and arithmetic happens at the level of R. However, the price to pay for such an efficient online phase, which overcomes the issues of lacking multiplicativity, is that the offline phase becomes much more complex.

In Sect. 5.2 we show how to compute the required preprocessing material for $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ by, intuitively, secret-sharing each entry of a matrix and then leveraging existing works on MPC over $\mathbb {Z}_{2^k}$ [ACD+19, DLS20]. As we need to compute the product between secret-shared matrices and retain information-theoretic security, this is our best approach for concrete efficiency. Secret-sharing each entry of a matrix in $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ individually would require us to move to a Galois extension of $\mathbb {Z}_{2^k}$ of degree $d \simeq \log (n\,+\,1)$, which would add such overhead in terms of communication and a worse one for computation. Instead of naively secret-sharing each entry, we amortize the asymptotic communication cost of working over such Galois extension by using the Circuit Amortization Friendly Encodings (CAFEs) introduced in [DLS20]. Intuitively, what this means is that chunks of every row/column of each matrix will be secret-shared as a single Galois Ring element.

At this point, one could ask why not work with this type of secret-sharing for the whole protocol execution, rather than just the preprocessing phase. The CAFE for inner products that we use in our preprocessing phase allows to “pack” approximately d/2 elements from $\mathbb {Z}_{2^k}$ into $\mathsf {GR}(2^k,d)$, so that seems to be a small overhead. Some arguments for not following this route are as follows. First of all, the protocol from [DLS20] is only fully detailed for double sharings and in the case of security with abort. Our online protocol, on the other hand, has guaranteed output delivery (if $t<n/3$) and uses multiplication triples. Furthermore, it is most efficient when using a function-dependent preprocessing in the style of [BNO19, ED20]. These differences make a fair comparison more difficult, but even assuming an adaptation of [DLS20] to the function-dependent techniques of [BNO19, ED20], our online phase remains more efficient in the following aspects.

• Secret sharing input values: For the adapted [DLS20], when parties provide inputs to the computation, it would be important to check that they are rightly encoded. This issue is not specific to CAFEs, but merely to the fact of having to work over an extension ($\mathsf {GR}(2^k,d)$) of the ring one is actually interested in ($\mathbb {Z}_{2^k}$). The check can be performed by using preprocessing material, but it increases the communication and round complexity of the protocol. Our online phase does not need to perform any such check, as it works directly over $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$.

• Computing the product of two secret-shared matrices, communication: In our work, this requires to reconstruct two secrets in $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$. An adapted [DLS20], would need to reconstruct one element of $\mathsf {GR}(2^k,d)$ per entry of the matrix. Hence, in terms of communication we are around d/2 times better in our work.

• Computing the product of two secret-shared matrices, computation: Our work benefits from the fact that the shares each party holds, as well as the operations they perform on them, are in $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$. This has the advantage that an implementation of our protocol can fully exploit existing libraries for matrix arithmetic, which is quite efficient due to its relevance in multiple practical settings. On the other hand, using a potential extension of the techniques of [DLS20] in the online phase would require computation on Galois ring elements, which is way less studied than matrix arithmetic and it is also more inefficient. Each multiplications of two Galois ring elements costs $d^2$ operations in $\mathbb {Z}_{2^k}$, or potentially $d\log (d)$ using FFT-based techniques. This is not very concretely efficient, as explored experimentally in [DEK21], for example.

Instead of using CAFEs, Reverse Multiplication Friendly Embeddings (RMFEs) [CCXY18] could have been chosen. A generalization of the interpolation-based RMFE from [CCXY18] was presented in [DLS20] and the constructions based on algebraic geometric codes were also lifted to rings in [CRX19]. Whereas RMFEs are much computationally heavier than CAFEs, they can provide a slightly better communication complexity. More concretely, if $\delta$ is the amount of elements from the base ring that the RMFE can “pack”, RMFEs incur in a communication complexity for the product of secret shared matrices that would be only $d/\delta$, rather than d/2, worse than ours. On the other hand, using RMFEs require two sequential openings per matrix multiplication, rather than a single one as CAFEs do. This is due to a resharing operation to compute $\psi (\phi ({\boldsymbol{a}})\cdot \phi ({\boldsymbol{b}}))$ in RMFEs.

In a nutshell, by using our seemingly theoretical tools, we are able to build MPC protocols which have a more efficient online phase than the state of the art protocols, while retaining a comparable preprocessing.

1.3 Related Work

There are a few works on MPC over non-abelian groups, rather than rings. Hence, we are not interested in those. These include [DPS+12] and [CDI+13]. Note that [CDI+13] additionally provides constructions for commutative rings.

MPC over non-commutative rings has been discussed in [CFIK03], but their results related to MPC from (multiplicative) Monotone Span Programs are restricted to (algebras over) commutative rings. They only seem to take care of the non-commutative case in Sects. 4.2 and 4.3, which deal only with branching programs and formulas, rather than circuits.

Although not mentioned explicitly in [BBY20], the basic building blocks (secure addition and multiplication) presented in that work for MPC based on replicated secret-sharing also work over a non-commutative ring. However, these techniques differ from ours in several ways. First, they use computational assumptions (PRFs) in order to improve their overall efficiency. Second, as it is inherent for MPC based on replicated secret-sharing, the communication complexity does not scale well as the number of parties increases. More precisely, each share consists of $\left( {\begin{array}{c}n\\ t\end{array}}\right)$ ring elements, which is exponential in n whenever $t = n/c$ for some $c>1$, since $\left( {\begin{array}{c}n\\ n/c\end{array}}\right) \ge (c^{1/c})^n$.²

2 Preliminaries

Notation. Sometimes, we use [n], where $n \in \mathbb {N}$, to represent $\{1, 2, \ldots , n\}$. We write $x \,{\mathop {\leftarrow }\limits ^{\$}}\, \mathcal{X}$ to denote sampling a value x uniformly from the set $\mathcal{X}$. We write $\mathbb {Z}_{p^k}$ to denote the ring of integers modulo $p^k$ and $\mathcal {M}_{r \times c}(R)$ to refer to the ring of $r \times c$ matrices over R.

2.1 Multiparty Computation

We consider secure evaluation of functions $(y_1,\ldots ,y_n)=f(x_1,\ldots ,x_n)$ given by arithmetic circuits with addition and multiplication gates defined over a finite ring R, where party $P_i$ is supposed to learn $y_i$.

The security of our protocols is proven in the UC framework by Cannetti [Can01]. We assume secure, synchronous channels, and we deal with active, static adversaries. In a nutshell, the adversary corrupts a subset of t parties actively, arbitrarily changing their behavior during the execution of the protocol. The adversary, also known as an environment, additionally provides the inputs for all the parties. A given protocol $\varPi$ instantiates a given functionality $\mathcal {F}$, if there exists a simulator $\mathcal {S}$ who, by interacting with the adversary and with the functionality $\mathcal {F}$, creates an execution (called the ideal execution) that is indistinguishable to the adversary from the real execution in which the actual honest parties are running the protocol $\varPi$.

If the distributions in the two executions are exactly the same, then we say that $\varPi$ instantiates $\mathcal {F}$ with perfect security. In contrast, if the distributions are only negligibly apart (in some security parameter $\kappa$), then we say that $\varPi$ instantiates $\mathcal {F}$ with statistical security. Finally, sometimes we consider hybrid models in which a protocol $\varPi$ instantiates a functionality $\mathcal {F}$, assuming access to another functionality $\mathcal {F}'$. In this case we say that $\varPi$ instantiates $\mathcal {F}$ in the $\mathcal {F}'$-hybrid model. See [Can01] for details.

In this work we consider a broadcast functionality $\mathcal {F}_{\scriptstyle \mathrm {BC}}$ that receives an input from a designated sender and relays this exact same value to all the parties.

We will take into account two functionalities for MPC. One is $\mathcal {F}_{\scriptstyle \mathrm {MPC-GOD}}$, which receives inputs $x_1,\ldots ,x_n$ from the parties, computes the given function $(y_1,\ldots ,y_n) = f(x_1,\ldots ,x_n)$, which is represented as an arithmetic circuit over a ring R composed of addition and multiplication gates, and returns the output $y_i$ to each party $P_i$. The second functionality is $\mathcal {F}_{\scriptstyle \mathrm {MPC-abort}}$, which is defined as $\mathcal {F}_{\scriptstyle \mathrm {MPC-GOD}}$, except that, before delivering output to the parties, it waits for a message from the adversary. If the message is $\mathtt {abort}$, then the functionality sends $\mathtt {abort}$ to all the parties. Else, if the message if $\mathtt {ok}$, then the functionality sends the output $y_i$ to each party $P_i$. In a real execution, when we say that an honest party “aborts”, it means that this party sends an abort signal to all the parties using $\mathcal {F}_{\scriptstyle \mathrm {BC}}$ and then outputs $\mathtt {abort}$. A party aborts upon receiving an abort signal through the broadcast channel.

2.2 Background in Ring Theory

We turn to recall some useful results from ring theory. Outside of this section, whenever we talk about a ring R, we mean a finite ring with identity $1 \ne 0$ for which we do not assume commutativity. During this specific section we do not assume finiteness, so that it is clear which results require such hypothesis.

Working over these general rings hides subtleties which do not appear in the field case. Besides the lack of commutativity, one has to be careful about the fact that the rings we consider contain zero divisors. Moreover, it is important to reconsider what it means to be a unit. We recap some basic definitions and results in this area of algebra. These are standard results, and some of their proofs are provided in the full version of this work.

Definition 2

Let R be a ring. An element $a \in R$ is a unit if there exists $b \in R$ such that $a \cdot b = b \cdot a = 1$. The set of all units is denoted by $R^*$.

An element $a \in R {\setminus }\{0\}$ is a left (resp. right) zero divisor if $\exists ~b \in R {\setminus }\{0\}$ such that $a \cdot b = 0$ (resp. $b \cdot a = 0$). In this work, whenever we say that $a \in R {\setminus }\{0\}$ is a zero divisor we mean that a is both a left and right zero divisor.

Lemma 1

• 1. $a \in R^*$ if and only if a is both left-invertible and right-invertible.

• 2. If a has a right inverse, then a is not a right zero divisor.

• 3. If R is finite, then every element which has a right inverse is a unit.

Lemma 2

Let R be a finite ring. Then all non-zero elements of R are either a unit or a zero divisor.

Some elements of a non-commutative ring have better commutative properties than other. The two following definitions allow us to name them.

Definition 3

The center of a ring R, denoted by Z(R) consists of the elements $a \in Z(R)$ such that $\forall b \in R$, $ab = ba$.

Definition 4

([QBC13]). Let $A = \{a_1, \dots , a_n \} \subset R$. We say that A is a commutative set if $\forall a_i, a_j \in A, a_i \cdot a_j = a_j \cdot a_i$.

Exceptional sets. Elements which satisfy that their pairwise differences are invertible will be fundamental in our constructions. These have received different names in the literature: ‘subtractive sets’ in [QBC13], ‘exceptional sequences’ in [ACD+19] and ‘exceptional sets’ in [DLS20]. We will stick with the latter denomination.

Definition 5

Let $A = \{a_1, \dots , a_n \} \subset R$. We say that A is an exceptional set if $\ \forall i \ne j, a_i - a_j \in R^*$. We define the Lenstra constant of R to be the maximum size of an exceptional set in R.

2.3 Polynomials over Non-commutative Rings

Definition 6

(Polynomial Ring). Let R be a ring and $A \subseteq R$. The set of polynomials over A of degree at most d is given by $A[\mathtt {X}]_{\le d} = \{f(\mathtt {X}) = \sum _{i=0}^d a_i\cdot \mathtt {X}^i ~|~ a_i \in A \}$. The set of polynomials over A is $A[\mathtt {X}] = \cup _{d\ge 0} A[\mathtt {X}]$. Given two polynomials $a(\mathtt {X}) = \left( \sum _{i=0}^d a_i\cdot \mathtt {X}^i\right)$, $b(\mathtt {X}) = \left( \sum _{j=0}^{d'} b_j\cdot \mathtt {X}^j\right)$, the ring R induces the following operations:

• 1. $c(\mathtt {X}) = a(\mathtt {X}) + b(\mathtt {X}) = \sum _{k=0}^{\max \{d,d'\}} (a_k + b_k) \cdot \mathtt {X}^k$, where $a_k = 0$ for $k > d$ and $b_k = 0$ for $k > d'$.

• 2. $c(\mathtt {X}) = a(\mathtt {X}) \cdot b(\mathtt {X}) = \sum _{k=0}^{d+d'} c_k\cdot \mathtt {X}^k$, where

  $$c_k = \sum _{\begin{array}{c} i+j=k\\ 0\le i\le d,\ 0\le j\le d' \end{array}}a_ib_j.$$

Furthermore, when A is a ring, so is $A[\mathtt {X}]$.

Our definition of the product in a polynomial ring imposes that “the indeterminate $\mathtt {X}$ commutes with the coefficients”. Otherwise, when formally multiplying two polynomials we would encounter terms of the form $a_i\mathtt {X}^ib_j\mathtt {X}^j$, which could not be turned into $a_ib_j\mathtt {X}^{i+j}$. Allowing the indeterminate to commute with coefficients, rather than keeping everything non-commutative, allows us to prove a series of results leading to the existence and uniqueness of interpolating polynomials. On the other hand, granting this small commutativity property to polynomials requires to consider their evaluation more carefully, as we will see next.

Definition 7

(Evaluation Maps). Let $f = \sum _{i=0}^{d} f_i \mathtt {X}^i \in R[\mathtt {X}]$ and $a \in R$. We define the evaluation at a on the right (resp. left) map ${f}^{\textsf {R}}(a)$ (resp. ${f}^{\textsf {L}}(a)$) as follows:

$$\begin{aligned} {\cdot }^{\textsf {R}}(a): R[\mathtt {X}]&\rightarrow R&{\cdot }^{\textsf {L}}(a): R[\mathtt {X}]&\rightarrow R\\ f&\mapsto {f}^{\textsf {R}}(a) = \sum _{i=0}^{d} f_i a^i&f&\mapsto {f}^{\textsf {L}}(a) = \sum _{i=0}^{d} a^i f_i \end{aligned}$$

We say that a is a right (rep. left) root whenever ${f}^{\textsf {R}}(a) = 0$ (resp. ${f}^{\textsf {L}}(a)=0$). We use f(a) to denote ${f}^{\textsf {R}}(a)$.

The evaluation maps above are additive homomorphisms but, in general, they are not ring homomorphisms. This is because, as mentioned above, in polynomial multiplication the indeterminate $\mathtt {X}$ commutes with the coefficients. It is important to keep in mind that we are dealing with polynomials as formal objects of their own, rather than confusing them with polynomial functions (where a “variable” $\mathtt {X}$ is “instantiated” with $a \in R$ when evaluating the polynomial) as one usually does in commutative rings. Fortunately, there are some cases in which some notion of multiplicative homomorphism holds for the evaluation maps, as described in the following lemma.

Lemma 3

Let $f \in R[\mathtt {X}]$.

• 1. Let A be a commutative set. If $g \in (A \,\cup \, Z(R))[\mathtt {X}]$ and $a \in A$, then ${(f\cdot g)}^{\textsf {R}}(a) ={f}^{\textsf {R}}(a) \cdot {g}^{\textsf {R}}(a)$ and ${(g\cdot f)}^{\textsf {L}}(a) = {g}^{\textsf {L}}(a)\cdot {f}^{\textsf {L}}(a)$.

• 2. Let $g \in R[\mathtt {X}]$. If $a \in Z(R)$, for all $h \in R[\mathtt {X}]$, ${h}^{\textsf {R}}(a) = {h}^{\textsf {L}}(a)$. Furthermore, ${(f\cdot g)}^{\textsf {R}}(a) ={f}^{\textsf {R}}(a) \cdot {g}^{\textsf {R}}(a)$.

Proof

We only prove the first part of the first statement, as the same reasoning applies for the rest of the claims. Let $a \in A$ and let $f(\mathtt {X}) = \left( \sum _{i=0}^d f_i\cdot \mathtt {X}^i\right) \in R[\mathtt {X}]$ and $g(\mathtt {X}) = \left( \sum _{j=0}^{d'} g_j\cdot \mathtt {X}^j\right) \in (A \cup Z(R))[\mathtt {X}]$ be our polynomials.

$$\begin{aligned} {f}^{\textsf {R}}(a) \cdot {g}^{\textsf {R}}(a)&= \left( \sum _{i=0}^d f_i\cdot a^i\right) \cdot \left( \sum _{j=0}^{d'} g_j\cdot a^j\right) = \sum _{i=0}^d \sum _{j=0}^{d'} f_i\cdot a^i \cdot g_j\cdot a^j =\\&= \sum _{i=0}^d \sum _{j=0}^{d'} f_i \cdot a^{i-1} \cdot g_j \cdot a^{j+1} = \sum _{i=0}^d \sum _{j=0}^{d'} f_i \cdot g_j \cdot a^{i+j} = {(f\cdot g)}^{\textsf {R}}(a). \end{aligned}$$

   $\blacksquare$

Theorem 3

(Euclidean Algorithm over Rings). Let $f(\mathtt {X}) \in R[\mathtt {X}]$ be a non-zero polynomial and let $g(\mathtt {X}) \in R[\mathtt {X}]$ be a monic polynomial. There exist unique $q_\ell (\mathtt {X}), r_\ell (\mathtt {X})$ (resp. $q_r(\mathtt {X}), r_r(\mathtt {X})$) such that $f(\mathtt {X}) = q_\ell (\mathtt {X}) \cdot g(\mathtt {X}) + r_\ell (\mathtt {X})$ (resp. $f(\mathtt {X}) = g(\mathtt {X}) \cdot q_r(\mathtt {X}) + r_r(\mathtt {X})$), where $\deg (r_\ell ) < \deg (g)$ (resp. $\deg (r_r) < \deg (g)$).

Given the two previous results, we can bound the number of roots of a polynomial as it is described in the next Lemma.

Lemma 4

Let $f \in R[\mathtt {X}]_{\le n}$ be a non-zero polynomial. Then f has at most n distinct left (resp. right) roots in the same commutative exceptional set $A \subset R$. In other words, if f has at least $n+1$ left (resp. right) roots in A, then it is the zero polynomial.

Proof

We focus on right roots for the result, and we reason by induction on the degree d of the non-zero polynomial f. The statement is clear when $d = 0$. Assuming the result for $d-1$, we now look at a degree-d polynomial f. If f does not have any roots, or if it only has one root, then the result clearly holds. Else, let $a,b \in A$ be two different roots of $f(\mathtt {X})$. As $g(\mathtt {X}) = \mathtt {X}\,-\,a$ is a monic polynomial, by Theorem 3 there exists $q(\mathtt {X})\in R[\mathtt {X}]$ and $c\in R$ such that $f(\mathtt {X}) = q(\mathtt {X}) \,\cdot \, g(\mathtt {X}) \,+\, c$. Observe that $\deg (q) < \deg (f)$.

Now, since $g(\mathtt {X})\in A[\mathtt {X}]$, by Lemma 3 we have that ${f}^{\textsf {R}}(a) = {q}^{\textsf {R}}(a){g}^{\textsf {R}}(a) \,+\, c$, so $0 = {q}^{\textsf {R}}(a)\cdot (a-a) + c=c$. From this, it follows that $0 = {f}^{\textsf {R}}(b) = {q}^{\textsf {R}}(b){g}^{\textsf {R}}(b) = {q}^{\textsf {R}}(b)\cdot (b-a)$. Since $(b - a) \in R^*$, then it has to be that ${q}^{\textsf {R}}(b)=0$.

By the induction hypothesis, $q(\mathtt {X})$ has at most $d-1$ distinct right roots in A, so we can conclude that $f(\mathtt {X})$ has at most d distinct right roots in A.    $\blacksquare$

Lagrange interpolation for sets of points $(x_i, y_i) \in R^2$ can be computed, as long as all the $x_i$ are part of the same commutative exceptional set $A \subset R$. The following result was proven in [QBC13], but it only considered evaluation on the right. We reformulate and extend their result here for completeness and additional precision.

Proposition 1

Let $A = \{x_1, \ldots ,x_{n+1}\} \subset R$ be a commutative exceptional set and let $B = \{y_1, \ldots , y_{n+1}\} \subset R$. Then there exists a unique polynomial $f \in R[\mathtt {X}]$ (resp. $g \in R[\mathtt {X}]$) of degree at most d such that ${f}^{\textsf {R}}(x_i) = y_i$ (resp. ${g}^{\textsf {L}}(x_i) = y_i$) for $i = 1, \ldots , d+1$. Furthermore, if $A \cup B$ constitutes a commutative set, or if $A \subset Z(R)$, $f(X) = g(X)$.

Proof

Let $L_i(\mathtt {X}) = \prod _{j \ne i} (\mathtt {X}-x_j) \in A[\mathtt {X}]$. Observe that for all $j=1,\ldots ,d+1$ it holds that $L_i(x_j) \in R^*$, since $(x_i-x_j) \in R^*$.

It is easy to verify, with the help of Lemma 3, that the two following polynomials show the existence of solutions:

$$\begin{aligned} f(\mathtt {X}) = \sum _{i=1}^{d+1} y_i L_i(x_i)^{-1} L_i(\mathtt {X}); \quad \quad \quad g(\mathtt {X}) = \sum _{i=1}^{d+1} L_i(\mathtt {X}) L_i(x_i)^{-1} y_i \end{aligned}$$

The uniqueness of f (resp. g) is a consequence of Lemma 4. The fact that $f(X) = g(X)$ when $A \cup B$ constitutes a commutative set or $A \subset Z(R)$ follows from inspection.    $\blacksquare$

2.4 Galois Rings

Galois Rings relate to integers modulo a prime power $p^k$ in the same way a Galois Field relates to integers modulo a prime p. They are a fundamental object of study among finite commutative rings.

Definition 8

A Galois Ring $\mathsf {GR}(p^k, d)$ is a ring of the form $R = \mathbb {Z}_{p^k}[\mathtt {X}]/(h(\mathtt {X}))$, where p is a prime, k a positive integer and $h(X) \in \mathbb {Z}_{p^k}[\mathtt {X}]$ a monic polynomial of degree $d \ge 1$ such that its reduction modulo p is an irreducible polynomial in $\mathbb {F}_{p}[\mathtt {X}]$.

Given a base ring $\mathbb {Z}_{p^k}$, there is a unique degree d Galois extension of $\mathbb {Z}_{p^k}$, which is precisely the Galois Ring provided on the previous definition. Note that Galois Rings reconcile the study of finite fields $\mathbb {F}_{p^d} = \mathsf {GR}(p, d)$ and finite rings of the form $\mathbb {Z}_{p^k} = \mathsf {GR}(p^k, 1)$. Every Galois Ring $R = \mathsf {GR}(p^k, d)$ is a local ring and its unique maximal ideal is (p). Hence, all the zero divisors of R are furthermore nilpotent, and they constitute the maximal ideal (p). Furthermore, we have that $R/(p) \cong \mathbb {F}_{p^d}$.

Proposition 2

([ACD+19]). The Lenstra constant of $R = GR(p^k, d)$ is $p^d$.

Whenever we need to explicitly represent elements $a \in R$, we will consider two options. The first one, which we will denote the additive representation, follows from Definition 8 and consists of the residue classes

$$\begin{aligned} a \equiv a_0 + a_1 \cdot \mathtt {X}+ \cdots + a_{d-1} \cdot \mathtt {X}^{d-1} \mod h(\mathtt {X}), \quad a_i \in \mathbb {Z}_{p^k}. \end{aligned}$$

(1)

The second option is what we shall call the matrix representation, which uses the embedding $\iota : \mathsf {GR}(p^k,d) \hookrightarrow \mathcal {M}_{d \times d}(\mathbb {Z}_{p^k})$ and represents a as $\iota (a)$. It will be instructive to discuss this embedding more explicitly for other parts of this work. Let us look at how the product between $a, b \in \mathsf {GR}(p^k,d)$ is computed. If we express a in its additive representation, $a = \sum _{\ell \in [d]}a_\ell \cdot \mathtt {X}^\ell$, multiplication by b can be seen as the homomorphism of free $\mathbb {Z}_{p^k}$-modules $\phi _b: \mathbb {Z}_{p^k}^d \rightarrow \mathbb {Z}_{p^k}^d$, which maps the coefficients of a’s additive representation to those of $c = \phi _b(a)$.

Notice that since $\mathsf {Im}(\iota ) \simeq \mathsf {GR}(p^k,d)$, we have that $\iota (a) \cdot \iota (b) = \iota (b) \cdot \iota (a)$. In other words, the matrices in $\mathsf {Im}(\iota )$ constitute a commutative subset of $\mathcal {M}_{d \times d}(\mathbb {Z}_{p^k})$.

3 Shamir’s Secret Sharing over Non-commutative Rings

Secret sharing schemes (SSS) are one of the most fundamental building blocks in secure computation. There are three properties which we usually want from SSS in MPC. The first one is t-privacy, meaning that no set of at most t shares reveals any information about the secret. The second one is $t+1$-reconstruction, which allows to reconstruct the secret from any subset of $t+1$ correct shares. The third one is linearity, which requires talking about specific algebraic structures. In our work, as we will be working over rings for which we do not assume commutativity, we need to distinguish between left and right linearity.

Definition 9

Let $C = \{(s, s_1, \ldots , s_n)\} \subseteq R^{n+1}$ be a SSS, where s is a secret and $s_1, \ldots , s_n$ are its shares. We say that C is a left (resp. right) linear secret sharing scheme if it is a left (resp. right) submodule of $R^{n+1}$. We will respectively denote the secret sharing of s by $[s], \langle s \rangle$. If C is a bisubmodule of $R^{n+1}$, then we simply call it a linear secret sharing scheme, which we denote as $\llbracket s \rrbracket$.

In Shamir’s secret sharing scheme, which was originally restricted to finite fields [Sha79], the submodule C is a Reed-Solomon code, i.e. $\llbracket s \rrbracket _t$ would be sampled from $C = \{(s,f(\alpha _1), \ldots , f(\alpha _n)): f \in \mathbb {F}[\mathtt {X}]_{\le t} \wedge s=f(\alpha _0)\}$. This was later on generalized to commutative rings containing big enough exceptional sets [ACD+19]. In this work, we observe that Reed-Solomon codes have been constructed even over non-commutative rings [QBC13]. Throughout this section we translate the relevant parts of [QBC13] to the LSSS language. Moreover, we fill some gaps about error correction left by the authors of [QBC13], we generalize standard secret reconstruction procedures from [DN07] and we show where do matrix rings fit in these results.

Beyond linearity, another desirable property for a SSS to have is that of (strong) multiplicativity. Briefly, such notion guarantees that (even in the presence of active adversaries) the product of two secrets a, b can be reconstructed as a function of the coordinate-wise product of their shares, $a_i \cdot b_i$. For a formal definition see [CDM00].

Theorem 4

Let R be a ring such that Z(R) contains an exceptional set $A=\{\alpha _0, \ldots , \alpha _n\}$ and let $t<n/3$. Then, we can define a Shamir-style strongly multiplicative linear secret sharing scheme over R. In more detail, a degree-t sharing $\llbracket s \rrbracket _t$ is sampled from:

$$\begin{aligned} \{(s,{f}^{\textsf {R}}(\alpha _1), \ldots , {f}^{\textsf {R}}(\alpha _n)): f \in \mathbb {F}[\mathtt {X}]_{\le t} \wedge s={f}^{\textsf {R}}(\alpha _0)\} \end{aligned}$$

Strong multiplicativity in the previous result woks as usual in Shamir’s LSSS. In more detail, given two shared values, $\llbracket a \rrbracket _t = (a,a_1,\ldots ,a_n)$ using a polynomial $f \in R[\mathtt {X}]_{\le t}$ and $\llbracket b \rrbracket _{t} = (b,b_1,\ldots ,b_n)$ using a polynomial $g \in R[\mathtt {X}]_{\le t}$, it holds that $\llbracket a\cdot b \rrbracket _{2t} = (ab, a_1 b_1,\ldots ,a_n b_n)$. This is due to the fact that the points $\alpha _i$ where f and g are evaluated at are contained in Z(R), and hence by Lemma 3 it holds that ${(f\cdot g)}^{\textsf {R}}(\alpha _i) ={f}^{\textsf {R}}(\alpha _i) \cdot {g}^{\textsf {R}}(\alpha _i)$, which is not generally the case for non-commutative polynomials.

Given the previous theorem, we can adapt the results of [BTH08, ACD+19] to work over non-commutative rings as the ones of the hypothesis without too much effort. This gives us the following result, for which a bit more details are given in the full version of this work. The increase on the size of the exceptional set is due to the use of so-called hyper-invertible matrices.

Corollary 2

Let R be a ring such that Z(R) contains an exceptional set of size at least 2n. Let $\mathcal {A}$ be an active adversary corrupting $t < n/3$ parties. There exists a perfectly secure, black-box MPC protocol with an amortized communication complexity of O(n) ring elements per gate.

If we relax the hypothesis of Theorem 4, so that we only ask from the elements of the exceptional set to commute with each other, rather than being in the centre of the ring, we can still build Shamir-style secret sharing schemes.

Theorem 5

Let R be a ring containing a commutative, exceptional set $A = \{\alpha _0, \ldots , \alpha _n\}$. Then, we can define a Shamir-style left-LSSS $[\cdot ]$ and a Shamir-style right-LSSS $\langle \cdot \rangle$ over R. These secret sharing schemes are not multiplicative.

We do not provide an explicit proof of the previous Theorem, but in Fig. 1 we show how to share a secret for the left-linear scheme $[\cdot ]$. The right-linear scheme $\langle \cdot \rangle$ would produce shares in an analogous way, setting instead $s_i = {f}^{\textsf {L}}(\alpha _i)$. The t-privacy and $t\,+1$-reconstruction properties are a consequence of Proposition 1. To see why these schemes are not multiplicative, remember that the evaluation maps are not ring homomorphisms in general, i.e. given $f,g \in R[\mathtt {X}]$, generally ${f}^{\textsf {R}}(\alpha _i) \cdot {g}^{\textsf {R}}(\alpha _i) \ne {(f\cdot g)}^{\textsf {R}}(\alpha _i)$. Hence, in contrast with Theorem 4, given $[a]_t = (a,{f}^{\textsf {R}}(\alpha _1),\ldots ,{f}^{\textsf {R}}(\alpha _n))$ and $[b]_t = (b,{g}^{\textsf {R}}(\alpha _1),\ldots ,{g}^{\textsf {R}}(\alpha _n))$, Lemma 3 is of no help now, since the $\alpha _i$ values are not in the centre any more. Note that we cannot simply impose for the sampled polynomial f in Fig. 1 to be in $A[\mathtt {X}]_{\le d}$. As an example, imagine the case when A is furthermore a subring of R. We would then have that ${f}^{\textsf {R}}(\alpha _0) \in A$, effectively restricting the values that can be secret shared to those in the subring A itself.

Fig. 1.

Sharing a secret using $[\cdot ]$.

3.1 Secret Sharing over Matrix Rings

As our more practical results are related to the ring $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, it will be useful to give already a more concrete analysis of how it fits with respect to Theorems 4 and 5, before returning to generic rings. We start by reminding the following basic result.

Lemma 5

The centre of $\mathcal {M}_{m \times m}(R)$, where R is a commutative ring, is the R-multiples of the identity matrix.

Besides which elements are in the centre of the ring, it is important that we identify exceptional sets in the ring. As we discussed in Sect. 2.4, there exists an embedding $\iota : \mathsf {GR}(p^k,m) \hookrightarrow \mathcal {M}_{m \times m}(\mathbb {Z}_{p^k})$. Hence, as the Lenstra constant of the former ring is $p^m$, that of $\mathcal {M}_{m \times m}(\mathbb {Z}_{p^k})$ has to be at least $p^m$. Furthermore, it can be proved that this is exactly the Lenstra constant of $\mathcal {M}_{m \times m}(\mathbb {Z}_{p^k})$, a result shown in the full version of this work.

Proposition 3

The Lenstra constant of $\mathcal {M}_{m \times m}(\mathbb {Z}_{p^k})$ is $p^m$.

Let us focus on the ring $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$. We know that Z(R) cannot contain exceptional sets of size bigger than two, so Theorem 4 is ruled out. The good news are that, since $\mathsf {GR}(2^k,m)$ (more precisely, $\mathsf {Im}(\iota )$) is a commutative subring of R, we can easily identify within R a commutative exceptional set of size $2^m$ and construct the secret sharing schemes described in Theorem 5 whenever $m > \log (n+1)$.

3.2 Error Correction and Robust Reconstruction

Let R be a finite ring and let $A=\{\alpha _0,\alpha _1,\ldots ,\alpha _n\}\subseteq R$ be an exceptional commutative set. Let $[s]_d = (s_1,\ldots ,s_n)$ be a secret-shared value $s\in R$ using a polynomial of degree at most d. For $i=1,\ldots ,n$, let $s_i' = s_i+\delta _i$, where at most e of the $\delta _i\in R$ are non-zero, with $n > d+2e$. Our goal is to recover $(s_1,\ldots ,s_n)$ from $(s_1',\ldots ,s_n')$. This is an essential primitive when designing MPC protocols based on Shamir secret-sharing, as it corresponds to reconstructing a secret-shared value from a given set of announced shares among which some of them could be incorrect due to adversarial behavior. This is achieved by a generalization of the Berlekamp-Welch decoding algorithm for Reed-Solomon codes to the non-commutative setting. Such result was exhibited in [QBC13], although many holes were left due to the general approach taken by the authors. For instance, a crucial step in the decoding algorithm lies in solving a system of linear equations over a non-commutative ring, which as we discuss later on is not a very well studied area and concrete algorithms should be developed for each particular instantiation. Motivated by this, and also for the sake of clarity and self-containment, we present below our own version of the generalization of the Berlekamp-Welch algorithm, filling in the holes left in [QBC13]. Below, we let $n'=d+2e+1$.

Generalization of the Berlekamp-Welch algorithm. Below we let F denote the subring of R made of finite sums of terms of the form $\alpha _{i_1}\cdot \alpha _{i_2}\cdots \alpha _{i_\ell }$. We say that two polynomials $p(\mathtt {X}),q(\mathtt {X})\in R[\mathtt {X}]$ satisfy the BW-conditions if:

• 1. $\deg (p)\le e$;

• 2. $\deg (q)\le d+e$;

• 3. $p(\mathtt {X})$ is monic;

• 4. $p(\mathtt {X}) \in F[\mathtt {X}]$;

• 5. For all $i=1,\ldots ,n'$, it holds that $s_i'\cdot p(\alpha _i) = q(\alpha _i)$.

We begin with the following claim.

Claim

There exists a pair $p(\mathtt {X}),q(\mathtt {X})\in R[\mathtt {X}]$ that satisfies the BW-conditions above.

Proof

Let $f(\mathtt {X}) = \sum _{i=0}^dc_i\mathtt {X}^i\in R_{\le d}[\mathtt {X}]$ such that $f(\alpha _i)=s_i$ for $i=1,\ldots ,n'$, guaranteed by Proposition 1, and define $p(\mathtt {X}) = \prod _{e_i\ne 0}(\mathtt {X}-\alpha _i)$ and $q(\mathtt {X}) = f(\mathtt {X})p(\mathtt {X})$. It can be easily verified, with the help of Lemma 3, that this choice of $p(\mathtt {X})$ and $q(\mathtt {X})$ satisfies the BW-conditions.    $\blacksquare$

The next claim shows that any other pair satisfying the BW-conditions is as good as the one guaranteed from the previous claim for the purpose of recovering $f(\mathtt {X})$.

Claim

Let $p(\mathtt {X}),q(\mathtt {X})$ be defined as in the proof of the previous claim, and suppose that $\hat{p}(\mathtt {X}), \hat{q}(\mathtt {X})$ satisfy the BW-conditions. Then $\hat{p}(\mathtt {X})$ divides $\hat{q}(\mathtt {X})$ and $\hat{q}(\mathtt {X})/\hat{p}(\mathtt {X}) = f(\mathtt {X})$.³

Proof

Consider the polynomial $r(\mathtt {X}) = \hat{q}(\mathtt {X})p(\mathtt {X}) - q(\mathtt {X})\hat{p}(\mathtt {X})$. In light of Lemma 3, taking into account that $p(\mathtt {X})\in F[\mathtt {X}]$, we have that for every $i=1,\ldots ,n'$:

$$r(\alpha _i) = \hat{q}(\alpha _i)p(\alpha _i) - q(\alpha _i)\hat{p}(\alpha _i) = s_i'\hat{p}(\alpha _i)p(\alpha _i) - s_i'p(\alpha _i)\hat{p}(\alpha _i) = 0.$$

Observe that in the last equality we have used the fact that $\hat{p}(\alpha _i)p(\alpha _i) = p(\alpha _i)\hat{p}(\alpha _i)$. Since $\deg (r)\le d+2e < n'$, it follows from Lemma 4 that $r(\mathtt {X})\equiv 0$, which shows that $\hat{q}(\mathtt {X})p(\mathtt {X}) = q(\mathtt {X})\hat{p}(\mathtt {X})$. Given that $q(\mathtt {X}) = f(\mathtt {X})p(\mathtt {X})$, we have that $\hat{q}(\mathtt {X})p(\mathtt {X}) = f(\mathtt {X})p(\mathtt {X})\hat{p}(\mathtt {X})$, which implies $(\hat{q}(\mathtt {X}) - f(\mathtt {X})\hat{p}(\mathtt {X}))\cdot p(\mathtt {X}) = 0$.

We claim that $\hat{q}(\mathtt {X}) - f(\mathtt {X})\hat{p}(\mathtt {X}) = 0$, which can be shown by proving that this polynomial evaluates to 0 in at least $d+e+1$ points on an exceptional set in light of Lemma 4. To see this, consider the evaluation of this polynomial at $\alpha _i$ for all i such that $e_i=0$. Observe that there are at least $n'-e = d+e+1$ such evaluation points. It is easy to see that in this case $p(\alpha _i)$ is invertible, so $(\hat{q}(\alpha _i) - f(\alpha _i)\hat{p}(\alpha _i))\cdot p(\alpha _i) = 0$ implies that $\hat{q}(\alpha _i) - f(\alpha _i)\hat{p}(\alpha _i)=0$, as required. At this point we see that $\hat{q}(\mathtt {X}) = f(\mathtt {X})\hat{p}(\mathtt {X})$, which concludes the proof of the main claim.    $\blacksquare$

Error Detection. Finally, if $n>d\,+\,e$ the parties may not be able to perform error correction, but they can still do error detection by checking if all the received shares $(s_1',\ldots ,s_n')$ are consistent with a polynomial of degree at most d (e.g. by using the first $d+1$ shares to interpolate such polynomial and checking that the remaining shares are consistent with it). If this is the case, since this polynomial is determined by any set of $d+1$ shares, it is in particular determined by the $n-e\ge d+1$ shares without errors.

Solving for the BW-conditions. In order to have an efficient decoder it remains to show how to find at least one pair $p(\mathtt {X}),q(\mathtt {X})$ that satisfies the BW-conditions. First, notice that by treating the coefficients of the unknown polynomials $p(\mathtt {X}),q(\mathtt {X})$ as unknowns, the BW-conditions transform into a system of $n'=d+2e+1$ linear equations on $d+2e+1$ variables over R.⁴ Unfortunately, to the best of our knowledge the theory of linear equations over general non-commutative rings is not very well understood, with only a few works considering concrete instantiations of some types of rings (e.g. [Ore31, Son75, DKH+12]). Since it is of particular interest to us, we develop in the full version of this work efficient algorithms to solve systems of linear equations for the matrix ring case $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{p^k})$.

Fig. 2.

Reconstructing secret-shared values efficiently to a single party.

3.3 Efficient Protocols for Secret Reconstruction

Given the above, a party that receives n shares of degree $\le d$, among which at most t can be corrupted by an adversary, can perform error detection if $t<n-d\le 2t$, and it can perform error correction if $2t<n-d$. We denote by $\varPi _{\scriptstyle \mathrm {PrivOpen}}([s]_d,P_r)$ the protocol in which all parties send their share of $[s]_d$ to $P_r$. If all parties are intended to learn the secret s, we make use of a protocol $\varPi _{\scriptstyle \mathrm {PublicOpen}}([s_0]_{d},\ldots ,[s_d]_{d})$ that opens a batch of secrets towards all the parties with an amortized communication complexity that is linear in n. This protocol is achieved by a natural generalization of the equivalent protocol in [DN07], except that great care must be taken when handling the different multiplications and polynomial evaluations when the ring is not commutative. This is described in detail in the full version of this work.

Finally, notice that the protocols $\varPi _{\scriptstyle \mathrm {PrivOpen}}, \varPi _{\scriptstyle \mathrm {PubOpen}}$ are currently described for $[\cdot ]$-sharings, but they can be naturally adapted to $\langle \cdot \rangle$-sharings by evaluating the polynomial $f(\mathtt {X})$ on the right and computing $\langle {f}^{\textsf {R}}(\alpha _i) \rangle = \sum _{j=0}^{t}\langle s_j \rangle \alpha _i^j$.

4 MPC in the Preprocessing Model

The goal of this section is to leverage the adaptations of Shamir’s secret sharing described in Sect. 3 to build an MPC protocol that operates directly over R, in a black-box way. We assume an active adversary corrupting t out of n parties, where it could hold either that $t<n/3$ or $t<n/2$. In the first case we can obtain guaranteed output delivery with perfect security, and in the second case we achieve perfect security with abort (both in the preprocessing model).

Multiparty computation can be obtained from any linear secret sharing scheme satisfying certain multiplicative properties, as shown in [CDM00]. As we proved in Corollary 2, even more modern and efficient techniques for MPC over commutative rings can be adapted to the non-commutative setting, assuming that there is a large enough exceptional set in the centre of the ring. The challenge in this section is, however, that we only assume the existence of a big enough commutative exceptional set, i.e. the conditions of Theorem 2.

Losing multiplicativity leads to most existing techniques for secret-sharing based MPC to fail. A clever solution when multilpicativity is lost is to resort to properties of the dual of the error-correcting code underlying the secret-sharing scheme [CDM00]. However, although as shown in [QBC13] the usual properties of the dual code of Reed-Solomon codes do carry over to non-commutative rings, this requires that the evaluation points constitute not only an exceptional set, but that they are also contained in Z(R). Unfortunately, this is precisely the assumption we do not want to make (and in fact, as said above, such assumption would yield a multiplicative LSSS directly).

Given the hurdles highlighted above, this work takes a different route. Our protocols are set in the offline/online paradigm, in which a set of input-independent correlated information is generated in a preprocessing phase, which is then used in an online phase once the inputs are known. By preprocessing the so-called Beaver triples, the online phase can be executed without relying on any multiplicativity property of the underlying secret-sharing scheme. However, due to non-commutativity, the usual approach to secure multiplication using Beaver triples does not directly work, as we will explain shortly. The rest of this section is then devoted to overcoming these issues and obtain a secure computation protocol in the preprocessing model, where we assume that the input-independent correlated data is given “for free”. Our protocols for instantiating such preprocessing phase will be discussed in Sect. 5.

4.1 A First Approach

We begin by considering the typical approach to Beaver-based multiplication, and discuss why it fails in our setting. Assume for a moment that R is commutative. A Beaver triple is a set of shared values $(\llbracket a \rrbracket , \llbracket b \rrbracket , \llbracket c \rrbracket )$ such that $a,b\in R$ are uniformly random and $c=a\cdot b$. Given two shared values $\llbracket x \rrbracket ,\llbracket y \rrbracket$, these can be multiplied by means of the following protocol:

• 1. Parties call $d = \varPi _{\scriptstyle \mathrm {PubOpen}}(\llbracket x \rrbracket - \llbracket a \rrbracket )$ and $e = \varPi _{\scriptstyle \mathrm {PubOpen}}(\llbracket y \rrbracket - \llbracket b \rrbracket )$.

• 2. Parties compute locally $\llbracket xy \rrbracket = \llbracket a \rrbracket e + d\llbracket b \rrbracket + \llbracket c \rrbracket + de$.

Privacy follows from the fact that the sensitive values x and y are being masked by uniformly random values a and b that are unknown to the adversary. Correctness follows from the fact that $xy = (d+a)(e+b) = ae+db+ab+de$, a relation that also holds even if R is non-commutative. Here we use the fact that, since $t<n/2$, the calls to $\varPi _{\scriptstyle \mathrm {PubOpen}}$ result in the parties learning the correct underlying secret or aborting (and in the stronger case that $t<n/3$ then $\varPi _{\scriptstyle \mathrm {PubOpen}}$ does not result in abort).

The issue with a non-commutative R is that, unless Z(R) contains a big enough exceptional set, the secret sharing scheme $[\cdot ]$ (resp. $\langle \cdot \rangle$) we can define is just a left (resp. right) submodule of $R^n$. In particular, the local operation $d\cdot [b]$ can be carried out, but $[a]\cdot e$ does not result in a $[\cdot ]$-shared value⁵. To address this complication, let $([a], [b], [c])$ be a triple. Assume the existence of “sextuples”, which are just triples of the form $([a], [b], [c])$ enhanced with shares of the form $(\langle a \rangle , [r], \langle r \rangle )$. These are produced by a functionality $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$.⁶ These tuples can be used to multiply $[x]$ and $[y]$ as follows:

• 1. Parties call $d = \varPi _{\scriptstyle \mathrm {PubOpen}}([x]_t - [a]_t)$, $e = \varPi _{\scriptstyle \mathrm {PubOpen}}([y]_t - [b]_t)$.

• 2. Parties call $f = \varPi _{\scriptstyle \mathrm {PubOpen}}(\langle a \rangle _t \cdot e + \langle r \rangle _t)$.

• 3. Parties compute locally $[xy]_t = d \cdot e + d \cdot [b]_t + f - [r]_t + [c]_t$

Privacy follows from the fact that sensitive data x and y is masked by the uniformly random values a and b before opening and also because, before reconstructing $a\cdot e$ (which could potentially leak information about a), the uniformly random mask r is applied. In terms of correctness, we observe that the final expression defining $[xy]_t$ is well defined given that only additions and multiplications on the left are used. Furthermore, the computation of f uses multiplication on the right on the sharings $\langle \cdot \rangle$, which admit such multiplications. The rest is simply a matter of using the definition of d, e, c and f in the final computation: $d\cdot e + d\cdot b + f - r + c = (x-a)\cdot (y-b) + (x-a)\cdot b + a\cdot (y-b) + r - r + a\cdot b = x\cdot y$.

4.2 Improving Round-Complexity

The protocol sketched in the previous section suffers from the issue that its round complexity is quite high, requiring 4 rounds per multiplication (two sequential calls to $\varPi _{\scriptstyle \mathrm {PubOpen}}$, each requiring 2 rounds). In MPC protocols networking is usually the most scarce resource, and it can be argued that round-count is even more sensitive than communication complexity, specially in wide area networks that have high latency. Therefore, the rest of this section is devoted to lowering the round count of each secure multiplication.

In order to achieve secure multiplication with no sequential calls to $\varPi _{\scriptstyle \mathrm {PubOpen}}$ in the non-commutative case, we modify the way multiplications are handled. First, each intermediate value of the computation x will not be represented by $[x]$, but rather by a pair $([\lambda _x],\mu _x)$, where $\lambda _x\in R$ is uniformly random and unknown to any party, and $\mu _x = x - \lambda _x$. Notice that this still maintains the privacy of x since the only public value is $\mu _x$, which perfectly hides x as it is being masked by $\lambda _x$, that is random and unknown to any party.

Suppose the parties have two shared values $([\lambda _x],\mu _x=x\,-\lambda _x)$ and $([\lambda _y],\mu _y=y\,-\lambda _y)$. To obtain a shared representation of their sum, the parties simply locally compute $([\lambda _x+\lambda _y],\mu _x+\mu _y)$. On the other hand, to securely multiply these shared values, the process is as follows. Let $[\lambda _z]$ be the random mask associated to the output of the multiplication. To obtain $([\lambda _z], \mu _z)$, the parties need to get the value $\mu _z = x\cdot y - \lambda _z$ in the clear. This is achieved by noticing that, since $x = \mu _x \,+\, \lambda _x$ and $y = \mu _y \,+\, \lambda _y$, it holds that $\mu _z = \mu _x\mu _y \,+\, \mu _x\lambda _y \,+\, \lambda _x\mu _y + \lambda _x\lambda _y \,-\, \lambda _z$. Assume that the parties have $[\lambda _x\lambda _y]$, which can be preprocessed as $\lambda _x$ and $\lambda _y$ are simply random values. If R was conmutative, then the parties could compute

$$[\mu _z] = \mu _x\mu _y + \mu _x[\lambda _y] + [\lambda _x]\mu _y + [\lambda _x\lambda _y] - [\lambda _z],$$

followed by opening $\mu _z$. This approach was followed in [BNO19] in order to improve the communication complexity of secure multiplication in the dishonest majority setting. It was also used in the context of honest majority in [ED20], both to minimize online communication complexity and in order to avoid selective failure attacks.

Unfortunately, when R is non-commutative, this approach cannot be carried out as we find the exact same issue we had in the previous section, namely that $[\lambda _x]\mu _y$ is not well defined as the secret-sharing scheme $[\cdot ]$ does not allow multiplication on the right. However, our crucial observation is that, unlike the traditional use of triples from Sect. 4.1, in this case the task is not to take a combination of sharings in order to obtain a new shared value but rather take a linear combination of sharings in order to open the result $\mu _z$. This difference turns out to be essential in order to devise a protocol for the non-commutative case that does not require sequential openings, which we describe in detail below. The overall idea of our protocol is that the parties do not really need to convert $\langle \lambda _x \rangle \mu _y$ to $[\lambda _x\mu _y]$ as in Sect. 4.1, which adds an extra opening round, but rather it is enough to open this part separately from the other part that uses the $[\cdot ]$-sharing, and then add the two opened values to obtain $\mu _z$. Some masking is necessary to ensure that each separate piece does not leak anything, but this is easily achievable, as we will describe next.

Preprocessing functionality. Unfortunately, resorting to this new approach does not allow us to use the functionality $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$ directly. Instead, we must resort to a similar but different type of preprocessing, which is captured by functionality for function-dependent preprocessing $\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}}$, which is formalized in detail in the full version. In a nutshell, this functionality also distributes tuples $([\lambda _x]_t, [\lambda _y]_t, [\lambda _x \cdot \lambda _y]_t, \langle \lambda _x \rangle _t, [r]_t, \langle r \rangle _t)$, except that, if $\lambda _x$ (resp. $\lambda _y$) is used to mask a value x (resp. y) for a given multiplication, then the same $\lambda _x$ (resp. $\lambda _y$) must be used for all multiplications involving x (resp. y) as a left (resp. right) input. Since the structure of the tuples returned depend on the way multiplications are arranged in the circuit, we refer to this type of preprocessing as function-dependent preprocessing. This is in contrast to the preprocessing from $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$ which only depends on (an upper bound on) the number of multiplications in the circuit and not on the way these are arranged.

Protocols for MPC in the $\boldsymbol{(\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}},\mathcal {F}_{\scriptstyle \mathrm {BC}})}$-hybrid model. Now we finally describe our protocol for MPC in the $(\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}},\mathcal {F}_{\scriptstyle \mathrm {BC}})$-hybrid model. The protocol $\varPi _{\scriptstyle \mathrm {Online}}$, described in Fig. 3 achieves guaranteed output delivery with perfect security against an active adversary corrupting $t<n/3$ parties, and it achieves perfect security with abort against an active adversary corrupting $t<n/2$ parties. The following makes use of a standard simulation-based proof which is provided in the full version of this work.

Fig. 3.

Online phase of our MPC protocol.

Theorem 6

Assume that $t<n/3$. Then protocol $\varPi _{\scriptstyle \mathrm {Online}}$ implements functionality $\mathcal {F}_{\scriptstyle \mathrm {MPC-GOD}}$ in the $(\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}},\mathcal {F}_{\scriptstyle \mathrm {BC}})$-hybrid model with perfect security.

We recall that the functionality $\mathcal {F}_{\scriptstyle \mathrm {BC}}$ can be instantiated with perfect security if $t<n/3$ [LSP82], which, together with Theorem 6, implies that there exists a protocol that instantiates $\mathcal {F}_{\scriptstyle \mathrm {MPC-GOD}}$ with perfect security in the $\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}}$-hybrid model.

Finally, in a similar way as the theorem above, the following is proved. The main difference lies in the fact that the simulator may send abort signals to the functionality $\mathcal {F}_{\scriptstyle \mathrm {MPC-abort}}$ if it detects that the adversary is sending inconsistent shares. This works since error detection in the $t<n/2$ case is possible.

Theorem 7

Assume that $t<n/2$. Then protocol $\varPi _{\scriptstyle \mathrm {Online}}$ implements functionality $\mathcal {F}_{\scriptstyle \mathrm {MPC-abort}}$ in the $(\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}},\mathcal {F}_{\scriptstyle \mathrm {BC}})$-hybrid model with satistical security.

5 Preprocessing

In this section we provide different protocols to realize the $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$ functionality when Z(R) does not contain a big enough exceptional set. Our presentation focuses in this simpler functionality, since $\mathcal {F}_{\scriptstyle \mathrm {F.D.Prep}}$ can be easily realized either in the $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$-hybrid or by slightly tweaking the protocols that implement $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$. In Sect. 5.1 we provide a generic protocol that only requires black-box access to the ring operations and the ability to sample random ring elements. On the downside, this theoretical result has a complexity of $\mathsf {poly}(n)$, in contrast with the more specialized protocol for matrices over commutative rings we provide in Sect. 5.2. By additionally getting black-box access to the commutative ring operations, this optimized protocol has O(n) communication complexity and $O(n\log n)$ computational complexity.

5.1 Generic, Black-Box Construction

Representing non-commutative ring arithmetic as operations in . We quickly recap the work of Ben-Or and Cleve [BC92]. Let $a \in R$, where R is a possibly non commutative ring. We will keep the invariant of representing such elements within the group of $3 \times 3$ invertible matrices over R, $\mathbb {G}= \mathsf {GL}_3(R)$, as follows:

$$\begin{aligned} M(a) = \begin{pmatrix} 1 &{} 0 &{} a \\ 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix} \end{aligned}$$

This allows us to compute additions as $M(a+b) = M(a) \cdot M(b)$. Multiplication is a bit more complicated. We can compute $M(a\cdot b) = J_1 \cdot M(b) \cdot J_2 \cdot M(a) \cdot J_3 \cdot M(b) \cdot J_4 \cdot M(a) \cdot J_5$, where the $J_i$ matrices are the following:

$$\begin{aligned} J_1 = \begin{pmatrix} 0 &{} 1 &{} 0 \\ -1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \end{pmatrix} J_2 = \begin{pmatrix} 0 &{} 0 &{} -1 \\ 1 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 \end{pmatrix} J_3 = \begin{pmatrix} 0 &{} 1 &{} 0 \\ 0 &{} 0 &{} 1 \\ 1 &{} 0 &{} 0 \end{pmatrix} J_4 = \begin{pmatrix} 0 &{} 0 &{} 1 \\ -1 &{} 0 &{} 0 \\ 0 &{} 1 &{} 0 \end{pmatrix} J_5 = \begin{pmatrix} -1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 0 \end{pmatrix} \end{aligned}$$

Preprocessing for MPC over non-commutative rings. Given the previous representation, we can use existing results for efficient MPC over non-abelian groups [DPS+12, CDI+13] in order to implement the $\mathcal {F}_{\scriptstyle \mathrm {Prep}}$ functionality required for the online phase in Sect. 4. In more detail, this can be computed as a constant-depth arithmetic circuit over R which we will represent as a series of products in the group $\mathbb {G}= \mathsf {GL}_3(R)$.

Note that the shares in the group-based protocol are according to the group law (i.e., they are “multiplicative shares”), whereas the protocols from Sect. 4 use Shamir’s secret sharing. One option would be to compute something like $[M(a)]_{\mathbb {G}} = \prod _{i=1}^{t+1} [M(a_i)]_{\mathbb {G}}$, $[M(b)]_{\mathbb {G}} = \prod _{i=1}^{t+1} [M(b_i)]_{\mathbb {G}}$ and $[M(c)]_{\mathbb {G}} = J_1 \cdot [M(b)]_{\mathbb {G}} \cdot J_2 \cdot [M(a)]_{\mathbb {G}} \cdot J_3 \cdot [M(b)]_{\mathbb {G}} \cdot J_4 \cdot [M(a)]_{\mathbb {G}} \cdot J_5$, as well as generating “double shares” of the form $[M(r)]_{\mathbb {G}}, [r]$ to e.g. extract $(c\,+\,r)$ from $\mathsf {PublicOpen}([M(c)]_{\mathbb {G}} \cdot [M(r)]_{\mathbb {G}})$ and then compute $[c] = (c+r) - [r]$.

Alternatively, we can employ the following, more direct approach. Let $A = \{0, \alpha _1, \ldots , \alpha _n\}$ be the commutative exceptional set defining the non-commutative sharing scheme $[\cdot ]$. Parties compute the following circuit, where each $P_i$ inputs random $f_j^i, g_j^i, h_j^i \in R$ and receives as output their corresponding shares of $([a], [b], [c])$, that is, $(f(\alpha _i), g(\alpha _i), h(\alpha _i))$.

$$\begin{aligned} a =&\sum _{i=1}^{t+1} f_0^i, \quad b = \sum _{i=1}^{t+1} g_0^i, \quad c = a \cdot b \\ f_j =&\sum _{i=1}^{t+1} f_j^i, \quad g_j = \sum _{i=1}^{t+1} g_j^i \quad h_j = \sum _{i=1}^{t+1} h_j^i, \quad j \in [t]\\ f(\alpha _\ell ) =\,&a + \sum _{j=1}^{t} f_j \alpha _\ell ^j, \ g(\alpha _\ell ) = b + \sum _{j=1}^{t} g_j \alpha _\ell ^j, \ h(\alpha _\ell ) = c + \sum _{j=1}^{t} h_j \alpha _\ell ^j, \quad \ell \in [n] \end{aligned}$$

The downside of these two generic approaches is that their respective protocols inherit the $\mathsf {poly}(n)$ complexity of [CDI+13]. On the upside, any improvement to MPC over non-abelian groups would directly translate to our blackbox constructions.

5.2 Concretely Efficient Preprocessing for Matrix Rings

For our more practical construction, which works over the ring $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, we describe how to implement $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$ using non-black-box protocols which are more efficient than the one from the previous section. Even though we specialize to matrices over $\mathbb {Z}_{2^{k}}$, our analysis and techniques can be generalized to matrices over other commutative rings.

Remember from Sect. 3.1 that $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ contains a commutative exceptional set of size $2^m$, which is why can only use the non-multiplicative secret sharing schemes from Theorem 5 that are linear only on one side.

In order to overcome the lack of multiplicativity, as $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}$ requires to produce values $([A],[B], [C])$ such that $C = A \cdot B$, we use an existing MPC protocol for computation over $\mathbb {Z}_{2^{k}}$. Given such an entry-wise protocol, we can trivially emulate the whole arithmetic of R. The issue is that, by doing this, we need to work over a big enough Galois extension of $\mathbb {Z}_{2^k}$, so that we can define a multiplicative, Shamir-style linear secret sharing scheme $\llbracket \cdot \rrbracket$⁷. Once we have computed this matrix product from the entry-wise shares of the matrices A and B, we need to convert $\llbracket \cdot \rrbracket$ sharings of the entries of A, B, C to sharings $[\cdot ]$ and $\langle \cdot \rangle$ over $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, so that parties obtain the tuple $[A], \langle A \rangle , [B], [C], [r], \langle r \rangle$ required for the online protocols in Sect. 4.

In particular, we will use the $\mathsf {InnerProd}$ CAFE from [DLS20], which can compute inner products of length $\delta \simeq d/2$ over $R = \mathsf {GR}(2^k,d)$ at the cost of just 2 sharings and a single opening in R. If one wants to calculate an inner product of length rd/2, the cost would be 2r sharings and a single opening in R. The following proposition captures the properties of $\mathsf {InnerProd}$ we are interested in, without getting into details about the specific construction.

Proposition 4

([DLS20]). Let $R=\mathsf {GR}(2^k,d)$ be a Galois Ring defined as $\mathbb {Z}_{2^k}[\mathtt {X}]/(h(\mathtt {X}))$. Let $\tilde{d}$ denote the degree of the second-highest degree monomial in $h(\mathtt {X})$. Let $\delta \in \mathbb {N}$ be such that $\delta < (d\,+1)/2$, $\delta < d\, - \tilde{d} \,+1$. There exist three $\mathbb {Z}_{2^{k}}$-linear homomorphisms $\mathsf {E}_{L}:(\mathbb {Z}_{2^{k}})^{\delta }\rightarrow R$, $\mathsf {E}_{R}:(\mathbb {Z}_{2^{k}})^{\delta }\rightarrow R$ and $\mathsf {E}_{out}:\mathbb {Z}_{2^{k}}\rightarrow R$ satisfying:

$$\begin{aligned} \mathsf {E}_{L}(a_1,\ldots ,a_\delta ) \cdot \mathsf {E}_{R}(b_1,\ldots ,b_\delta ) + \mathsf {E}_{out}(c) = \mathsf {E}_{out}(c + \sum _{\ell =1}^{\delta } a_\ell \cdot b_\ell ) \end{aligned}$$

Furthermore, the value $\mathsf {E}_{out}(c \,+\, \sum _{\ell =1}^{\delta } a_\ell \cdot b_\ell ) \in R$ does not reveal any information beyond $c + \sum _{\ell =1}^{\delta } a_\ell \cdot b_\ell \in \mathbb {Z}_{2^k}$.

Since the maps $\mathsf {E}_{L}, \mathsf {E}_{R}$ and $\mathsf {E}_{out}$ are homomorphisms of $\mathbb {Z}_{2^k}$-modules, the image of each of them can be seen as a $\mathbb {Z}_{2^k}$-submodule of $\mathsf {GR}(2^k,d)$. We will indistinctively refer to either these homomorphisms, or the $\mathbb {Z}_{2^k}$-modules they define as encodings.

By extension, we define how these encodings can be applied to matrices. Given $A' \in \mathcal {M}_{1 \times \delta }(\mathbb {Z}_{2^k})$, $B' \in \mathcal {M}_{\delta \times 1}(\mathbb {Z}_{2^k})$, for which we want to compute $C' = A' \cdot B'$, where $C' \in \mathbb {Z}_{2^k}$, we simply view the entries of $A', B'$ as elements of $(\mathbb {Z}_{2^k})^\delta$, to which we apply $\mathsf {E}_{L}$ and $\mathsf {E}_{R}$, respectively. In order to compute the product of $A, B \in \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, we need to introduce some additional notation. Let $\varDelta = \lceil m/\delta \rceil$. Let $\mathcal {A} \in \mathcal {M}_{m \times \delta \varDelta }(\mathbb {Z}_{2^k})$ (resp. $\mathcal {B} \in \mathcal {M}_{\delta \varDelta \times m}(\mathbb {Z}_{2^k})$) denote the matrix A padded with $\delta \varDelta \,-\, m$ columns of zeroes (resp. the matrix B padded with $\delta \varDelta - m$ rows of zeroes). For $\ell \in [m\varDelta ]$, let $A^{(\ell )} \in \mathcal {M}_{1 \times \delta }(\mathbb {Z}_{2^k}), B^{(\ell )} \in \mathcal {M}_{\delta \times 1}(\mathbb {Z}_{2^k})$ be submatrices such that

$$\begin{aligned} \mathcal {A} = \begin{pmatrix} A^{(1)} &{} A^{(2)} &{} \ldots &{} A^{(\varDelta )} \\ A^{(\varDelta + 1)} &{} A^{(\varDelta + 2)}&{} \ldots &{} A^{(2\cdot \varDelta )} \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ A^{((m-1)\cdot \varDelta + 1)} &{} A^{((m-1)\cdot \varDelta + 2)} &{} \ldots &{} A^{(m\cdot \varDelta )} \\ \end{pmatrix} \quad \mathcal {B} = \begin{pmatrix} B^{(1)} &{} B^{(\varDelta + 1)}&{} \ldots &{} B^{((m-1)\cdot \varDelta + 1)} \\ B^{(2)} &{} B^{(\varDelta + 2)}&{} \ldots &{} B^{((m-1)\cdot \varDelta + 2)} \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ B^{(\varDelta )} &{} B^{(2 \cdot \varDelta )} &{} \ldots &{} B^{(m\cdot \varDelta )} \end{pmatrix}, \end{aligned}$$

where $A^{(\varDelta )}, A^{(2\cdot \varDelta )}, \ldots , A^{(m\cdot \varDelta )}$ and $B^{(\varDelta )}, B^{(2\cdot \varDelta )}, \ldots , B^{(m\cdot \varDelta )}$ are the submatrices including the zero-padding. Let $\gamma \in \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ be a matrix that we will use to mask the result of $C = A \cdot B$ and let us denote the entries of $\gamma , C \in \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ as $C^{(\alpha ,\beta )}, \gamma ^{(\alpha ,\beta )} \in \mathbb {Z}_{2^k}$, where $\alpha , \beta \in \{1, \ldots , m\}$. Taking into account Definition 4, we can compute:

$$\begin{aligned} \mathsf {E}_{out}(C^{(\alpha ,\beta )} + {\gamma }^{(\alpha ,\beta )}) = \mathsf {E}_{out}({\gamma }^{(\alpha ,\beta )}) + \sum _{\ell =1}^{\varDelta } \mathsf {E}_{L}(A^{((\alpha -1)\varDelta +\ell )}) \cdot \mathsf {E}_{R}(B^{((\beta -1)\varDelta +\ell )}) \end{aligned}$$

Hyperinvertible matrices acting on commutative and non-commutative LSSS. Hyper-Invertible Matrices were introduced in [BTH08] as a tool for generating and checking linearly correlated randomness in the context of perfectly secure MPC over fields. We recall their properties in the full version of this work.

Let $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$, $d = 1 + \log n$, $S = \mathcal {M}_{n \times n}(\mathsf {GR}(2^k,d))$ and $M \in S$ be a hyper-invertible matrix. Let N be a $\mathbb {Z}_{2^k}$-module, such as those defined by commutative sharings of $\mathsf {E}_{L},\mathsf {E}_{R}$ or $\mathsf {E}_{out}$ encodings. Let $N_L$ (resp. $N_R$) be the left (resp. right) R-module defined by $[\cdot ]$ (resp. $\langle \cdot \rangle$). We want to define the action of multiplying by M on the left on those modules. We will refer to the morphisms they define as $\phi _M: N^{d \cdot n} \rightarrow N^{d \cdot n}$, $\psi ^L_M: N_L^{d \cdot n} \rightarrow N_L^{d\cdot n}$ and $\psi ^R_M: N_R^{d \cdot n} \rightarrow N_R^{d\cdot n}$.

Let us first look at the $\mathbb {Z}_{2^k}$-linear action of multiplying elements ${\boldsymbol{a}}\in N^d$ by $b \in \mathsf {GR}(2^k,d)$. As $N^d$ is a $\mathbb {Z}_{2^k}$-module, we know how to multiply its elements with scalars from $\mathbb {Z}_{2^k}$, but how can we multiply them with scalars from $\mathsf {GR}(2^k,d)$? The formal answer is tensor products: $N^d$ is isomorphic to $\mathsf {GR}(2^k,d) \otimes _{\mathbb {Z}_{2^k}} N$ as a $\mathbb {Z}_{2^k}$-module, but $\mathsf {GR}(2^k,d) \otimes _{\mathbb {Z}_{2^k}} N$ can also be seen as an $\mathsf {GR}(2^k,d)$-module compatible with the $\mathbb {Z}_{2^k}$-module structure $N^d$. Informally, one just needs to represent $b \in \mathsf {GR}(2^k,d)$ on its matrix representation $\iota (b)$ (see Sect. 2.4) and compute the matrix-vector product $\iota (b) \cdot {\boldsymbol{a}}$. We refer the reader interested in a more systematic exposition of the tensoring technique to the discussion on interleaved generalized secret sharing schemes in [CCXY18], which is restricted to fields but can be generalized to commutative rings [CRX19]. For those who want a more computational description, we recommend [DLS20, Section 4.1].

Given the description of the $\mathbb {Z}_{2^k}$-linear action of multiplying elements ${\boldsymbol{a}}\in N^d$ by $b \in \mathsf {GR}(2^k,d)$, we can deduce the $\mathbb {Z}_{2^k}$-linear action of multiplying elements in $(N^d)^n$ by the matrix M with entries in $\mathsf {GR}(2^k,d)$, giving result to the $\mathbb {Z}_{2^k}$-module homomorphism $\phi _M: (N^d)^n \rightarrow (N^d)^{n}$. We were talking about multiplying by the matrix $M \in S$ “on the left”, so whereas one could easily imagine how everything works fine when defining $\psi ^L_M: N_L^{d \cdot n} \rightarrow N_L^{d\cdot n}$, what happens with $\psi ^R_M: N_R^{d \cdot n} \rightarrow N_R^{d\cdot n}$? The important remark here is that $N_R$ is a right R-module, but it also a $\mathbb {Z}_{2^k}$-bimodule, so we can meaningfully “multiply by M on the left”, as we are interested in the $\mathbb {Z}_{2^k}$-linear action of multiplication by M. Moreover, the $\mathbb {Z}_{2^k}$-bimodule structure of $N_R$ is compatible with the right R-module structure, since Z(R) consists of the $\mathbb {Z}_{2^k}$-multiples of the identity matrix and hence $\forall a \in \mathbb {Z}_{2^k}, \langle b \rangle \in N_R$, we have that $a \cdot \langle b \rangle = \langle b \rangle \cdot a = \langle b \cdot a \rangle = \langle a\cdot b \rangle$. This leads us to the observation that:

$$\begin{aligned}&\psi ^L_M([\tilde{r}_{1,1}]_{t},\ldots ,[\tilde{r}_{1,d}]_{t}; \ldots ; [\tilde{r}_{n,1}]_{t},\ldots ,[\tilde{r}_{n,d}]_{t}) \nonumber \\&\qquad \qquad \qquad \qquad \qquad \,\,\, = \psi ^R_M(\langle \tilde{r}_{1,1} \rangle _{t},\ldots ,\langle \tilde{r}_{1,d} \rangle _{t}; \ldots ; \langle \tilde{r}_{n,1} \rangle _{t},\ldots ,\langle \tilde{r}_{n,d} \rangle _{t}) \end{aligned}$$

(2)

What is more, $\psi ^L_M$ and $\psi ^R_M$ will also be compatible with $\phi _M$, as they are all defined by the unique $\mathbb {Z}_{2^k}$-linear action that is defined by multiplying by M on the left that we describe above, where M is basically interpreted as a block matrix over $\mathbb {Z}_{2^{k}}$ taking the matrix representation of its entries in $\mathsf {GR}(2^k,d)$. The following Lemma is stated for $\psi ^L_M$, but it can be naturally adapted to $\psi ^R_M$ and $\phi _M$.

Lemma 6

Let $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$ and let $N_L$ denote the R-module defined by $[\cdot ]$. Let $M \in \mathcal {M}_{n \times n}(\mathsf {GR}(2^k,d))$ be a hyper-invertible matrix. Then, for all $A, B \subseteq [n]$ with $|A | + |B | = n$, there exists an isomorphism of R-modules $\psi ^L_M: N_L^{nd} \rightarrow N_L^{nd}$, $\psi ^L_M({\boldsymbol{x}}) = {\boldsymbol{y}}$, defined by the $\mathbb {Z}_{2^k}$-linear action of “multiplying ${\boldsymbol{x}}$ by M on the left”, such that $\psi ^L_M({\boldsymbol{x}}_A, {\boldsymbol{y}}_B) = ({\boldsymbol{x}}_{\bar{A}}, {\boldsymbol{y}}_{\bar{B}})$, where ${\bar{A}} = [n] {\setminus }A$ and ${\bar{B}} = [n] {\setminus }B$.⁸

See protocol $\varPi _{\scriptstyle \mathrm {Tuples}}$ on Fig. 4, Protocol $\varPi _{\scriptstyle \mathrm {Tuples-NC-Shares}}$ on Fig. 5 and $\varPi _{\scriptstyle \mathrm {TuplesCheck}}$ on Fig. 6. We provide a standard simulation-based proof of the following result in the full version of this work.

Fig. 4.

Preprocessing phase for MPC over $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$.

Fig. 5.

Preprocessing phase for MPC over $\mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$: Non-Commutative Shares.

Fig. 6.

Consistency check of the preprocessing phase for MPC over $R = \mathcal {M}_{m \times m}(\mathbb {Z}_{2^k})$.

Theorem 8

Assume that $t<n/3$. Then protocol $\varPi _{\scriptstyle \mathrm {Tuples}}$ on Fig. 4 implements functionality $\mathcal {F}_{\scriptstyle \mathrm {Tuples}}^{\mathsf {abort}}$ in the $\mathcal {F}_{\scriptstyle \mathrm {BC}}$-hybrid model with perfect security.

The case of $n/3\le t<n/2$ is discussed in the full version of this work.