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

David Heath, Vladimir Kolesnikov, Stanislav Peceny

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

Abstract

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.4×. Total wall-clock time is improved by 4.1 - 9.2 × depending on network settings. Our work is in the semi-honest model, tolerating all-but-one corruptions.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
EditorsShiho Moriai, Huaxiong Wang
PublisherSpringer
Pages3-30
Number of pages28
ISBN (Print)9783030648398
DOIs
StatePublished - 2020
Externally publishedYes
Event26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, Korea, Republic of
Duration: Dec 7 2020Dec 11 2020

Publication series

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

Conference

Conference26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
Country/TerritoryKorea, Republic of
CityDaejeon
Period12/7/2012/11/20

Keywords

  • Conditional branching
  • GMW
  • MPC

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'MOTIF: (Almost) Free Branching in GMW: Via Vector-Scalar Multiplication'. Together they form a unique fingerprint.

Cite this