Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions

Michele Ciampi; Rafail Ostrovsky; Luisa Siniscalchi; Hendrik Waldner

doi:10.1007/978-3-031-91092-0_12

Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions

Michele Ciampi^*
, Rafail Ostrovsky
, Luisa Siniscalchi
, Hendrik Waldner

^*Corresponding author for this work

University of Edinburgh
University of California
Nethermind

Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-review

Abstract

A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals:
1. reduce the total number of rounds of communication (to four, which is optimal);
2. use only polynomial-time hardness assumptions, and
3. rely solely on cryptographic assumptions in a black-box manner.
This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.

Original language	English
Title of host publication	Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025
Volume	15605
Publisher	Springer
Publication date	2025
Pages	331-359
ISBN (Print)	978-3-031-91091-3
ISBN (Electronic)	978-3-031-91092-0
DOIs	https://doi.org/10.1007/978-3-031-91092-0_12
Publication status	Published - 2025
Event	The 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Madrid, Spain Duration: 4 May 2025 → 8 May 2025

Conference

Conference	The 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Country/Territory	Spain
City	Madrid
Period	04/05/2025 → 08/05/2025

Access to Document

10.1007/978-3-031-91092-0_12

OpenUrl availability

Check availability in DTU Findit

Cite this

@inbook{37d5e200304b478fa36b1430af8b2d7e,

title = "Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions",

abstract = "A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals: 1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner. This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.",

author = "Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Hendrik Waldner",

year = "2025",

doi = "10.1007/978-3-031-91092-0\_12",

language = "English",

isbn = "978-3-031-91091-3",

volume = "15605",

pages = "331--359",

booktitle = "Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025",

publisher = "Springer",

note = "The 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt ; Conference date: 04-05-2025 Through 08-05-2025",

}

Ciampi, M, Ostrovsky, R, Siniscalchi, L & Waldner, H 2025, Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions. in Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 . vol. 15605, Springer, pp. 331-359, The 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, 04/05/2025. https://doi.org/10.1007/978-3-031-91092-0_12

Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions. / Ciampi, Michele; Ostrovsky, Rafail; Siniscalchi, Luisa et al.
Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025 . Vol. 15605 Springer, 2025. p. 331-359.

Research output: Chapter in Book/Report/Conference proceeding › Book chapter › Research › peer-review

TY - CHAP

T1 - Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions

AU - Ciampi, Michele

AU - Ostrovsky, Rafail

AU - Siniscalchi, Luisa

AU - Waldner, Hendrik

PY - 2025

Y1 - 2025

N2 - A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals: 1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner. This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.

AB - A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals: 1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner. This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.

U2 - 10.1007/978-3-031-91092-0_12

DO - 10.1007/978-3-031-91092-0_12

M3 - Book chapter

SN - 978-3-031-91091-3

VL - 15605

SP - 331

EP - 359

BT - Proceedings of the 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2025

PB - Springer

T2 - The 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques

Y2 - 4 May 2025 through 8 May 2025

ER -

Round-Optimal Black-Box Multiparty Computation from Polynomial-Time Assumptions

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this