Paper 2024/990

Perfectly-secure Network-agnostic MPC with Optimal Resiliency

Shravani Patil, Indian Institute of Science Bangalore
Arpita Patra, Indian Institute of Science Bangalore
Abstract

We study network-agnostic secure multiparty computation with perfect security. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous. The feasibility of perfectly-secure MPC in synchronous and asynchronous networks has been settled a long ago. The landmark work of [Ben-Or, Goldwasser, and Wigderson, STOC'88] shows that $n > 3t_s$ is necessary and sufficient for any MPC protocol with $n$-parties over synchronous network tolerating $t_s$ active corruptions. In yet another foundational work, [Ben-Or, Canetti, and Goldreich, STOC'93] show that the bound for asynchronous network is $n > 4t_a$, where $t_a$ denotes the number of active corruptions. However, the same question remains unresolved for network-agnostic setting till date. In this work, we resolve this long-standing question. We show that perfectly-secure network-agnostic $n$-party MPC tolerating $t_s$ active corruptions when the network is synchronous and $t_a$ active corruptions when the network is asynchronous is possible if and only if $n > 2 \max(t_s,t_a) + \max(2t_a,t_s)$. When $t_a \geq t_s$, our bound reduces to $n > 4t_a$, whose tightness follows from the known feasibility results for asynchronous MPC. When $t_s > t_a$, our result gives rise to a new bound of $n > 2t_s + \max(2t_a,t_s)$. Notably, the previous network-agnostic MPC in this setting [Appan, Chandramouli, and Choudhury, PODC'22] only shows sufficiency for a loose bound of $n > 3t_s + t_a$. When $t_s > 2t_a$, our result shows tightness of $ n > 3t_s$, whereas the existing work shows sufficiency for $n > 3t_s+t_a$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Network-agnostic MPCPerfect SecurityLower Bound
Contact author(s)
shravanip @ iisc ac in
arpita @ iisc ac in
History
2024-06-20: approved
2024-06-19: received
See all versions
Short URL
https://ia.cr/2024/990
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/990,
      author = {Shravani Patil and Arpita Patra},
      title = {Perfectly-secure Network-agnostic {MPC} with Optimal Resiliency},
      howpublished = {Cryptology ePrint Archive, Paper 2024/990},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/990}},
      url = {https://eprint.iacr.org/2024/990}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.