Amortizing randomness in private multiparty computations

Authors:
  • EKEyal Kushilevitz
    Eyal Kushilevitz
  • RORafail Ostrovsky
    Rafail Ostrovsky
  • ARAdi Rosén
    Adi Rosén
Open Access
Publisher website
Google Scholar
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 by re-using the same ` random bits we can significantly speedup the round-complexity of each computation compared to what is achieved by the naive strategy of partitioning the...