TY - GEN
T1 - Dumbo-MPC
T2 - 34th USENIX Security Symposium, USENIX Security 2025
AU - Su, Yuan
AU - Lu, Yuan
AU - Li, Jiliang
AU - Wang, Yuyi
AU - Dong, Chengyi
AU - Tang, Qiang
N1 - Publisher Copyright:
© 2025 by The USENIX Association All Rights Reserved.
PY - 2025
Y1 - 2025
N2 - Fully asynchronous multi-party computation (AMPC) has superior robustness in realizing privacy and guaranteed output delivery (G.O.D.) against asynchronous adversaries that can arbitrarily delay communications. However, none of these protocols are truly practical, as they either have sub-optimal resilience, incur cumbersome communication cost, or suffer from an online phase with extra cryptographic overhead. The only attempting implementation-HoneyBadgerMPC (hbMPC)-merely ensures G.O.D. in some implausible optimistic cases due to a non-robust offline pre-processing phase. We propose Dumbo-MPC a concretely efficient AMPC-as-a-service design with all-phase G.O.D. and optimal resilience against t < n/3 malicious parties (where n is the total number of parties). Similar to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. To achieve all-phase G.O.D., we design a novel dual-mode offline protocol that can robustly pre-process multiplication triples in asynchrony. The offline phase features O(n) per-triple communication in the optimistic case, followed by a fully asynchronous fallback to a pessimistic path to securely restore G.O.D. in the bad case. To (concretely) efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for the product relationship of secret shares over compact KZG polynomial commitments, which enables us to reduce the degree of two secret shares’ product from 2t to t and could be of independent interest. We also implement and extensively evaluate Dumbo-MPC (particularly its offline phase) in varying network settings with up to 31 AWS servers. To our knowledge, we provide the first AMPC implementation with all-phase G.O.D. A recent asynchronous triple generation protocol from Groth and Shoup (GS23) is also implemented and experimentally compared. When n = 31, Dumbo-MPC generates 94 triples/sec (almost twice as many as GS23) in the pessimistic case and 349 triples/sec (about 6X of GS23) in the good case.
AB - Fully asynchronous multi-party computation (AMPC) has superior robustness in realizing privacy and guaranteed output delivery (G.O.D.) against asynchronous adversaries that can arbitrarily delay communications. However, none of these protocols are truly practical, as they either have sub-optimal resilience, incur cumbersome communication cost, or suffer from an online phase with extra cryptographic overhead. The only attempting implementation-HoneyBadgerMPC (hbMPC)-merely ensures G.O.D. in some implausible optimistic cases due to a non-robust offline pre-processing phase. We propose Dumbo-MPC a concretely efficient AMPC-as-a-service design with all-phase G.O.D. and optimal resilience against t < n/3 malicious parties (where n is the total number of parties). Similar to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. To achieve all-phase G.O.D., we design a novel dual-mode offline protocol that can robustly pre-process multiplication triples in asynchrony. The offline phase features O(n) per-triple communication in the optimistic case, followed by a fully asynchronous fallback to a pessimistic path to securely restore G.O.D. in the bad case. To (concretely) efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for the product relationship of secret shares over compact KZG polynomial commitments, which enables us to reduce the degree of two secret shares’ product from 2t to t and could be of independent interest. We also implement and extensively evaluate Dumbo-MPC (particularly its offline phase) in varying network settings with up to 31 AWS servers. To our knowledge, we provide the first AMPC implementation with all-phase G.O.D. A recent asynchronous triple generation protocol from Groth and Shoup (GS23) is also implemented and experimentally compared. When n = 31, Dumbo-MPC generates 94 triples/sec (almost twice as many as GS23) in the pessimistic case and 349 triples/sec (about 6X of GS23) in the good case.
UR - https://www.scopus.com/pages/publications/105021345277
M3 - 会议稿件
AN - SCOPUS:105021345277
T3 - Proceedings of the 34th USENIX Security Symposium
SP - 1925
EP - 1944
BT - Proceedings of the 34th USENIX Security Symposium
PB - USENIX Association
Y2 - 13 August 2025 through 15 August 2025
ER -