Exploring the boundaries of topology-hiding computation

Marshall Ball, Elette Boyle, Tal Malkin, Tal Moran

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. In a line of recent works [Moran, Orlov & Richelson TCC’15, Hirt et al. CRYPTO’16, Akavia & Moran EUROCRYPT’17, Akavia et al. CRYPTO’17], THC protocols for securely computing any function in the semi-honest setting have been constructed. In addition, it was shown by Moran et al. that in the fail-stop setting THC with negligible leakage on the topology is impossible. In this paper, we further explore the feasibility boundaries of THC. We show that even against semi-honest adversaries, topology-hiding broadcast on a small (4-node) graph implies oblivious transfer; in contrast, trivial broadcast protocols exist unconditionally if topology can be revealed.We strengthen the lower bound of Moran et al. identifying and extending a relation between the amount of leakage on the underlying graph topology that must be revealed in the fail-stop setting, as a function of the number of parties and communication round complexity: Any n-party protocol leaking bits for must have rounds. We then present THC protocols providing close-to-optimal leakage rates, for unrestricted graphs on n nodes against a fail-stop adversary controlling a dishonest majority of the n players. These constitute the first general fail-stop THC protocols. Specifically, for this setting we show: A THC protocol that leaks at most one bit and requires rounds.A THC protocol that leaks at most bits for arbitrarily small non-negligible, and requires rounds. These protocols also achieve full security (with no leakage) for the semi-honest setting. Our protocols are based on one-way functions and a (stateless) secure hardware box primitive. This provides a theoretical feasibility result, a heuristic solution in the plain model using general-purpose obfuscation candidates, and a potentially practical approach to THC via commodity hardware such as Intel SGX. Interestingly, even with such hardware, proving security requires sophisticated simulation techniques.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
EditorsJesper Buus Nielsen, Vincent Rijmen
PublisherSpringer Verlag
Number of pages32
ISBN (Print)9783319783710
StatePublished - 2018
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018 - Tel Aviv, Israel
Duration: Apr 29 2018May 3 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10822 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
CityTel Aviv

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Exploring the boundaries of topology-hiding computation'. Together they form a unique fingerprint.

Cite this