Paper 2018/486

Pushing the Communication Barrier in Secure Computation using Lookup Tables

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. NDSS 2017
Secure computationcompilerGMWlookup tablesmulti-input gatesimplementationefficiency
Contact author(s)
thomas schneider @ crisp-da de
2018-05-23: received
Short URL
Creative Commons Attribution


      author = {Ghada Dessouky and Farinaz Koushanfar and Ahmad-Reza Sadeghi and Thomas Schneider and Shaza Zeitouni and Michael Zohner},
      title = {Pushing the Communication Barrier in Secure Computation using Lookup Tables},
      howpublished = {Cryptology ePrint Archive, Paper 2018/486},
      year = {2018},
      doi = {10.14722/ndss.2017.23097},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.