Welcome to the resource topic for 2021/604
Title:
Masked Triples: Amortizing Multiplication Triples across Conditionals
Authors: David Heath, Vladimir Kolesnikov, 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.
ePrint: https://eprint.iacr.org/2021/604
Talk: https://www.youtube.com/watch?v=mZm2tMas-yc
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .