Abstract
The purpose of this result is to simplify and improve secure computation protocols.
Firstly, we simplify the framework of garbling schemes, specifically linear garbling schemes, by reducing simulation-based security to an easy-to-check algebraic property in the random oracle model; we explain how this property tightly connects linear garbling with linear secret sharing. We then provide a new garbling scheme in this framework, improving both on the communication complexity and on the parallelizability of the calls to the random oracle, com- pared to previous state of the art. Our approach takes advantage of partitioning the circuit into “units” that may be functionally more complex than single binary gates. This approach allows us to circumvent the known lower bound on the communication complexity of gate- by-gate linear garbling proved by Zahur, Rosulek, and Evans. Moreover, each specific choice of the partition of the circuit in units gives a specific tradeoff between parallel calls to the random oracle and communication complexity (for example, partitioning the whole circuit into a single unit allows static calls to the random oracle, while smaller units may result in lower communication complexity, depending on the circuit). Each unit is garbled at once, by using a standard polynomial decomposition technique for each unit’s associated function. We also extend this scheme to natively work over arbitrary finite fields, and show that for small fields our approach is more efficient than translating the circuit into boolean and using boolean garbling techniques.
Secondly, we use the same polynomial decomposition technique in a similar fashion to improve the communication complexity of secure computation protocols in the pre-processing model, by extending the notion of Beaver/multiplicative triples to tuples whose algebraic relations may be more complex.
Joint work with Tal Malkin and Abhi Shelat.