What a lovely hat

Paper 2023/074

Random Sources in Private Computation

Abstract

We consider multi-party information-theoretic private computation. Such computation inherently requires the use of local randomness by the parties, and the question of minimizing the total number of random bits used for given private computations has received considerable attention in the literature. In this work we are interested in another question: given a private computation, we ask how many of the players need to have access to a random source, and how many of them can be deterministic parties. We are further interested in the possible interplay between the number of random sources in the system and the total number of random bits necessary for the computation. We give a number of results. We first show that, perhaps surprisingly, $t$ players (rather than $t+1$) with access to a random source are sufficient for the information-theoretic $t$-private computation of any deterministic functionality over $n$ players for any $t<n/2$; by a result of (Kushilevitz and Mansour, PODC'96), this is best possible. This means that, counter intuitively, while private computation is impossible without randomness, it is possible to have a private computation even when the adversary can control all parties who can toss coins (and therefore sees all random coins). For randomized functionalities we show that $t+1$ random sources are necessary (and sufficient). We then turn to the question of the possible interplay between the number of random sources and the necessary number of random bits. Since for only very few settings in private computation meaningful bounds on the number of necessary random bits are known, we consider the AND function, for which some such bounds are known. We give a new protocol to $1$-privately compute the $n$-player AND function, which uses a single random source and $6$ random bits tossed by that source. This improves, upon the currently best known results (Kushilevitz et al., TCC'19), at the same time the number of sources and the number of random bits (KOPRT19 gives a $2$-source, $8$-bits protocol). This result gives maybe some evidence that for $1$-privacy, using the minimum necessary number of sources one can also achieve the necessary minimum number of random bits. We believe however that our protocol is of independent interest for the study of randomness in private computation.