CryptoDB
Paper: Random Sources in Private Computation
Authors: 


Download:  
Conference:  ASIACRYPT 2022 
Abstract:  We consider multiparty informationtheoretic 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 informationtheoretic tprivate 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 1privately compute the nplayer 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 2019), at the same time the number of sources and the number of random bits ((Kushilevitz et al., TCC 2019) gives a 2source, 8bits protocol). This result gives maybe some evidence that for 1privacy, 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. 
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt202232527, title={Random Sources in Private Computation}, publisher={SpringerVerlag}, author={Geoffroy Couteau and Adi Rosén}, year=2022 }