Paper 2017/1006

Round and Communication Efficient Unconditionally-secure MPC with $t < n/3$ in Partially Synchronous Network

Ashish Choudhury, Arpita Patra, and Divya Ravi

Abstract

In this work, we study unconditionally-secure multi-party computation (MPC) tolerating $t < n/3$ corruptions, where $n$ is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with $t<n/3$ requires a communication of $O(n^5)$ field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires $O(n^2)$ communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. ICITS 2017
Keywords
Verifiable Secret SharingPartial SynchronousMulti-party computationstatistical security
Contact author(s)
divya 18oct @ gmail com
History
2017-10-16: last of 2 revisions
2017-10-13: received
See all versions
Short URL
https://ia.cr/2017/1006
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1006,
      author = {Ashish Choudhury and Arpita Patra and Divya Ravi},
      title = {Round and Communication Efficient Unconditionally-secure MPC with $t < n/3$ in Partially Synchronous Network},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1006},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1006}},
      url = {https://eprint.iacr.org/2017/1006}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.