On Sufficient Oracles for Secure Computation with Identifiable Abort

Mark Simkin, Luisa Siniscalchi, Sophia Yakoubov

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Abstract

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≤ 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≤ n- ℓ- 2 and ℓ∈ O(1 ), oracles that return output to n- ℓ- 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 share. 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.

Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks - 13th International Conference, SCN 2022, Proceedings
EditorsClemente Galdi, Stanislaw Jarecki
Number of pages22
Place of publicationCham
PublisherSpringer
Publication date2022
Pages494-515
ISBN (Print)978-3-031-14790-6
ISBN (Electronic)978-3-031-14791-3
DOIs
Publication statusPublished - 2022
Event13th Conference on Security and Cryptography For Networks - Almafi, Italy
Duration: 12 Sept 202214 Sept 2022
https://scn.unisa.it/scn22/

Conference

Conference13th Conference on Security and Cryptography For Networks
Country/TerritoryItaly
CityAlmafi
Period12/09/202214/09/2022
Internet address
SeriesLecture Notes in Computer Science
Volume13409
ISSN0302-9743

Keywords

  • identifiable abort
  • secure computation

Fingerprint

Dive into the research topics of 'On Sufficient Oracles for Secure Computation with Identifiable Abort'. Together they form a unique fingerprint.

Cite this