On Fully-Secure Honest Majority MPC Without nRound Overhead

Daniel Escudero, Serge FehrLATINCRYPT 2023 · OpenReview

Abstract

Fully secure multiparty computation (or guaranteed output delivery) among n parties can be achieved with perfect security if the number of corruptions t is less than n/3, or with statistical security with the help of a broadcast channel if \(t<n/2\). In the case of \(t<n/3\), it is known that it is possible to achieve linear communication complexity, but at a cost of having a round count of \(\varOmega (\textsf{depth}(C) + n)\) in the worst case. The number of rounds can be reduced to \(O(\textsf{depth}(C))\) by either increasing communication, or assuming some correlated randomness (a setting also known as the preprocesing model). For \(t<n/2\) it is also known that linear communication complexity is achievable, but at the cost of \(\varOmega (\textsf{depth}(C) + n^2)\) rounds, due to the use of a technique called dispute control. However, in contrast to the \(t<n/3\) setting, it is not known how to reduce this round count for \(t<n/2\) to \(O(\textsf{depth}(C))\), neither allowing for larger communication, or by using correlated randomness.
BibTeX
@inproceedings{escudero2023fully,
  author = {Daniel Escudero and Serge Fehr},
  title = {{On Fully-Secure Honest Majority MPC Without nRound Overhead}},
  booktitle = {LATINCRYPT},
  year = {2023},
  url = {https://openreview.net/forum?id=HnojXhtYwV},
}

Loading related content...

Figure