Towards Topology-Hiding Computation from Oblivious Transfer

Marshall Ball, Alexander Bienstock, Lisa Kohl, Pierre Meyer

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


Topology-Hiding Computation (THC) enables parties to securely compute a function on an incomplete network without revealing the network topology. It is known that secure computation on a complete network can be based on oblivious transfer (OT), even if a majority of the participating parties are corrupt. In contrast, THC in the dishonest majority setting is only known from assumptions that imply (additively) homomorphic encryption, such as Quadratic Residuosity, Decisional Diffie-Hellman, or Learning With Errors. In this work we move towards closing the gap between MPC and THC by presenting a protocol for THC on general graphs secure against all-but-one semi-honest corruptions from constant-round constant-overhead secure two-party computation. Our protocol is therefore the first to achieve THC on arbitrary networks without relying on assumptions with rich algebraic structure. As a technical tool, we introduce the notion of locally simulatable MPC, which we believe to be of independent interest.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
EditorsGuy Rothblum, Hoeteck Wee
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages31
ISBN (Print)9783031486142
StatePublished - 2023
Event21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China
Duration: Nov 29 2023Dec 2 2023

Publication series

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


Conference21st International conference on Theory of Cryptography Conference, TCC 2023
Country/TerritoryTaiwan, Province of China

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Towards Topology-Hiding Computation from Oblivious Transfer'. Together they form a unique fingerprint.

Cite this