Paper 2019/1024

Optimal-Round Preprocessing-MPC via Polynomial Representation and Distributed Random Matrix

Dor Bitan and Shlomi Dolev


We present preprocessing-MPC schemes of arithmetic functions with optimal round complexity, function-independent correlated randomness, and communication and space complexities that grow linearly with the size of the function. We extend our results to the client-server model and present a scheme which enables a user to outsource the storage of confidential data to $N$ distrusted servers and have the servers perform computations over the encrypted data in a single round of communication. We further extend our results to handle Boolean circuits. All our schemes have perfect passive security against coalitions of up to $N-1$ parties. Our schemes are based on a novel secret sharing scheme, Distributed Random Matrix (DRM), which we present here. The DRM secret sharing scheme supports homomorphic multiplications, and, after a single round of communication, supports homomorphic additions. Our approach deviates from standard conventions of MPC. First, we consider a representation of the function f as a multivariate polynomial (rather than an arithmetic circuit). Second, we divide the problem into two cases. We begin with solving the Non-Vanishing case, in which the inputs are non-zero elements of $F_p$. In this case, our schemes have space complexity $O(nkN)$ and communication complexity $O(nk(N^2))$, where $n$ is the size of the input, and $k$ is the number of monomials of the function. Then, we present several solutions for the general case, in which some of the secrets can be zero. In these solutions, the space and communication complexities are either $O(nk(N^2)(2^n))$ and $O(nk(N^3)(2^n))$, or $O(nkN)$ and $O(nk(N^2))$, respectively, where $K$ is the size of a modified version of $f$. $K$ is bounded by the square of the maximal possible size of $k$.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
MPC with preprocessingcorrelated randomnessoptimal round complexityhomomorphic secret sharingperfect securitydistributed cryptography
Contact author(s)
dorbi @ post bgu ac il
2020-11-21: revised
2019-09-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dor Bitan and Shlomi Dolev},
      title = {Optimal-Round Preprocessing-MPC via Polynomial Representation and Distributed Random Matrix},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1024},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.