Amortizing Randomness in Private Multiparty Computations
Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosen
Abstract: We study the relationship between the number of rounds needed to repeatedly perform a private computation (i.e., where there are many sets of inputs sequentially given to the players on which the players must compute a function privately) and the overall randomness needed for this task. For the XOR function, we show that for k sets of inputs, if instead of using totally fresh (i.e., independent) random bits for each of these k sets of inputs, we re-use the same \ell random bits then we can significantly speedup the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the \ell random bits between the k computations.
comment: Appeared In Proceedings of Seventeenth Annual ACM Symposium on Principles of Distributed Computing (PODC-98)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |