Optimal-round preprocessing-MPC of polynomials over non-zero inputs via distributed random matrix

Secure multiparty computation (MPC) is an extensively studied research field in cryptography. It considers two main models—the plain model and the preprocessing model. The latter enables achieving objectives known to be unachievable for the plain model. One prominent example of such an objective is the perfectly secure evaluation of functions over private inputs, with the majority of the parties being dishonest. Recent results have shown that this objective can even be achieved in an optimal number of rounds of communication—two rounds. However, when the function to be evaluated is a polynomial with a possibly high degree over inputs taken from a large domain, existing solutions require an exponential amount of memory in the size of the domain. This paper presents preprocessing-MPC protocols for high-degree polynomials over non-zero inputs. These protocols are the first to have optimal round complexity, perfect security against coalitions of up to \(N-1\) out of N parties, and communication and space complexities that grow linearly with the number of monomials in the polynomial (independent of its degree). Furthermore, the results are extended to the client-server model. Namely, this paper presents a scheme that enables a user to outsource the storage of non-zero secrets to N distrusted servers and have the servers obliviously evaluate polynomials over the secrets in a single round of communication, perfectly secure against coalitions of up to \(N-1\) servers. These schemes are based on a novel secret sharing scheme, Distributed Random Matrix (DRM), first presented here. The DRM secret sharing scheme supports homomorphic multiplications and, after a single round of communication, supports homomorphic additions.

Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

1. The term active security refers to security against malicious parties. These parties might deviate from the protocol in an attempt to sabotage the computation process. Handling malicious parties is out of the scope of this work.

2. If every two-party functionality had a protocol with polynomial space complexity, this would imply an unexpected answer to a longstanding open question on the complexity of information-theoretic private information retrieval. See [10, 37].

3. Note that [34] suggests a specific example for a specific technique to cope with possible zeros, which is a special case for our techniques.

We thank Dani Berend for being involved during the entire research providing original ideas throughout. We thank the participants of the Crypto seminar, held at Tel Aviv University at July 18th 2019—Iftach Haitner, Ran Canetti, and students and researchers from the computer science department—for useful comments.

