Paper 2023/074
Random Sources in Private Computation
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 $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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2022
 Keywords
 secure computationrandomness
 Contact author(s)

couteau @ irif fr
adiro @ irif fr  History
 20230123: approved
 20230122: received
 See all versions
 Short URL
 https://ia.cr/2023/074
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/074, author = {Geoffroy Couteau and Adi Rosén}, title = {Random Sources in Private Computation}, howpublished = {Cryptology ePrint Archive, Paper 2023/074}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/074}}, url = {https://eprint.iacr.org/2023/074} }