Silas Richelson: "Topology Hiding Computation"

Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography, allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the output of the function.
Over the past two decades, the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model, underlying assumptions, complexity and composability of the resulting protocols.

One question that appears to have received very little attention, however, is that of MPC over an underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being of pure theoretic interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations, vehicle-to-vehicle networks and the "internet of things" are some of the examples.

In this talk we will describe the first results that consider the question of "topology-hiding computation" in the computational setting. As a first step, we will show how to formally define what we mean by "toplogy hiding". For these natural definitions, we can prove some strong impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.

Note that the talk will be self-contained—we will not assume any previous knowledge of cryptography.

Based on joint work with Tal Moran and Ilan Orlov