Cryptology ePrint Archive: Report 2018/486

Pushing the Communication Barrier in Secure Computation using Lookup Tables

Ghada Dessouky and Farinaz Koushanfar and Ahmad-Reza Sadeghi and Thomas Schneider and Shaza Zeitouni and Michael Zohner

Abstract: Secure two-party computation has witnessed significant efficiency improvements in the recent years. Current implementations of protocols with security against passive adversaries generate and process data much faster than it can be sent over the network, even with a single thread. This paper introduces novel methods to further reduce the communication bottleneck and round complexity of semi-honest secure two-party computation. Our new methodology creates a trade-off between communication and computation, and we show that the added computing cost for each party is still feasible and practicable in light of the new communication savings. We first improve communication for Boolean circuits with 2-input gates by factor 1.9x when evaluated with the protocol of Goldreich-Micali-Wigderson (GMW). As a further step, we change the conventional Boolean circuit representation from 2-input gates to multi-input/multi-output lookup tables (LUTs) which can be programmed to realize arbitrary functions. We construct two protocols for evaluating LUTs offering a trade-off between online communication and total communication. Our most efficient LUT-based protocol reduces the communication and round complexity by a factor 2-4x for several basic and complex operations. Our proposed scheme results in a significant overall runtime decrease of up to a factor of 3x on several benchmark functions.

Category / Keywords: cryptographic protocols / Secure computation; compiler; GMW; lookup tables; multi-input gates; implementation; efficiency

Original Publication (with minor differences): NDSS 2017

Date: received 22 May 2018

Contact author: thomas schneider at crisp-da de

Available format(s): PDF | BibTeX Citation

Version: 20180523:025258 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]