**
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 |