# 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 -connected networks. For this simulation, at most additional random bits are needed, where is the number of bits exchanged in the original protocol and 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 -connected networks, namely random bits for networks consisting of players. |

Item Type: | Article |

Copyright: | © 2006 Springer |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

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 |

Repository Staff Only: item control page