Minimizing Setup in Broadcast-Optimal Two Round MPC

Ivan Damgård; Divya Ravi; Luisa Siniscalchi; Sophia Yakoubov

doi:10.1007/978-3-031-30617-4_5

Minimizing Setup in Broadcast-Optimal Two Round MPC

Ivan Damgård, Divya Ravi, Luisa Siniscalchi^*, Sophia Yakoubov

^*Corresponding author for this work

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Abstract

In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each communication structure. In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority). Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round. We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2023 : 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II
Editors	Carmit Hazay, Martijn Stam
Number of pages	30
Place of publication	Cham
Publisher	Springer
Publication date	Apr 2023
Pages	129-158
ISBN (Print)	978-3-031-30616-7
ISBN (Electronic)	978-3-031-30617-4
DOIs	https://doi.org/10.1007/978-3-031-30617-4_5
Publication status	Published - Apr 2023
Event	42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 - Lyon, France Duration: 23 Apr 2023 → 27 Apr 2023

Conference

Conference	42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023
Country/Territory	France
City	Lyon
Period	23/04/2023 → 27/04/2023

Series	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14005
ISSN	0302-9743

Keywords

Minimal setup
Round complexity
Secure computation

Access to Document

10.1007/978-3-031-30617-4_5

Cite this

Damgård, I., Ravi, D., Siniscalchi, L., & Yakoubov, S. (2023). Minimizing Setup in Broadcast-Optimal Two Round MPC. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II (pp. 129-158). Springer. https://doi.org/10.1007/978-3-031-30617-4_5

Damgård, Ivan ; Ravi, Divya ; Siniscalchi, Luisa et al. / Minimizing Setup in Broadcast-Optimal Two Round MPC. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. editor / Carmit Hazay ; Martijn Stam. Cham : Springer, 2023. pp. 129-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14005).

@inproceedings{2f887cf530d14239be3e2f3b8680fc13,

title = "Minimizing Setup in Broadcast-Optimal Two Round MPC",

abstract = "In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damg{\aa}rd, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each communication structure. In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority). Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damg{\aa}rd et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round. We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.",

keywords = "Minimal setup, Round complexity, Secure computation",

author = "Ivan Damg{\aa}rd and Divya Ravi and Luisa Siniscalchi and Sophia Yakoubov",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

year = "2023",

month = apr,

doi = "10.1007/978-3-031-30617-4_5",

language = "English",

isbn = "978-3-031-30616-7",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "129--158",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology – EUROCRYPT 2023",

address = "Netherlands",

}

Damgård, I, Ravi, D, Siniscalchi, L & Yakoubov, S 2023, Minimizing Setup in Broadcast-Optimal Two Round MPC. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. Springer, Cham, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14005, pp. 129-158, 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023, Lyon, France, 23/04/2023. https://doi.org/10.1007/978-3-031-30617-4_5

Minimizing Setup in Broadcast-Optimal Two Round MPC. / Damgård, Ivan; Ravi, Divya; Siniscalchi, Luisa et al.
Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. ed. / Carmit Hazay; Martijn Stam. Cham: Springer, 2023. p. 129-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14005).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Minimizing Setup in Broadcast-Optimal Two Round MPC

AU - Damgård, Ivan

AU - Ravi, Divya

AU - Siniscalchi, Luisa

AU - Yakoubov, Sophia

PY - 2023/4

Y1 - 2023/4

N2 - In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each communication structure. In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority). Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round. We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.

AB - In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each communication structure. In this work, we introduce a new security notion, namely, selective identifiable abort, which guarantees that every honest party either obtains the output, or aborts identifying one corrupt party (where honest parties may potentially identify different corrupted parties). We investigate what broadcast patterns in two-round MPC allow achieving this guarantee across various settings (such as with or without PKI, with or without an honest majority). Further, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two-thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round. We use fundamentally different techniques from the previous works to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one.

KW - Minimal setup

KW - Round complexity

KW - Secure computation

U2 - 10.1007/978-3-031-30617-4_5

DO - 10.1007/978-3-031-30617-4_5

M3 - Article in proceedings

AN - SCOPUS:85161713455

SN - 978-3-031-30616-7

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 158

BT - Advances in Cryptology – EUROCRYPT 2023

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer

CY - Cham

T2 - 42nd Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023

Y2 - 23 April 2023 through 27 April 2023

ER -

Damgård I, Ravi D, Siniscalchi L, Yakoubov S. Minimizing Setup in Broadcast-Optimal Two Round MPC. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. Cham: Springer. 2023. p. 129-158. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 14005). doi: 10.1007/978-3-031-30617-4_5