Ever-larger amounts of a data are being collected for training machine-learning models (ML), yet in many areas (such as healthcare) maintaining privacy continues to be a primary concern. Secure multiparty computation (MPC) allows models to be constructed while preserving privacy by running ML on encrypted training data. Garbled circuits are one of the most practical techniques for constructing MPC and have been used, together with secret sharing, for privacy-preserving ML (Mohassel and Zhang, "SecureML". IEEE SSP 2017). However, due to high bandwidth usage, it still required more than an hour to train a simple MNIST model, even when running between two machines on the same LAN and even allowing significant precomputation. The communication complexity of garbled circuits has not improved since the 2015 "half-gates" technique (Zahur, Rosulek, and Evans, Eurocrypt 2015).
We describe a garbling scheme for boolean circuits in which XOR gates are free and AND gates require communication of 3/2 times the security parameter, a 25 percent improvement over the state of the art. The half-gates paper proved a communication lower bound of twice the security parameter per AND gate, in a model that captured all known garbling techniques at the time. We bypass this lower bound with a novel technique called slicing and dicing, which involves slicing the encrypted values (called wire labels) in half and operating separately on those halves. Ours is the first to bypass the lower bound on AND gates without requiring communication for XOR gates.