Paper 2020/153

Constructing Secure Multi-Party Computation with Identifiable Abort

Nicholas Brandt, ETH Zurich
Sven Maier, French National Centre for Scientific Research
Tobias Müller
Jörn Müller-Quade, Karlsruhe Institute of Technology

Composable protocols for Multi-Party Computation that provide security with Identifiable Abort against a dishonest majority require some form of setup, e.g. correlated randomness among the parties. While this is a very useful model, it has the downside that the setup's randomness must be programmable, otherwise security becomes provably impossible. Since programmability is more realistic for smaller setups (in terms of number of parties), it is crucial to minimize the correlation complexity (degree of correlation) of the setup's randomness. We give a tight tradeoff between the correlation complexity \(\beta\) and the corruption threshold \(t\). Our bounds are strong in that \(\beta\)-wise correlation is sufficient for statistical security while \(\beta-1\)-wise correlation is insufficient even for computational security. In particular, for strong security, i.e., \(t < n\), full \(n\)-wise correlation is necessary. However, for any constant fraction of honest parties, we provide a protocol with constant correlation complexity which tightens the gap between the theoretical model and the setup's implementation in the real world. In contrast, previous state-of-the-art protocols require full \(n\)-wise correlation regardless of \(t\).

Note: This is a merge of a previous version of this paper and, subsuming and unifying both papers.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Financial Cryptography and Data Security 2023
Multi-Party ComputationIdentifiable AbortUniversal Composability
Contact author(s)
nicholas brandt @ inf ethz ch
2023-12-04: last of 7 revisions
2020-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicholas Brandt and Sven Maier and Tobias Müller and Jörn Müller-Quade},
      title = {Constructing Secure Multi-Party Computation with Identifiable Abort},
      howpublished = {Cryptology ePrint Archive, Paper 2020/153},
      year = {2020},
      doi = {10.1007/978-3-031-47754-6_8},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.