Cryptology ePrint Archive: Report 2018/208

Efficient MPC from Syndrome Decoding (or: Honey, I Shrunk the Keys)

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

Date: received 21 Feb 2018

Contact author: peter scholl at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20180222:161349 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]