Author(s): Jesper Buus Nielsen, Thomas Schneider, Roberto Trifiletti

Download: Paper (PDF)

Date: 27 Feb 2017

Document Type: Reports

Additional Documents: Slides Video

Associated Event: NDSS Symposium 2017


Asymptotically more efficient than on the circuit level. Since then the LEGO approach has been improved upon in several theoretical works, but never implemented. In this paper we describe further concrete improvements and provide the first implementation of a protocol from the LEGO family. Our protocol has a constant number of rounds and is optimized for the offline/online setting with function-independent preprocessing. We have benchmarked our prototype and find that our protocol can compete with all existing implementations and that it is often more efficient. As an example, in a LAN setting we can evaluate an AES-128 circuit with online latency down to 1:13ms, while if evaluating 128 AES-128 circuits in parallel the amortized cost is 0:09ms per AES-128. This online performance does not come at the price of offline inefficiency as we achieve comparable performance to previous, less general protocols, and significantly better if we ignore the cost of the function-independent preprocessing. Also, as our protocol has an optimal 2-round online phase it is significantly more efficient than previous protocols when considering a high latency network.