Amortizing randomness in private multiparty computations

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 l 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 l random bits between the computations. Moreover, we prove that our protocols are optimal in the amount of randomness they require.