### 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.

Original language | Undefined |
---|---|

Pages (from-to) | 341-357 |

Number of pages | 17 |

Journal | Journal of cryptology |

Volume | 19 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2006 |

### Keywords

- Private computation
- randomness
- EWI-21274
- Connectivity
- Secure multi-party computation
- Parity
- IR-79425
- Secure function evaluation

## Cite this

Bläser, M., Jakoby, A., Liśkiewicz, M., & Manthey, B. (2006). Private computation: k-connected versus 1-connected networks.

*Journal of cryptology*,*19*(3), 341-357. https://doi.org/10.1007/s00145-005-0329-x