CINXE.COM
Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link href="/css/dist/css/bootstrap.min.css" rel="stylesheet"> <title>Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience</title> <link rel="stylesheet" href="/css/eprint.css?v=10"> <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" /> <link rel="apple-touch-icon" href="/img/apple-touch-icon-180x180.png" /> <style> a.toggle-open:after { content:' -'; font-weight: 800; } a.toggle-closed:after { content: " ›"; font-weight: 800; } .paper-abstract { white-space: pre-wrap; } #metadata dt { margin-top: 1rem; } #metadata dt + dd { /* gap between dt and first dd */ margin-top: .75rem; } #metadata dd { margin-left: 2rem; } #metadata dd.keywords { padding-bottom: .5rem; } span.authorName { margin-top: .5rem; font-style: italic; } </style> <script> MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEnvironments: false }, loader: { load: [ "ui/safe", "ui/lazy", ], }, options: { safeOptions: { allow: { URLs: "none", classes: "safe", cssIDs: "safe", styles: "safe", }, }, } }; </script> <script id="MathJax-script" async src="/js/mathjax/tex-chtml.js"></script> <meta name="citation_title" content="Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience"> <meta name="citation_author" content="Yuan Su"> <meta name="citation_author" content="Yuan Lu"> <meta name="citation_author" content="Jiliang Li"> <meta name="citation_author" content="Yuyi Wang"> <meta name="citation_author" content="Chengyi Dong"> <meta name="citation_author" content="Qiang Tang"> <meta name="citation_journal_title" content="Cryptology ePrint Archive"> <meta name="citation_publication_date" content="2024"> <meta name="citation_pdf_url" content="https://eprint.iacr.org/2024/1705.pdf"> <meta property="og:image" content="https://eprint.iacr.org/img/iacrlogo.png"/> <meta property="og:image:alt" content="IACR logo"/> <meta property="og:url" content="https://eprint.iacr.org/2024/1705"> <meta property="og:site_name" content="IACR Cryptology ePrint Archive" /> <meta property="og:type" content="article" /> <meta property="og:title" content="Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience" /> <meta property="og:description" content="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 phases G.O.D. and optimal resilience against $t<n/3$ malicious parties (where $n$ is the total number of parties). Same to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. While for achieving all phases 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 efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for 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 implementation of AMPC 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 of GS23) in the pessimistic case and 349 triples/sec (6X of GS23) in the good case, such that 31 parties require only 2-8 min to prepare a private Vickrey auction of 100 bidders or 10-36 min for a mixing network of $2^{10}$ inputs." /> <meta property="article:section" content="PROTOCOLS" /> <meta property="article:modified_time" content="2024-10-18T12:14:10+00:00" /> <meta property="article:published_time" content="2024-10-18T12:14:10+00:00" /> <meta property="article:tag" content="asynchronous multi-party computation" /> </head> <body> <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <div class="fixed-top" id="topNavbar"> <nav class="navbar navbar-custom navbar-expand-lg"> <div class="container px-0 justify-content-between justify-content-lg-evenly"> <div class="order-0 align-items-center d-flex"> <button class="navbar-toggler btnNoOutline" type="button" data-bs-toggle="collapse" data-bs-target="#navbarContent" aria-controls="navbarContent" aria-expanded="false"> <span class="icon-bar top-bar"></span> <span class="icon-bar middle-bar"></span> <span class="icon-bar bottom-bar"></span> </button> <a class="d-none me-5 d-lg-inline" href="https://iacr.org/"><img class="iacrlogo" src="/img/iacrlogo_small.png" alt="IACR Logo" style="max-width:6rem;"></a> </div> <a class="ePrintname order-1" href="/"> <span class="longNavName">Cryptology ePrint Archive</span> </a> <div class="collapse navbar-collapse order-3" id="navbarContent"> <ul class="navbar-nav me-auto ms-2 mb-2 mb-lg-0 justify-content-end w-100"> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Papers </a> <ul class="dropdown-menu me-3" aria-labelledby="navbarDropdown"> <span class="text-dark mx-3" style="white-space:nowrap;">Updates from the last:</span> <li><a class="dropdown-item ps-custom" href="/days/7">7 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/31">31 days</a></li> <li><a class="dropdown-item ps-custom" href="/days/183">6 months</a></li> <li><a class="dropdown-item ps-custom" href="/days/365">365 days</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/byyear">Listing by year</a></li> <li><a class="dropdown-item" href="/complete">All papers</a></li> <li><a class="dropdown-item" href="/complete/compact">Compact view</a></li> <li><a class="dropdown-item" href="https://www.iacr.org/news/subscribe">Subscribe</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/citation.html">How to cite</a></li> <li><hr class="dropdown-divider"></li> <li><a class="dropdown-item" href="/rss">Harvesting metadata</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="submissionsDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Submissions </a> <ul class="dropdown-menu me-3" aria-labelledby="submissionsDropdown"> <li><a class="dropdown-item" href="/submit">Submit a paper</a></li> <li><a class="dropdown-item" href="/revise">Revise or withdraw a paper</a></li> <li><a class="dropdown-item" href="/operations.html">Acceptance and publishing conditions</a></li> </ul> </li> <li class="ps-md-3 nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="aboutDropdown" role="button" data-bs-toggle="dropdown" aria-expanded="false"> About </a> <ul class="dropdown-menu me-3" aria-labelledby="aboutDropdown"> <li><a class="dropdown-item" href="/about.html">Goals and history</a></li> <li><a class="dropdown-item" href="/news.html">News</a></li> <li><a class="dropdown-item" href="/stats">Statistics</a></li> <li><a class="dropdown-item" href="/contact.html">Contact</a></li> </ul> </li> </ul> </div> <div class="dropdown ps-md-2 text-right order-2 order-lg-last"> <button class="btn btnNoOutline" type="button" id="dropdownMenuButton1" data-bs-toggle="dropdown" aria-expanded="false"> <img src="/img/search.svg" class="searchIcon" alt="Search Button"/> </button> <div id="searchDd" class="dropdown-menu dropdown-menu-end p-0" aria-labelledby="dropdownMenuButton1"> <form action="/search" method="GET"> <div class="input-group"> <input id="searchbox" name="q" type="search" class="form-control" autocomplete="off"> <button class="btn btn-secondary border input-group-append ml-2"> Search </button> </div> </form> <div class="ms-2 p-1 d-none"><a href="/search">Advanced search</a></div> </div> </div> </div> </nav> </div> <main id="eprintContent" class="container px-3 py-4 p-md-4"> <div class="row mt-4"> <div class="col-md-7 col-lg-8 pe-md-5"> <h4>Paper 2024/1705</h4> <h3 class="mb-3">Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience</h3> <div class="author"><span class="authorName">Yuan Su</span><span class="affiliation">, Xi’an Jiaotong University</span></div> <div class="author"><span class="authorName">Yuan Lu</span><span class="affiliation">, Institute of Software Chinese Academy of Sciences</span></div> <div class="author"><span class="authorName">Jiliang Li</span><span class="affiliation">, Xi’an Jiaotong University</span></div> <div class="author"><span class="authorName">Yuyi Wang</span><span class="affiliation">, CRRC Zhuzhou Institute</span></div> <div class="author"><span class="authorName">Chengyi Dong</span><span class="affiliation">, Xi’an Jiaotong University</span></div> <div class="author"><span class="authorName">Qiang Tang</span><span class="affiliation">, The University of Sydney</span></div> <h5 class="mt-3">Abstract</h5> <p style="white-space: pre-wrap;">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 phases G.O.D. and optimal resilience against $t<n/3$ malicious parties (where $n$ is the total number of parties). Same to hbMPC, Dumbo-MPC has a robust (almost) information-theoretic online phase that can efficiently perform online computations, given pre-processed multiplication triples. While for achieving all phases 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 efficiently implement the pessimistic path, we devise a concretely efficient zk-proof for 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 implementation of AMPC 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 of GS23) in the pessimistic case and 349 triples/sec (6X of GS23) in the good case, such that 31 parties require only 2-8 min to prepare a private Vickrey auction of 100 bidders or 10-36 min for a mixing network of $2^{10}$ inputs.</p> </div> <div id="metadata" class="col-md-5 col-lg-4 ps-md-5 mt-4 mt-md-0"> <h5>Metadata</h5> <dl> <dt> Available format(s) </dt> <dd> <a class="btn btn-sm btn-outline-dark" href="/2024/1705.pdf"> <img class="icon" src="/img/file-pdf.svg">PDF</a> </dd> <dt>Category</dt> <dd><a href="/search?category=PROTOCOLS"><small class="badge category category-PROTOCOLS">Cryptographic protocols</small></a></dd> <dt>Publication info</dt> <dd>Preprint. </dd> <dt>Keywords</dt> <dd class="keywords"><a href="/search?q=asynchronous%20multi-party%20computation" class="me-2 badge bg-secondary keyword">asynchronous multi-party computation</a></dd> <dt>Contact author(s)</dt> <dd><span class="font-monospace"> suyuan<span class="obfuscate"> @ </span>stu xjtu edu cn<br>luyuan<span class="obfuscate"> @ </span>iscas ac cn<br>jiliang li<span class="obfuscate"> @ </span>xjtu edu cn<br>yuyiwang920<span class="obfuscate"> @ </span>gmail com<br>2196113533<span class="obfuscate"> @ </span>xjtu stu edu cn<br>qiang tang<span class="obfuscate"> @ </span>sydney edu au </span> </dd> <dt>History</dt> <dd>2024-10-21: approved</dd> <dd>2024-10-18: received</dd> <dd><a rel="nofollow" href="/archive/versions/2024/1705">See all versions</a></dd> <dt>Short URL</dt> <dd><a href="https://ia.cr/2024/1705">https://ia.cr/2024/1705</a></dd> <dt>License</dt> <dd><a rel="license" target="_blank" href="https://creativecommons.org/licenses/by/4.0/"> <img class="licenseImg" src="/img/license/CC_BY.svg" alt="Creative Commons Attribution" title="Creative Commons Attribution"><br> <small>CC BY</small> </a> </dd> </dl> </div> </div> <p class="mt-4"><strong>BibTeX</strong> <button id="bibcopy" class="ms-2 btn btn-sm btn-outline-dark" aria-label="Copy to clipboard" onclick="copyBibtex()"> <img src="/img/copy-outline.svg" class="icon">Copy to clipboard</button></p> <pre id="bibtex"> @misc{cryptoeprint:2024/1705, author = {Yuan Su and Yuan Lu and Jiliang Li and Yuyi Wang and Chengyi Dong and Qiang Tang}, title = {Dumbo-{MPC}: Efficient Fully Asynchronous {MPC} with Optimal Resilience}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1705}, year = {2024}, url = {https://eprint.iacr.org/2024/1705} } </pre> <script> var bibcopy; function triggerTooltip() { console.log('setting tooltip'); } window.onload = triggerTooltip; function copyBibtex() { let range = document.createRange(); range.selectNode(document.getElementById('bibtex')); window.getSelection().removeAllRanges(); window.getSelection().addRange(range); document.execCommand('copy'); window.getSelection().removeAllRanges(); let bibcopy = document.getElementById('bibcopy'); let copyTooltip = new bootstrap.Tooltip(bibcopy, {trigger: 'manual', title: 'Copied!'}); copyTooltip.show(); setTimeout(function() { copyTooltip.dispose(); }, 2000); } </script> </main> <div class="container-fluid mt-auto" id="eprintFooter"> <a href="https://iacr.org/"> <img id="iacrlogo" src="/img/iacrlogo_small.png" class="img-fluid d-block mx-auto" alt="IACR Logo"> </a> <div class="colorDiv"></div> <div class="alert alert-success w-75 mx-auto"> Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content. </div> </div> <script src="/css/bootstrap/js/bootstrap.bundle.min.js"></script> <script> var topNavbar = document.getElementById('topNavbar'); if (topNavbar) { document.addEventListener('scroll', function(e) { if (window.scrollY > 100) { topNavbar.classList.add('scrolled'); } else { topNavbar.classList.remove('scrolled'); } }) } </script> </body> </html>