Cryptology ePrint Archive: Report 2018/208

TinyKeys: A New Approach to Efficient Multi-Party Computation

Carmit Hazay and Emmanuela Orsini and Peter Scholl and Eduardo Soria-Vazquez

Abstract: We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols \emph{does not depend on the number of honest parties}, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for $n-1$ corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties' keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption.

We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around $n=20$ parties with $h=6$ honest parties, and as these increase we obtain up to a 13 times reduction (for $n=400,h=120$) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.

Category / Keywords: cryptographic protocols / multi-party computation, oblivious transfer, syndrome decoding

Original Publication (with major differences): IACR-CRYPTO-2018

Date: received 21 Feb 2018, last revised 30 Aug 2018

Contact author: carmit hazay at biu ac il

Available format(s): PDF | BibTeX Citation

Note: Full version

Version: 20180830:125959 (All versions of this report)

Short URL: ia.cr/2018/208


[ Cryptology ePrint archive ]