+ and × is all you need

Created on March 01, 2021

2021   ·   mpc   machine-learning   ·   research

Secure computation for machine learning usually juggles two kinds of secret sharing. The linear parts of a network — convolutions, matrix multiplies — are cheap and natural in arithmetic sharing. The non-linear parts — ReLU, maxpool, division — don’t fit there, so the textbook move is to convert to Boolean sharing, compute them, and convert back.

That conversion is the expensive part. Each interconversion — the bit-extraction / bit-decomposition that bridges the two representations — costs \(O(\text{bit-length})\) and a stack of protocol machinery, paid on every non-linear operation.

F : Convolutions Matrix Multiplication Linear Operations Arithmetic Secret Sharing F : ReLU, Maxpool Derivatives (ReLU, Maxpool) Division Boolean Secret Sharing Interconversion protocols (Bit Extraction / Decomposition) O(Bit-length)
SecureNN deletes the costly arithmetic ↔ Boolean bridge — it does the non-linear functions in arithmetic sharing directly.

SecureNN’s move is to delete that bridge. It computes the non-linear functions without ever leaving arithmetic sharing — using nothing but additions and multiplications. No Boolean conversion, no bit-decomposition round-trip, no garbled circuits.

In software engineering, simplicity is an underappreciated goal. Those interconversion protocols are exactly the kind of moving part that makes a system hard to build, test, and trust. By staying in one representation with the two simplest operations there are, the SecureNN approach is genuinely easy to implement — and that simplicity is precisely what makes it efficient.

Pushed to its logical extreme, the same line of thinking yields a maliciously secure comparison that is remarkably efficient — the Rabbit protocol.

PDF Code SecureNN · PETS 2019 · extended in Rabbit (FC 2021)