Faster secure multiplication of matrices and integers, even against cheating adversaries

What is it about?

Garbled circuits let two parties who do not trust each other compute a function of their private inputs, while revealing nothing beyond the output. The fastest protocols are designed for parties who follow the rules. However, if one party cheats, they can make the other compute a wrong answer without noticing. Authenticated garbling is the leading way to stop this, and it costs about as much as the honest-party protocols. However, it handles computation one small AND gate at a time. Operations like matrix and integer multiplication break into a huge number of these gates. For parties who follow the rules, a technique called one-hot garbling already handles these operations as a single larger gate, at much lower cost. We show how to bring that improvement to the setting where either party may cheat. We give two protocols. The first makes the garbled circuit as small as in the honest-party setting. The second makes total communication as low as possible.

Featured Image

Photo by franco alva on Unsplash

Photo by franco alva on Unsplash

Why is it important?

Multiplication is at the core of many computations people want to run on private data, including machine learning inference, where matrix multiplication dominates. Until now, protecting against a cheating party meant giving up the savings that one-hot garbling offers in the honest-party setting. Our protocols fill this gap, providing the best of both worlds. For a 256 by 256 bit tensor product, we see a 5.8x improvement in communication and a 2.9 to 4.0x improvement in wall clock time over the previous state of the art. Since authenticated garbling is not a black-box compiler, this kind of upgrade has to be built by hand for each new semi-honest technique.

Perspectives