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)
- 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
-
CC BY