Is Information-Theoretic Topology-Hiding Computation Possible?

Marshall Ball

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.
I will discuss recent work beginning to 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.

Results for standard THC definition:

New relaxed definition: Distributional-THC:

Based on joint work with Elette Boyle, Ran Cohen, Tal Malkin, and Tal Moran.