Topology-Hiding Computation

Topology-Hiding Computation

Status

The project started in 2016 and has been successfully completed.

Researchers

Martin Hirt (ETH Zurich)
Rio Lavigne (MIT)
Ueli Maurer (ETH Zurich)
Tal Moran (IDC Herzliya)
Marta Mularczyk (ETH Zurich)
Daniel Tschudi (Aarhus University)
Vassilis Zikas (University of Edinburgh)

Description

Secure communication over an insecure network is one of the fundamental goals of cryptography. The security goal can be to hide different aspects of the communication, ranging from the content (secrecy), the participants’ identity (anonymity), the existence of communication (steganography), to hiding the topology of the underlying network in case it is not complete.

Incomplete networks arise in many contexts, such as social networks, the Internet of Things (IoT) or ad-hoc vehicular networks. Hiding the topology can, for example, be important because the position of a node within the network depends on the node’s location. This could in turn leak information about the node’s identity or other confidential parameters.

Incomplete networks have been studied in the context of communication security, referred to as secure message transmission, where the goal is to enable communication between any pair of entities, despite an incomplete communication graph. Also, anonymous communication has been studied extensively. Unfortunately, none of these approaches can be used to hide the network topology. In fact, secure message transmission protocols assume (for their execution) that the network graph is public knowledge.

The goal of this project is to design topology-hiding communication protocols, which allow a set of parties connected by an incomplete network with unknown communication graph, where each party only knows its neighbors, to communicate in such a way that the network topology remains hidden even from a powerful adversary who can corrupt parties. These communication protocols can then be used to perform arbitrary tasks, for example secure multi-party computation, in a topology-hiding manner. In the formal analysis, we consider different degrees of network hiding. For example, a network may be completely hidden, or some partial knowledge about it may leak to the adversary. Recent results show that we can hide the topology up to leaking 1 bit of information about it with probability p.

Publications

Network-Hiding Communication and Applications to Multi-Party Protocols
Martin Hirt, Ueli Maurer, Daniel Tschudi, and Vassilis Zikas
Advances in Cryptology – CRYPTO 2016, Security and Cryptology, Springer-Verlag Berlin Heidelberg, vol. 9814,
pp. 335-365, Aug 2016.

Topology-Hiding Computation Beyond Semi-Honest Adversaries
Rio Lavigne and Chen-Da Liu-Zhang and Ueli Maurer and Tal Moran and Marta Mularczyk and Daniel Tschudi
Theory of Cryptography Conference, TCC 2018, pp. 3-35, Springer, 2018.

Topology-Hiding Computation for Networks with Unknown Delays
Rio LaVigne, Chen-Da Liu Zhang, Ueli Maurer, Tal Moran, Marta Mularczyk, and Daniel Tschudi
Public-Key Cryptography — PKC 2020, LNCS, Springer, vol. 12111, pp. 215–245, Apr 2020.