Paper 2021/604

Masked Triples: Amortizing Multiplication Triples across Conditionals

David Heath, Vladimir Kolesnikov, and Stanislav Peceny

Abstract

A classic approach to MPC uses preprocessed multiplication triples to evaluate arbitrary Boolean circuits. If the target circuit features conditional branching, e.g. as the result of a IF program statement, then triples are wasted: one triple is consumed per AND gate, even if the output of the gate is entirely discarded by the circuit's conditional behavior. In this work, we show that multiplication triples can be re-used across conditional branches. For a circuit with $b$ branches, each having $n$ AND gates, we need only a total of $n$ triples, rather than the typically required $b\cdot n$. Because preprocessing triples is often the most expensive step in protocols that use them, this significantly improves performance. Prior work similarly amortized oblivious transfers across branches in the classic GMW protocol (Heath et al., Asiacrypt 2020, [HKP20]). In addition to demonstrating conditional improvements are possible for a different class of protocols, we also concretely improve over [HKP20]: their maximum improvement is bounded by the topology of the circuit. Our protocol yields improvement independent of topology: we need triples proportional to the size of the program's longest execution path, regardless of the structure of the program branches. We implemented our approach in C++. Our experiments show that we significantly improve over a naive protocol and over prior work: for a circuit with $16$ branches and in terms of total communication, we improved over naive by $12\times$ and over [HKP20] by an average of $2.6\times$. Our protocol is secure against the semi-honest corruption of $p-1$ parties.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in Pkc 2021
Keywords
MPCconditional branchingBeaver triples
Contact author(s)
heath davidanthony @ gatech edu
kolesnikov @ gatech edu
stan peceny @ gatech edu
History
2021-05-10: received
Short URL
https://ia.cr/2021/604
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/604,
      author = {David Heath and Vladimir Kolesnikov and Stanislav Peceny},
      title = {Masked Triples: Amortizing Multiplication Triples across Conditionals},
      howpublished = {Cryptology ePrint Archive, Paper 2021/604},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/604}},
      url = {https://eprint.iacr.org/2021/604}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.