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 is necessary and sufficient for any MPC protocol with -parties over synchronous network tolerating active corruptions. In yet another foundational work, [Ben-Or, Canetti, and Goldreich, STOC'93] show that the bound for asynchronous network is , where 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 -party MPC tolerating active corruptions when the network is synchronous and active corruptions when the network is asynchronous is possible if and only if . When , our bound reduces to , whose tightness follows from the known feasibility results for asynchronous MPC. When , our result gives rise to a new bound of . Notably, the previous network-agnostic MPC in this setting [Appan, Chandramouli, and Choudhury, PODC'22] only shows sufficiency for a loose bound of . When , our result shows tightness of , whereas the existing work shows sufficiency for .

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},
      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.