Research partially supported by the Lynne and William Frankel Center for Computer Science, the Rita Altura Trust Chair in Computer Science and also supported by a grant from the Ministry of Science, Technology and Space, Infrastructure Research in the Field of Advanced Computing and Cyber Security, the Israel & the Japan Science and Technology Agency (JST), and the German Research Funding Organization (DFG, Grant#8767581199).

Authors and Affiliations

1. Ben-Gurion University of the Negev, Beer-Sheva, Israel

   Dor Bitan & Shlomi Dolev

Corresponding author

Correspondence to Dor Bitan.

Conflict of interest

The authors declare that they have no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

1.1 A non-zero inputs and general functions

We now show some simple ways in which our schemes may be adjusted to support evaluation of arbitrary functions over possibly-zero inputs. We stress that the performances of the resulting schemes are often inferior to those of existing solutions. We present these ways mainly to show that, theoretically, our approach is capable of supporting general scenarios.^{Footnote 3}

First, we note that any function \(f : \mathbb {F}_{p}^N \rightarrow \mathbb {F}_{p}\) can be represented as a multivariate polynomial. This representation may be obtained, for example, by solving a system of linear equations, or using other polynomial interpolation methods. Due to Fermat’s little theorem, that states that \(x^p \equiv x \pmod {p}\), f can be written as a polynomial of degree at most \(N(p-1)\) and with at most \(p^N\) monomials. Namely, one may write

where \(\mathcal {L}=\{0,\dots ,p-1\}^N\), for appropriate elements \(a_l\in \mathbb {F}_{p}\).

Next, if f is a Boolean function, our scheme may be used to support MPC of f by working in \(\mathbb {F}_{2}\). A True Boolean value is \(1\in \mathbb {F}_{2}\) and a False Boolean value is \(0\in \mathbb {F}_{2}\). Boolean operations may be identified with field operations in the following way. The \(\wedge\) operation is identified with \(\mathbb {F}_{2}\) multiplication, the \(\oplus\) operation with \(\mathbb {F}_{2}\) addition, and the \(\lnot\) operation with adding 1 in \(\mathbb {F}_{2}\). The \(\vee\) operation of two literals is identified with \(x+y+xy\), where x and y are the elements of \(\mathbb {F}_{2}\) corresponding to the literals. Then, given a Boolean formula \(\varphi\) over Boolean literals \(b_1,\dots ,b_M\in \{True,False\}\), one can take the \(\mathbb {F}_{2}\) correspondents \(s_1,\dots ,s_M\in \mathbb {F}_{2}\) of \(b_1,\dots ,b_M\), and evaluate the Boolean formula \(\varphi :\{True,False\}^M \rightarrow \{True,False\}\) using the polynomial \(\tilde{\varphi }: \mathbb {F}_{2}^M \rightarrow \mathbb {F}_{2}\), obtained by replacing Boolean operations and literals with their \(\mathbb {F}_{2}\) correspondents.

Now, the communication and space complexities of our schemes are analyzed with respect to the number k of monomials in the polynomial representation of the function. Most of the known MPC schemes assume that f is given as an arithmetic circuit, and their communication and space complexities are analyzed with respect to the size s and depth d of the circuit. In order to (asymptotically) compare the performances of our schemes to those of a different scheme that assumes f is given as a circuit with size s and depth d, one must write k in terms of s and d. For an arbitrary f, that task might be hard. In general, consider the following question.

What is the relation between the size and depth of a circuit which computes an arbitrary function f and the size of a polynomial which computes f?

This question is an open problem, rooted in the algebraic analog of the \(P{\mathop {=}\limits ^{?}}NP\) problem, suggested by Valiant in [36], and is out of the scope of this paper.

So far, we have shown how MPC of Boolean or arithmetic functions reduces to MPC of polynomials over finite fields. This reduction still does not make our schemes suitable for all Boolean and arithmetic functions, since our schemes assume that the inputs are non-zero elements of the field. Next, we suggest several ways of handling possibly-zero inputs.

First, we suggest the q-bounded approach. Let \(s=(s_1, \dots , s_N)\in \mathbb {F}_{p}^N\). One can compute f(s) by performing operations in \(\mathbb {F}_{p}\) according to the representation of f as a multivariate polynomial. The same result is obtained if one computes f(s) over the positive integers and then takes the result modulo p. Formally, for each entry \(s_j\) of s, let \(a_j\) denote the minimal positive integer such that \(a_j \equiv s_j \pmod {p}\). Then, performing the computation over the \(a_j\)’s using integer operations one obtains an integer result \(f(s)_\mathbb {N}\), such that \(f(s)_\mathbb {N}\equiv f(s) \pmod {p}\). If q is a prime number such that for every \(s\in \mathbb {F}_{p}^N\), computation of f(s) over the integers yields an integer result, \(f(s)_\mathbb {N}\), which is smaller than q, then f is q-bounded. Since there are at most \(p^N\) monomials in f, for every \(s\in \mathbb {F}_{p}^N\) it holds that \(f(s)_\mathbb {N}<p^N\cdot (p-1)\cdot (p^{p-1})^N=p^N\cdot (p-1) \cdot p^{Np-N}=(p-1)\cdot p^{Np}\). Hence, f is q bounded for a prime q larger than \((p-1)\cdot p^{Np}\). In practice, one may find a smaller prime \(q'\) for which f is \(q'\)-bounded.

Now, we can use this fact to evaluate \(\mathbb {F}_{p}\)-polynomials over possibly-zero inputs by working in \(\mathbb {F}_{q}\) for large enough q. To this end we present the DRM two-round OTS-qB scheme. OTS-qB supports evaluating polynomials over possibly-zero inputs by embedding \(\mathbb {F}_{p}\) in a larger field, \(\mathbb {F}_{q}\), and using OTS as a subroutine. The larger field \(\mathbb {F}_{q}\) is chosen to satisfy the condition that f is q-bounded. The embedding is performed as follows. For \(s_j\in \mathbb {F}_{p}\), let \(\sigma _j\) denote the minimal positive integer such that \(\sigma _j \equiv s_j \pmod {p}\). Let \(\tilde{s}_j \equiv \sigma _j \pmod {q}\) be the \(\mathbb {F}_{q}\) correspondent of \(s_j\) in the q world. Let \(\tilde{s}=(\tilde{s}_1,\dots ,\tilde{s}_N)\). Now, let \(\tilde{f}:\mathbb {F}_{q}^N\rightarrow \mathbb {F}_{q}\) denote the function corresponding to f in the q-world. That is, \(\tilde{f}\) is obtained from f by replacing the leading coefficients of the monomials with their q-world correspondents. OTS-qB may be invoked by the parties to find f(s).

Theorem A.1

OTS-qB is a two-round N-party P-MPC scheme for arithmetic functions which has perfect correctness, perfect passive security, threshold \(N-1\), communication complexity \(\mathcal {O}(kN^3n2^n)\), space complexity \(\mathcal {O}(kN^2n2^n)\), and f-independent CR.

Proof

Since all q-world inputs are non-zero elements of \(\mathbb {F}_{q}\), security of OTS-qB follows from that of OTS. Correctness follows from that of OTS and the fact that f is q-bounded. By construction, the round complexity is two. Now, in OTS-qB, all the messages and the CR are \(\mathbb {F}_{q}\) elements. At the worst case, \(q\approx p^{pN}\), and hence, the number of bits required for each element is \(\lceil \log q \rceil \approx \log \bigl (p^{pN}\bigr ) =pN \log p=2^{\log p}N\log p=nN2^n.\) Since the number of messages and amount of CR remains unchanged, the exact space and communication complexities of OTS-qB are obtained from those of OTS by replacing n with \(nN2^n\). \(\square\)

OTS-qB solves the general case by replacing \(\mathbb {F}_{p}\) elements with \(\mathbb {F}_{q}\) elements, hence the factor \(2^n\). OTS-IS and OTS-IS\(_2\), which we now present, avoid the \(2^n\) factor. Instead, these schemes replace f with a K-monomials version of it.

The DRM two-round OTS-IS scheme solves the general case by splitting each input to a sum of two non-zero elements, and replacing f with the split-inputs version of f. That is, for a polynomial f, let \(\varphi :\mathbb {F}_{p}^{2N}\rightarrow \mathbb {F}_{p}\) denote the function obtained from f by replacing each variable \(x_i\) of f with the sum of two variables, \(z_i\) and \(w_i\), as follows:

where \(\lambda =(\lambda _1,\dots ,\lambda _{2N})\), \(\Lambda =\{0,1,\dots ,p-1\}^{2N}\), and \(b_\lambda \in \mathbb {F}_{p}\). \(\varphi\) is the split-inputs version of f. We note that, since f is a polynomial of N variables, \(k\le p^N\), and since \(\varphi\) is a polynomial of 2N variables, \(K\le p^{2N}=(p^N)^2\).

Now, if \(p\ne 2\), OTS-IS may be invoked by the parties to find f(s).

Theorem A.2

OTS-IS is a two-round N-party P-MPC scheme for \(\mathbb {F}_{p}\) functions (\(p\ne 2\)) which has perfect correctness, perfect passive security, threshold \(N-1\), f-independent CR, communication complexity \(\mathcal {O}(N^2nK)\), and space complexity \(\mathcal {O}(NnK)\), where K is the number of monomials of the split-inputs version of f.

Proof

Correctness follows from that of OTS and from the observation that if \(\alpha _i,\beta _i\in \mathbb {F}_{p}\) (\(1\le i\le N\)) are such that for every \(i\in [N]\) it holds that \(s_i=\alpha _i+\beta _i\), then \(f(s_1,\dots ,s_N)=\varphi (\alpha _1,\dots ,\alpha _N,\beta _1,\dots ,\beta _N)\). The security and complexity properties follow immediately from those of OTS. \(\square\)

Now, in \(\mathbb {F}_{2}\), 1 cannot be written as a sum of two non-zero elements. This is the reason for the requirement \(p\ne 2\) in Theorem A.2. OTS-IS\(_2\) solves the case \(p=2\) by embedding \(\mathbb {F}_{2}\) in \(\mathbb {F}_{3}\) and using OTS-IS as a subroutine. The embedding is performed as follows. The elements \(0,1\in \mathbb {F}_{2}\) are identified with \(0,1\in \mathbb {F}_{3}\). For \(s_j\in \mathbb {F}_{2}\) let \(\overline{s_j}\) denote the \(\mathbb {F}_{3}\) correspondent of \(s_j\). \(\mathbb {F}_{2}\) operations are identified with \(\mathbb {F}_{3}\) operations as follows. \(\mathbb {F}_{2}\)-multiplication is identified with \(\mathbb {F}_{3}\)-multiplication, and \(\mathbb {F}_{2}\)-addition is identified with \(Add:\mathbb {F}_{3}^2\rightarrow \mathbb {F}_{3}\), \(Add(x,y)=x+y+xy\). Let \(\overline{f}:\mathbb {F}_{3}^N\rightarrow \mathbb {F}_{3}\) denote the \(\mathbb {F}_{3}\) correspondent of f. That is, \(\overline{f}\) is obtained from f by replacing the \(\mathbb {F}_{2}\)-operations ‘\(\cdot\)’ and ‘\(+\)’ of f with the \(\mathbb {F}_{3}\)-operations ‘\(\cdot\)’ and ‘Add’. The parties may invoke OTS-IS\(_2\) to find f(s).

Theorem A.3

OTS-IS\(_2\) is a two-round N-party P-MPC scheme for arithmetic functions over \(\mathbb {F}_{2}\) which has perfect correctness, perfect passive security, threshold \(N-1\), f-independent CR, communication complexity \(\mathcal {O}(N^2nK)\), and space complexity \(\mathcal {O}(NnK)\), where K is the number of monomials of the split-input version of the \(\mathbb {F}_{3}\) correspondent of f.

Reprints and permissions