Abstract
The seminal work of Rabin and Ben-Or (STOC ’89) showed that the problem of secure n-party computation can be solved for \(t<n/2\) corruptions with guaranteed output delivery and statistical security. This holds in the traditional static model where the set of parties is fixed throughout the entire protocol execution.
The need to better capture the dynamics of large scale and long-lived computations, where compromised parties may recover and the set of parties can change over time, has sparked renewed interest in the proactive security model by Ostrovsky and Yung (PODC ’91). This abstraction, where the adversary may periodically uncorrupt and corrupt a new set of parties, is taken even a step further in the more recent YOSO and Fluid MPC models (CRYPTO ’21) which allow, in addition, disjoint sets of parties participating in each round. Previous solutions with guaranteed output delivery and statistical security only tolerate \(t<n/3\) corruptions, or assume a random corruption pattern plus non-standard communication models. Matching the Rabin and Ben-Or bound in these settings remains an open problem.
In this work, we settle this question considering the unifying Layered MPC abstraction recently introduced by David et al. (CRYPTO ’23). In this model, the interaction pattern is defined by a layered acyclic graph, where each party sends secret messages and broadcast messages only to parties in the very next layer. We complete the feasibility landscape of layered MPC, by extending the Rabin and Ben-Or result to this setting. Our results imply maximally-proactive MPC with statistical security in the honest-majority setting.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We are faced with a dichotomy of languages: a VSS protocol can be thought of as a strong distributed commitment. From this perspective, the party providing input is a committer, producing commitments that can be opened. More often, the language of secret sharing is used. Here, the party providing input is a dealer, producing sharings that can be reconstructed. We oscillate between these two abstractions.
- 2.
For simplicity, we consider the notion of “non-retroactive” (see [8], Definition 3) adaptive adversaries, who chooses at each round r a set of up to t parties from layer \(\mathcal {L}_{r}\) to corrupt. Since our protocols are information-theoretic, we conjecture that they are also secure against the stronger notion of retroactive-adaptive adversaries that can corrupt parties in previous layers.
References
Beerliová-Trubíniová, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1–10. ACM Press (1988)
Benhamouda, F., et al.: Can a public blockchain keep a secret? In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Part I, volume 12550 of LNCS, pp. 260–290. Springer, Heidelberg (2020)
Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press (2001)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (abstract) (informal contribution). In: Pomerance, C. (ed.) CRYPTO’87, volume 293 of LNCS, page 462. Springer, Heidelberg (1988)
Chaum, D., Crépeau, C., Damgard, I.: Multiparty unconditionally secure protocols (extended abstract). In: 20th ACM STOC, pp. 11–19. ACM Press (1988)
Choudhuri, A.R., Goel, A., Green, M., Jain, A., Kaptchuk, G.: Fluid MPC: secure multiparty computation with dynamic participants. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 94–123. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_4
Cramer, R., Damgård, I., Dziembowski, S., Hirt, M., Rabin, T.: Efficient multiparty computations secure against an adaptive adversary. In: Stern, J. (ed.) EUROCRYPT’99. LNCS, vol. 1592, pp. 311–326. Springer, Heidelberg (1999)
David, B., et al.: Perfect MPC over layered graphs. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. Part I, volume 14081 of LNCS, pp. 360–392. Springer, Heidelberg (2023)
Deligios, G., Goel, A., Liu-Zhang, C.D.: Maximally-fluid MPC with guaranteed output delivery. Cryptology ePrint Archive, Paper 2023/415 (2023). https://eprint.iacr.org/2023/415
Desmedt, Y., Wang, Y.: Perfectly secure message transmission revisited. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 502–517. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_33
Dolev, D., Dwork, C., Waarts, O., Yung, M.: Perfectly secure message transmission. J. ACM (JACM) 40(1), 17–47 (1993)
Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The round complexity of verifiable secret sharing and secure multicast. In: 33rd ACM STOC, pp. 580–589. ACM Press (2001)
Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Coan, B.A., Afek, Y., (eds.) 17th ACM PODC, pp. 101–111. ACM (1998)
Gentry, C., et al.: YOSO: you only speak once. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 64–93. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_3
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A., (eds.) 19th ACM STOC, pp. 218–229. ACM Press (1987)
Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J. Cryptol. 13(1), 31–60 (2000)
Hirt, M., Maurer, U.M., Przydatek, B.: Efficient secure multi-party computation. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 143–161. Springer, Heidelberg (2000)
Hofheinz, D., Müller-Quade, J.: A synchronous model for multi-party computation and the incompleteness of oblivious transfer. In: Proceedings of FCS, pp. 117–130. Citeseer (2004)
Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 477–498. Springer, Heidelberg (2013)
Lamport, L., Shostak, R., Pease, M.: The Byzantine Generals Problem, pp.203–226. Association for Computing Machinery, New York, NY, USA (2019)
Liu-Zhang, C.-D., Maurer, U.: Synchronous constructive cryptography. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Part II, volume 12551 of LNCS, pp. 439–472. Springer, Heidelberg (2020)
Manurangsi, P., Srinivasan, A., Vasudevan, P.N.: Nearly optimal robust secret sharing against rushing adversaries. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. Part III, volume 12172 of LNCS, pp. 156–185. Springer, Heidelberg (2020)
Nielsen, J.B.: On protocol security in the cryptographic model. BRICS (2003)
Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks (extended abstract). In: Luigi L., (ed.) 10th ACM PODC, pp. 51–59. ACM (1991)
Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC, pp. 73–85. ACM Press (1989)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press (1986)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 International Association for Cryptologic Research
About this paper
Cite this paper
Deligios, G., Konring, A., Liu-Zhang, CD., Narayanan, V. (2025). Statistical Layered MPC. In: Boyle, E., Mahmoody, M. (eds) Theory of Cryptography. TCC 2024. Lecture Notes in Computer Science, vol 15367. Springer, Cham. https://doi.org/10.1007/978-3-031-78023-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-78023-3_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-78022-6
Online ISBN: 978-3-031-78023-3
eBook Packages: Computer ScienceComputer Science (R0)