Paper 2018/208

TinyKeys: A New Approach to Efficient Multi-Party Computation

Carmit Hazay, Emmanuela Orsini, 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 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.

Note: Minor revision

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Keywords
Secure Multi-Party ComputationOblivious TransferSyndrome DecodingLarge Scale
Contact author(s)
carmit hazay @ biu ac il
emmanuela orsini @ kuleuven be
peter scholl @ cs au dk
eduardo @ cs au dk
History
2022-02-21: last of 6 revisions
2018-02-22: received
See all versions
Short URL
https://ia.cr/2018/208
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/208,
      author = {Carmit Hazay and Emmanuela Orsini and Peter Scholl and Eduardo Soria-Vazquez},
      title = {TinyKeys: A New Approach to Efficient Multi-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/208},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/208}},
      url = {https://eprint.iacr.org/2018/208}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.