Cryptology ePrint Archive: Report 2015/371
Constant-Round MPC with Fairness and Guarantee of Output Delivery
S. Dov Gordon and 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.
Category / Keywords: MPC, Threshold FHE, Learning with error
Date: received 22 Apr 2015
Contact author: fenghao at cs umd edu
Available format(s): PDF | BibTeX Citation
Version: 20150423:131710 (All versions of this report)
Short URL: ia.cr/2015/371
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]