Private computation: k-connected versus 1-connected networks

Bläser, Markus and Jakoby, Andreas and Liśkiewicz, Maciej and Manthey, Bodo (2006) Private computation: k-connected versus 1-connected networks. Journal of Cryptology, 19 (3). pp. 341-357. ISSN 0933-2790

PDF
Restricted to UT campus only: Request a copy
137Kb

Abstract:	We study the role of connectivity of communication networks in private computations under information theoretical settings in the honest-but-curious model. We show that some functions can 1-privately be computed even if the underlying network is 1-connected but not 2-connected. Then we give a complete characterisation of non-degenerate functions that can 1-privately be computed on non-2-connected networks. Furthermore, we present a technique for simulating 1-private protocols that work on arbitrary (complete) networks on $k$ -connected networks. For this simulation, at most $\begin{equation}(1 - \frac{k}{n-1}) \cdot L\end{equation}$ additional random bits are needed, where $L$ is the number of bits exchanged in the original protocol and $n$ is the number of players. Finally, we give matching lower and upper bounds for the number of random bits needed to 1-privately compute the parity function on $k$ -connected networks, namely $\begin{equation}\lceil \frac{n-2}{k-1}\rceil - 1\end{equation}$ random bits for networks consisting of $n$ players.
Item Type:	Article
Copyright:	© 2006 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/79425
Official URL:	http://dx.doi.org/10.1007/s00145-005-0329-x
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page