Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Marshall Ball, Columbia University

Abstract

I will speak about some recent developments in topology-hiding communication (and computation). A topology-hiding broadcast protocol for class of networks, allows a party to send a message to every other party in the network, without revealing anything about the network beyond a party's local neighborhood. Such protocols are a central tool underlying general topology-hiding secure computation, protocols that allow parties to evaluate arbitrary functionalities, without revealing the topology, or anything about the input beyond the output of the functionality. In particular, I will focus on recent work studying how graph properties impact the feasibility of topology-hiding broadcast in the presence of a single honest-but-curious corruption. One intriguing corollary of these investigations is the following dichotomy for networks containing at least 3 nodes (and 1 honest-but-curious corruption): - If all networks in the class are 2-connected, then statistically-secure topology-hiding computation is possible. - Otherwise, key agreement is necessary and sufficient (for security against probabilistic polynomial time adversaries). This talk is based on joint work with Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, and Tal Moran.

The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home