Paper 2017/189
Authenticated Garbling and Efficient Maliciously Secure Multi-Party Computation
Jonathan Katz and Samuel Ranellucci and Xiao Wang
Abstract
In this paper, we extend the recent work by Wang et al., who proposed a new framework for secure two-party computation in the preprocessing model that can be instantiated efficiently using TinyOT. We show that their protocol can be generalized to the multi-party setting, where the preprocessing functionality is based on the multi-party TinyOT-like protocol. Assuming there are $n$ parties where at most $n-1$ parties are corrupted, the function-dependent phase has a total communication complexity of $O(\kappa n^2)$ bits per AND gate; the online phase has a total communication complexity of $O(\kappa n^2)$ bits per input/output bit. In the second part of this paper, we propose a new multi-party TinyOT protocol. The new protocol uses a set of new techniques that allow parties to distributively check the correctness without the need for cut-and-choose. The resulting protocol is much more efficient compared to previous protocols: with statistical security parameter $\rho$, the complexity to generate one AND triple is $O(\frac{\rho}{\log |C|}n^2)$, where $|C|$ is the circuit size. The best previous multi-party TinyOT protocol by Frederiksen et al. has a complexity of $O(\frac{\rho^2}{\log^2|C|}n^2)$ per AND triple. The complexity is measured in terms of number of symmetric key operations/number of symmetric key messages. The resulting protocol enjoys extremely high efficiency, compared to the state-of-the-art protocol by Lindell et al. that combines the BMR protocol with the SPDZ protocol.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- multi-party computationsecure computationgarbled circuits
- Contact author(s)
- wangxiao @ cs umd edu
- History
- 2017-05-22: last of 4 revisions
- 2017-02-28: received
- See all versions
- Short URL
- https://ia.cr/2017/189
- License
-
CC BY