Private Computations in Networks: Topology versus Randomness
Lists
Only you see this
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...