Fulltext

Private Computation: k-Connected versus 1-Connected Networks

Bläser, Markus ; Jakoby, Andreas ; Liskiewicz, Maciej ; Manthey, Bodo

In: Journal of Cryptology, 2006, vol. 19, no. 3, p. 341-357

Ajouter à la liste personnelle
    Titre
    • Private Computation: k-Connected versus 1-Connected Networks
    Auteur
    • Bläser, Markus. Institut fur Theoretische Informatik, ETH Zurich, 8092 Zurich, Switzerland
    • Jakoby, Andreas. Institut fur Theoretische Informatik, Universitat zu Lubeck, Ratzeburger Allee 160, 23538 Lubeck, Germany
    • Liskiewicz, Maciej. Institut fur Theoretische Informatik, Universitat zu Lubeck, Ratzeburger Allee 160, 23538 Lubeck, Germany
    • Manthey, Bodo. Institut fur Theoretische Informatik, Universitat zu Lubeck, Ratzeburger Allee 160, 23538 Lubeck, Germany
    Type de document
    • Postprint
    Langue
    • Anglais
    Publié dans
    • Journal of Cryptology, 2006, vol. 19, no. 3, p. 341-357. Springer-Verlag; www.springer-ny.com
    Autre version électronique
    Identifiant OAI-PMH
    • oai:doc.rero.ch:312681
    Summary
    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