Paper 2021/151

On Sufficient Oracles for Secure Computation with Identifiable Abort

Mark Simkin, Luisa Siniscalchi, and Sophia Yakoubov


Identifiable abort is the strongest security guarantee that is achievable for secure multi-party computation in the dishonest majority setting. Protocols that achieve this level of security ensure that, in case of an abort, all honest parties agree on the identity of at least one corrupt party who can be held accountable for the abort. It is important to understand what computational primitives must be used to obtain secure computation with identifiable abort. This can be approached by asking which oracles can be used to build perfectly secure computation with identifiable abort. Ishai, Ostrovsky, and Zikas (Crypto 2014) show that an oracle that returns correlated randomness to all $n$ parties is sufficient; however, they leave open the question of whether oracles that return output to fewer than $n$ parties can be used. In this work, we show that for $t \leq n - 2$ corruptions, oracles that return output to $n - 1$ parties are sufficient to obtain information-theoretically secure computation with identifiable abort. Using our construction recursively, we see that for $t \leq n - \ell - 2$ and $\ell \in \mathcal{O}(1)$, oracles that return output to $n - \ell - 1$ parties are sufficient. For our construction, we introduce a new kind of secret sharing scheme which we call unanimously identifiable secret sharing with public and private shares (UISSwPPS). In a UISSwPPS scheme, each share holder is given a public and a private shares. Only the public shares are necessary for reconstruction, and the knowledge of a private share additionally enables the identification of at least one party who provided an incorrect share in case reconstruction fails. The important new property of UISSwPPS is that, even given all the public shares, an adversary should not be able to come up with a different public share that causes reconstruction of an incorrect message, or that avoids the identification of a cheater if reconstruction fails.

Available format(s)
Cryptographic protocols
Publication info
Secure ComputationIdentifiable Abort
Contact author(s)
simkin @ cs au dk
sophia yakoubov @ gmail com
lsiniscalchi @ cs au dk
2021-06-11: last of 4 revisions
2021-02-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mark Simkin and Luisa Siniscalchi and Sophia Yakoubov},
      title = {On Sufficient Oracles for Secure Computation with Identifiable Abort},
      howpublished = {Cryptology ePrint Archive, Paper 2021/151},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.