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, by re-using the same $\ell$ random bits, we can significantly speed up the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the $\ell$ random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.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, by re-using the same $\ell$ random bits, we can significantly speed up the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the $\ell$ random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.

SIAM Journal on Discrete MathematicsJan 1, 20037 citations

Amortizing randomness in private multiparty computations

Eyal Kushilevitz Z, Rafail Ostrovsky, Adi Rosén

IntroductionWe 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 f! 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 fJ random bits between the k computations.IntroductionWe 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 f! 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 fJ random bits between the k computations.

ACM Symposium on Principles of Distributed Computing (PODC)Jan 1, 199813 citations

Random Sources in Private Computation

Geoffroy Couteau, Adi Rosén

Lecture notes in computer scienceJan 1, 20221 citation

\ell

random bits, we can significantly speed up the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the

\ell

random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.