[Resource Topic] 2023/820: Network Agnostic MPC with Statistical Security

Welcome to the resource topic for 2023/820

Network Agnostic MPC with Statistical Security

Authors: Ananya Appan, Ashish Choudhury


We initiate the study of the network agnostic MPC protocols with statistical security. Network agnostic protocols give the best possible security guarantees irrespective of the underlying network type. We consider the general-adversary model, where the adversary is characterized by an adversary structure which enumerates all possible candidate subsets of corrupt parties. The \mathcal{Q}^{(k)} condition enforces that the union of no k subsets from the adversary structure covers the party set. Given an unconditionally-secure PKI setup, known statistically-secure synchronous MPC protocols are secure against adversary structures satisfying the \mathcal{Q}^{(2)} condition. Known statistically-secure asynchronous MPC protocols can tolerate \mathcal{Q}^{(3)} adversary structures. Fix a set of n parties \mathcal{P} = \{P_1, ... ,P_n\} and adversary structures \mathcal{Z}_s and \mathcal{Z}_a, satisfying the \mathcal{Q}^{(2)} and \mathcal{Q}^{(3)} conditions respectively, where \mathcal{Z}_a \subset \mathcal{Z}_s. Then, given an unconditionally-secure PKI, we ask whether it is possible to design a statistically-secure MPC protocol resilient against \mathcal{Z}_s and \mathcal{Z}_a in a synchronous and an asynchronous network respectively if the parties in \mathcal{P} are unaware of the network type. We show that it is possible iff \mathcal{Z}_s and \mathcal{Z}_a satisfy the \mathcal{Q}^{(2,1)} condition, meaning that the union of any two subsets from \mathcal{Z}_s and any one subset from \mathcal{Z}_a is a proper subset of \mathcal{P}. We design several important network agnostic building blocks with the \mathcal{Q}^{(2,1)} condition, such as Byzantine broadcast, Byzantine agreement, information checking protocol, verifiable secret-sharing and secure multiplication protocol, whose complexity is polynomial in n and |\mathcal{Z}_s|.

ePrint: https://eprint.iacr.org/2023/820

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .