Cryptology ePrint Archive: Report 2018/578

Optimizing Authenticated Garbling for Faster Secure Two-Party Computation

Jonathan Katz and Samuel Ranellucci and Mike Rosulek and Xiao Wang

Abstract: Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the- art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically:

- We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6x improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation.

- We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5x improvement in the communication and a 2x improvement in the computation for that step.

Category / Keywords: cryptographic protocols / secure two-party computation, malicious security

Original Publication (in the same form): IACR-CRYPTO-2018

Date: received 5 Jun 2018, last revised 10 Oct 2018

Contact author: wangxiao at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Add a note that version 1 requires a higher roundtrip complexity.

Version: 20181011:005124 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]