Private Computations in Networks: Topology versus Randomness

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Abstract

In a distributed network, computing a function privately requires that no participant gains any additional knowledge other than the value of the function.We study this problem for incomplete networks and establish a tradeoff between connectivity properties of the network and the amount of randomness needed. First, a general lower bound on the number of random bits is shown. Next, for every k ≥2 we design a quite efficient (with respect to randomness) protocol for symmetric functions that works in arbitrary k-connected networks. Finally, for directed cycles that compute threshold functions privately almost matching lower and upper bounds for the necessary amount of randmoness are proven.
BibTeX
@inproceedings{jakoby2003private,
  author = {Andreas Jakoby and Maciej Liskiewicz and Rüdiger Reischuk},
  title = {{Private Computations in Networks: Topology versus Randomness}},
  booktitle = {STACS},
  year = {2003},
  doi = {10.1007/3-540-36494-3\_12},
}

Loading related content...

Figure