Paper 2023/330

Perfect MPC over Layered Graphs

Bernardo David, IT University of Copenhagen
Yuval Ishai, Technion – Israel Institute of Technology
Anders Konring, IT University of Copenhagen
Eyal Kushilevitz, Technion – Israel Institute of Technology
Varun Narayanan, Technion – Israel Institute of Technology

The classical "BGW protocol" (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among $n$ parties can be realized with perfect full security if $t < n/3$ parties are corrupted. This holds against malicious adversaries in the "standard" model for MPC, where a fixed set of $n$ parties is involved in the full execution of the protocol. However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the adversary may periodically "move" by uncorrupting parties and corrupting a new set of $t$ parties. In this setting, it is unclear if full security can be achieved against an adversary that is maximally mobile, i.e., moves after every round. The question is further motivated by the "You Only Speak Once" (YOSO) setting of Gentry et al. (Crypto 2021), where not only the adversary is mobile but also each round is executed by a disjoint set of parties. Previous positive results in this model do not achieve perfect security, and either assume probabilistic corruption and a nonstandard communication model, or only realize the weaker goal of security-with-abort. The question of matching the BGW result in these settings remained open. In this work, we tackle the above two challenges simultaneously. We consider a layered MPC model, a simplified variant of the fluid MPC model of Choudhuri et al. (Crypto 2021). Layered MPC is an instance of standard MPC where the interaction pattern is defined by a layered graph of width $n$, allowing each party to send secret messages and broadcast messages only to parties in the next layer. We require perfect security against a malicious adversary who may corrupt at most $t$ parties in each layer. Our main result is a perfect, fully secure layered MPC protocol with an optimal corruption threshold of $t < n/3$, thus extending the BGW feasibility result to the layered setting. This implies perfectly secure MPC protocols against a maximally mobile adversary.

Available format(s)
Cryptographic protocols
Publication info
Layered NetworkMultiparty ComputationProactive SecurityStateless PartiesYOSO
Contact author(s)
beda @ itu dk
yuvali @ cs technion ac il
anders konring @ gmail com
eyal kushilevitz @ gmail com
varunnkv @ gmail com
2023-09-03: revised
2023-03-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bernardo David and Yuval Ishai and Anders Konring and Eyal Kushilevitz and Varun Narayanan},
      title = {Perfect {MPC} over Layered Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/330},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.