Authenticated Garbling and Efficient Maliciously Secure Multi Party Computation
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(kn) bits per AND gate; the online phase has a total communication complexity of O(kn) 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 r, the complexity to generate one AND triple is O( r log |C|n where |C| is the circuit size. The best previous multi party TinyOT protocol by Frederiksen et al. has a complexity of O( r 2 log2 |C|n 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.
IACR Cryptol. ePrint Arch.