Cryptology ePrint Archive: Report 2017/030

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation

Xiao Wang and Samuel Ranellucci and Jonathan Katz

Abstract: We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authentication information for the two parties; this information is then used to construct a single ``authenticated'' garbled circuit which is then transmitted and evaluated.

We also show how to efficiently instantiate the preprocessing phase using our own optimized version of the TinyOT protocol. Our overall protocol outperforms existing work in both the single-execution and amortized settings, with or without preprocessing:

- In the single-execution setting, our protocol evaluates an AES circuit with malicious security in 37~ms total with an online time of just 1~ms. Previous work with the best online time (also 1~ms) requires 124~ms in total; previous work with the best total time requires 62~ms (with 14~ms online time).

- In the amortized setting where the time is amortized over 1024 executions, each AES computation runs in just 6.7~ms overall, with roughly the same online time as above. The best previous work in this setting requires roughly the same total time but does not support preprocessing independent of the function to be evaluated.

Our work shows that the performance penalty for maliciously secure two-party computation (vs.\ semi-honest security) is much smaller than previously believed.

As a by-product of our framework, we also obtain the first constant-round maliciously-secure two-party computation with $O(|C|\kappa)$ bits of communication, by instantiating the preprocessing using the IPS compiler under the $\Phi$-hiding assumption. This protocol achieves a constant communication overhead compared to Yao's semi-honest protocol.

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

Date: received 10 Jan 2017, last revised 16 Mar 2017

Contact author: wangxiao at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Fix a small bug in the TinyOT improvement

Version: 20170317:003010 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]