Paper 2021/388

Topology-Hiding Communication from Minimal Assumptions.

Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, and Tal Moran


Topology-hiding broadcast (THB) enables parties communicating over an incomplete network to broadcast messages while hiding the topology from within a given class of graphs. THB is a central tool underlying general topology-hiding secure computation (THC) (Moran et al. TCC’15). Although broadcast is a privacy-free task, it was recently shown that THB for certain graph classes necessitates computational assumptions, even in the semi-honest setting, and even given a single corrupted party. In this work we investigate the minimal assumptions required for topology-hiding communication: both Broadcast or Anonymous Broadcast (where the broadcaster’s identity is hidden). We develop new techniques that yield a variety of necessary and sufficient conditions for the feasibility of THB/THAB in different cryptographic settings: information theoretic, given existence of key agreement, and given existence of oblivious transfer. Our results show that feasibility can depend on various properties of the graph class, such as connectivity, and highlight the role of different properties of topology when kept hidden, including direction, distance, and/or distance-of-neighbors to the broadcaster. An interesting corollary of our results is a dichotomy for THC with a public number of at least three parties, secure against one corruption: information-theoretic feasibility if all graphs are 2-connected; necessity and sufficiency of key agreement otherwise.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2020
secure multiparty computationtopology-hiding computationbroadcastfoundations
Contact author(s)
pierre meyer @ ens-lyon fr
2021-03-27: received
Short URL
Creative Commons Attribution


      author = {Marshall Ball and Elette Boyle and Ran Cohen and Lisa Kohl and Tal Malkin and Pierre Meyer and Tal Moran},
      title = {Topology-Hiding Communication from Minimal Assumptions.},
      howpublished = {Cryptology ePrint Archive, Paper 2021/388},
      year = {2021},
      doi = {10.1007/978-3-030-64378-2_17},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.