Paper 2019/1094

Is Information-Theoretic Topology-Hiding Computation Possible?

Marshall Ball, Elette Boyle, Ran Cohen, Tal Malkin, and Tal Moran


Topology-hiding computation (THC) is a form of multi-party computation over an incomplete communication graph that maintains the privacy of the underlying graph topology. Existing THC protocols consider an adversary that may corrupt an arbitrary number of parties, and rely on cryptographic assumptions such as DDH. In this paper we address the question of whether information-theoretic THC can be achieved by taking advantage of an honest majority. In contrast to the standard MPC setting, this problem has remained open in the topology-hiding realm, even for simple "privacy-free" functions like broadcast, and even when considering only semi-honest corruptions. We uncover a rich landscape of both positive and negative answers to the above question, showing that what types of graphs are used and how they are selected is an important factor in determining the feasibility of hiding topology information-theoretically. In particular, our results include the following. We show that topology-hiding broadcast (THB) on a line with four nodes, secure against a single semi-honest corruption, implies key agreement. This result extends to broader classes of graphs, e.g., THB on a cycle with two semi-honest corruptions. On the other hand, we provide the first feasibility result for information-theoretic THC: for the class of cycle graphs, with a single semi-honest corruption. Given the strong impossibilities, we put forth a weaker definition of distributional-THC, where the graph is selected from some distribution (as opposed to worst-case). We present a formal separation between the definitions, by showing a distribution for which information theoretic distributional-THC is possible, but even topology-hiding broadcast is not possible information-theoretically with the standard definition. We demonstrate the power of our new definition via a new connection to adaptively secure low-locality MPC, where distributional-THC enables parties to "reuse" a secret low-degree communication graph even in the face of adaptive corruptions.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2019
secure multiparty computationtopology-hiding computationbroadcastfoundations
Contact author(s)
marshall @ cs columbia edu
elette boyle @ idc ac il
rancohen @ ccs neu edu
tal @ cs columbia edu
talm @ idc ac il
2020-02-21: last of 3 revisions
2019-09-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marshall Ball and Elette Boyle and Ran Cohen and Tal Malkin and Tal Moran},
      title = {Is Information-Theoretic Topology-Hiding Computation Possible?},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1094},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.