Private Computation: k-Connected versus 1-Connected Networks

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 be 1-privately 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 be 1-privately 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 \((1 - k/(n - 1)) \cdot L\) 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 compute the parity function on k-connected networks 1-privately, namely \(\lceil (n - 2)/(k - 1) \rceil - 1\) random bits for networks consisting of n players.

Authors and Affiliations

1. Institut fur Theoretische Informatik, ETH Zurich, 8092 Zurich, Switzerland

   Markus Bläser

2. Institut fur Theoretische Informatik, Universitat zu Lubeck, Ratzeburger Allee 160, 23538 Lubeck, Germany

   Andreas Jakoby, Maciej Liskiewicz & Bodo Manthey

Corresponding authors

Correspondence to Markus Bläser, Andreas Jakoby, Maciej Liskiewicz or Bodo Manthey.

Reprints and permissions