Perfectly-Secure Synchronous MPC With Asynchronous Fallback Guarantees
- 1 August 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 69 (8) , 5386-5425
Abstract
Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of n mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security (also called unconditional security ) provides the strongest security guarantees and remains secure even against computationally unbounded adversaries. Perfectly-secure MPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in an error-free fashion. The focus of this work is perfectly-secure MPC. Known protocols are designed assuming either a synchronous or asynchronous communication network. It is well known that perfectly-secure synchronous MPC is possible as long as the adversary can corrupt any ts < n /3 parties. On the other hand, perfectly-secure asynchronous MPC protocols can tolerate up to ta < n /4 corrupt parties. A natural question is does there exist a single MPC protocol for the setting where the parties are not aware of the exact network type and which can tolerate up to ts < n /3 corruptions in a synchronous network and up to ta < n /4 corruptions in an asynchronous network. We design such a best-of-both-worlds perfectly-secure MPC protocol, provided 3 ts + ta < n holds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worlds Byzantine agreement (BA) protocol tolerating t < n /3 corruptions which remains secure both in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds verifiable secret-sharing (VSS) protocol, which can tolerate up to ts and ta corruptions in a synchronous and in an asynchronous network respectively.Keywords
Funding Information
- Ministry of Electronics and Information technology
- Center for Internet of Ethical Things (CIET) project
- Department of Electronics Information Technology Biotechnology (ITBT), Government of Karnataka
This publication has 52 references indexed in Scilit:
- Efficient Asynchronous Verifiable Secret Sharing and Multiparty ComputationJournal of Cryptology, 2013
- Improving the round complexity of VSS in point-to-point networksInformation and Computation, 2009
- Perfectly-Secure MPC with Linear Communication Complexity2008
- Security and Composition of Multiparty Cryptographic ProtocolsJournal of Cryptology, 2000
- An Optimal Probabilistic Protocol for Synchronous Byzantine AgreementSIAM Journal on Computing, 1997
- Perfectly secure message transmissionJournal of the ACM, 1993
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- On sharing secrets and Reed-Solomon codesCommunications of the ACM, 1981
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980
- How to share a secretCommunications of the ACM, 1979