Biblio

Motivated by applications in cryptography, we introduce and study the problem of distribution design. The goal of distribution design is to find a joint distribution on \$n\$ random variables that satisfies a given set of constraints on the marginal distributions. Each constraint can either require that two sequences of variables be identically distributed or, alternatively, that the two sequences have disjoint supports. We present several positive and negative results on the existence and efficiency of solutions for a given set of constraints. Distribution design can be seen as a strict generalization of several well-studied problems in cryptography. These include secret sharing, garbling schemes, and non-interactive protocols for secure multiparty computation. We further motivate the problem and our results by demonstrating their usefulness towards realizing non-interactive protocols for ad-hoc secure multiparty computation, in which any subset of the parties may choose to participate and the identity of the participants should remain hidden to the extent possible.

We present a unified framework for studying secure multiparty computation (MPC) with arbitrarily restricted interaction patterns such as a chain, a star, a directed tree, or a directed graph. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns, such as those studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014). Since restricted interaction patterns cannot always yield full security for MPC, we start by formalizing the notion of "best possible security" for any interaction pattern. We then obtain the following main results: Completeness theorem. We prove that the star interaction pattern is complete for the problem of MPC with general interaction patterns. Positive results. We present both information-theoretic and computationally secure protocols for computing arbitrary functions with general interaction patterns. We also present more efficient protocols for computing symmetric functions, both in the computational and in the information-theoretic setting. Our computationally secure protocols for general functions necessarily rely on indistinguishability obfuscation while the ones for computing symmetric functions make simple use of multilinear maps. Negative results. We show that, in many cases, the complexity of our information-theoretic protocols is essentially the best that can be achieved. All of our protocols rely on a correlated randomness setup, which is necessary in our setting (for computing general functions). In the computational case, we also present a generic procedure to make any correlated randomness setup reusable, in the common random string model. Although most of our information-theoretic protocols have exponential complexity, they may be practical for functions on small domains (e.g., f0; 1g20), where they are concretely faster than their computational counterparts.