You are looking at a specific version 20170317:003010 of this paper. See the latest version.

Paper 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.

Note: Fix a small bug in the TinyOT improvement

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
two-party computationsecure computation
Contact author(s)
wangxiao @ cs umd edu
History
2017-05-22: last of 5 revisions
2017-01-13: received
See all versions
Short URL
https://ia.cr/2017/030
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.