Constructing Secure Multi-Party Computation with Identifiable Abort

Nicholas Brandt; Sven Maier; Tobias Müller; Jörn Müller-Quade

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

Abstract

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 https://eprint.iacr.org/2021/684, subsuming and unifying both papers.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. Financial Cryptography and Data Security 2023
DOI: 10.1007/978-3-031-47754-6_8
Keywords: Multi-Party Computation Identifiable Abort Universal Composability
Contact author(s): nicholas brandt @ inf ethz ch
History: 2023-12-04: last of 7 revisions; 2020-02-13: received; See all versions
Short URL: https://ia.cr/2020/153
License: CC BY

BibTeX

@misc{cryptoeprint:2020/153,
      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},
      url = {https://eprint.iacr.org/2020/153}
}