Paper 2023/849

Towards Topology-Hiding Computation from Oblivious Transfer

Marshall Ball, New York University
Alexander Bienstock, New York University
Lisa Kohl, Centrum Wiskunde & Informatica
Pierre Meyer, IRIF, Université Paris Cité, CNRS, Reichman University

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2023
secure multiparty computationtopology-hiding computationfoundations
Contact author(s)
marshall ball @ cs nyu edu
abienstock @ cs nyu edu
lisa kohl @ cwi nl
pierre meyer @ irif fr
2023-09-19: revised
2023-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marshall Ball and Alexander Bienstock and Lisa Kohl and Pierre Meyer},
      title = {Towards Topology-Hiding Computation from Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2023/849},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.