Paper 2015/371

Constant-Round MPC with Fairness and Guarantee of Output Delivery

S. Dov Gordon, Feng-Hao Liu, and Elaine Shi

Abstract

We study the round complexity of multiparty computation with fairness and guaranteed output delivery, assuming existence of an honest majority. We demonstrate a new lower bound and a matching upper bound. Our lower bound rules out any two-round fair protocols in the standalone model, even when the parties are given access to a common reference string (CRS). The lower bound follows by a reduction to the impossibility result of virtual black box obfuscation of arbitrary circuits. Then we demonstrate a three-round protocol with guarantee of output delivery, which in general is harder than achieving fairness (since the latter allows the adversary to force a fair abort). We develop a new construction of a threshold fully homomorphic encryption scheme, with a new property that we call ``flexible'' ciphertexts. Roughly, our threshold encryption scheme allows parties to adapt flexible ciphertexts to the public keys of the non-aborting parties, which provides a way of handling aborts without adding any communication.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
MPCThreshold FHELearning with error
Contact author(s)
fenghao @ cs umd edu
History
2015-04-23: received
Short URL
https://ia.cr/2015/371
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/371,
      author = {S.  Dov Gordon and Feng-Hao Liu and Elaine Shi},
      title = {Constant-Round MPC with Fairness and Guarantee of Output Delivery},
      howpublished = {Cryptology ePrint Archive, Paper 2015/371},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/371}},
      url = {https://eprint.iacr.org/2015/371}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.