Paper 2020/1175

MOTIF: (Almost) Free Branching in GMW via Vector-Scalar Multiplication

David Heath, Vladimir Kolesnikov, and Stanislav Peceny


MPC functionalities are increasingly specified in high-level languages, where control-flow constructions such as conditional statements are extensively used. Today, concretely efficient MPC protocols are circuit-based and must evaluate all conditional branches at high cost to hide the taken branch. The Goldreich-Micali-Wigderson, or GMW, protocol is a foundational circuit-based technique that realizes MPC for p players and is secure against up to p - 1 semi-honest corruptions. While GMW requires communication rounds proportional to the computed circuit’s depth, it is effective in many natural settings. Our main contribution is MOTIF (Minimizing OTs for IFs), a novel GMW extension that evaluates conditional branches almost for free by amortizing Oblivious Transfers (OTs) across branches. That is, we simultaneously evaluate multiple independent AND gates, one gate from each mutually exclusive branch, by representing them as a single cheap vector-scalar multiplication (VS) gate. For 2PC with b branches, we simultaneously evaluate up to b AND gates using only two 1-out-of-2 OTs of b-bit secrets. This is a factor ~b improvement over the state-of-the-art 2b 1-out-of-2 OTs of 1-bit secrets. Our factor b improvement generalizes to the multiparty setting as well: b AND gates consume only p(p - 1) 1-out-of-2 OTs of b-bit secrets. We implemented our approach and report its performance. For 2PC and a circuit with 16 branches, each comparing two length-65000 bitstrings, MOTIF outperforms standard GMW in terms of communication by ~9.4x. Total wall-clock time is improved by 4.1 - 9.2x depending on network settings. Our work is in the semi-honest model, tolerating all-but-one corruptions.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in ASIACRYPT 2020
MPCGMWconditional branching
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
stan peceny @ gatech edu
2020-09-25: received
Short URL
Creative Commons Attribution


      author = {David Heath and Vladimir Kolesnikov and Stanislav Peceny},
      title = {MOTIF: (Almost) Free Branching in GMW via Vector-Scalar Multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1175},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.