Welcome to the resource topic for 2019/1024
Title:
Optimal-Round Preprocessing-MPC via Polynomial Representation and Distributed Random Matrix
Authors: Dor Bitan, Shlomi Dolev
Abstract: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.
ePrint: https://eprint.iacr.org/2019/1024
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .