International Association for Cryptologic Research

International Association
for Cryptologic Research


Towards Topology-Hiding Computation from Oblivious Transfer

Marshall Ball , New York University
Alexander Bienstock , New York University
Lisa Kohl , CWI
Pierre Meyer , Université Paris Cité, IRIF, CNRS and Reichman University
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: 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.
  title={Towards Topology-Hiding Computation from Oblivious Transfer},
  author={Marshall Ball and Alexander Bienstock and Lisa Kohl and Pierre Meyer},