Search results

<!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>Search results</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> input { background-color: #e8e8e8 !important; } mark { font-weight: 600; padding: .2em 0px .2em 0px; color: black; } span.term { font-weight: 700 !important; font-family: var(--bs-font-monospace), monospace !important; } form { background-color:#fff; } @media (min-width: 768px) { form { position:sticky;top:6rem; } } </style> <meta name="description" content="Search the Cryptology ePrint Archive"> </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"> <div class="col-12 col-lg-4"> <form class="p-2 pt-md-4 align-items-end needs-validation" novalidate onsubmit="return validateForm()" method="GET" action="/search"> <label for="anything" class="mt-2 form-label">Match anything</label> <input type="text" name="q" class="form-control form-control-sm" id="anything" aria-label="Match anything" value="asynchronous"> <label for="title" class="mt-4 form-label">Match title</label> <input type="text" name="title" class="form-control form-control-sm" id="title" aria-label="Match title" value=""> <label for="authors" class="mt-4 form-label">Match authors</label> <input type="text" name="authors" class="form-control form-control-sm" id="authors" aria-label="Match authors" value=""> <label for="category" class="mt-4 form-label">Category</label><br> <select class="form-select form-select-sm" id="category" name="category" aria-label="Category"> <option value="">All categories</option> <option value="APPLICATIONS" >Applications</option> <option value="PROTOCOLS" >Cryptographic protocols</option> <option value="FOUNDATIONS" >Foundations</option> <option value="IMPLEMENTATION" >Implementation</option> <option value="SECRETKEY" >Secret-key cryptography</option> <option value="PUBLICKEY" >Public-key cryptography</option> <option value="ATTACKS" >Attacks and cryptanalysis</option> </select> <div class="row d-none d-lg-flex"> <div class="col-6"> <label for="submittedafter" class="mt-4 form-label">Submitted after</label><br> <input class="form-control form-control-sm" type="number" min="1996" id="submittedafter" name="submittedafter" aria-label="Submitted after" value="None" placeholder="Enter a year"> </div> <div class="col-6"> <label for="submittedbefore" class="mt-4 form-label">Submitted before</label><br> <input class="form-control form-control-sm" type="number" min="1996" id="submittedbefore" name="submittedbefore" aria-label="Submitted before" value="None" placeholder="Enter a year"> <div class="invalid-feedback"> Dates are inconsistent </div> </div> </div> <div class="row d-none d-lg-flex"> <div class="col-6"> <label for="revisedafter" class="mt-4 form-label">Revised after</label><br> <input class="form-control form-control-sm" type="number" min="1996" id="revisedafter" name="revisedafter" aria-label="Revised after" placeholder="Enter a year" value="None"> <div class="invalid-feedback"> Dates are inconsistent </div> </div> <div class="col-6"> <label for="revisedbefore" class="mt-4 form-label">Revised before</label><br> <input class="form-control form-control-sm" type="number" min="1996" id="revisedbefore" name="revisedbefore" aria-label="Revised before" value="None" placeholder="Enter a year"> </div> </div> <div class="d-none d-lg-flex mt-3"> <div class="form-check"> <input type="checkbox" id="relevance" name="relevance" > <label for="relevance" class="form-check-label ms-2">Sort by relevance</label> </div> </div> <div class="mt-3 d-flex"> <button class="btn btn-primary btn-sm" type="submit">Search</button> <button id="clearButton" class="btn btn-secondary btn-sm ms-2" type="button">Clear</button> <button id="helpButton" class="btn btn-info btn-sm ms-auto" type="button" data-bs-toggle="modal" data-bs-target="#helpModal">Help</button> </div> </form> <div class="modal" tabindex="-1" id="helpModal"> <div class="modal-dialog modal-lg"> <div class="modal-content"> <div class="modal-header"> <h4 class="modal-title">Search Help</h4> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <p> You can search for a phrase by enclosing it in double quotes, e.g., <span class="term text-nowrap"><a href="/search?q=%22differential%20privacy%22">"differential privacy"</a></span>. </p> <p> You can require or exclude specific terms using + and -. For example, to search for papers that contain the term elliptic but not the term factoring, use <span class="term text-nowrap"><a href="/search?q=%2Belliptic%20-factoring">+elliptic -factoring</a></span> </p> <p> To search in a title or for author name, use <span class="term text-nowrap"><a href="/search?q=title%3Aisogeny%20author%3Aboneh">title:isogeny author:boneh</a></span>. If you want to require both, you can use <span class="term text-nowrap"><a href="/search?q=title%3Aisogeny%20AND%20author%3Aboneh">title:isogeny AND author:boneh</a></span> because it recognizes logical operators <span class="term">AND</span> and <span class="term">OR</span>. This is equivalent to <a href="/search?title=isogeny&authors=boneh">using the individual fields</a> for author and title. You can also use NOT to negate a condition, as with <span class="term text-nowrap"><a href="/search?q=title%3Aisogeny%20AND%20NOT%20author%3Aboneh">title:isogeny AND NOT author:boneh</a></span> to search for papers with an author other than Boneh. </p> <p> To find documents containing a term starting with the string <span class="term">differe</span>, use <span class="term"><a href="/search?q=differe%2A">differe*</a></span>. This will match the terms difference, different, and differential </p> <p> Note that search applies stemming, so that if you search for <span class="term">yield</span> it will also match terms <span class="term">yields</span> and <span class="term">yielding</span>. If you want to disable stemming, capitalize the term. A search for <span class="term">Adam</span> will not match the term 'Adams'. </p> <p> The system attempts to recognize possible misspellings. This is perhaps a source of amusement more than anything else. </p> <p> This currently searches the text in titles, authors, abstracts, and keywords, but does not search in the PDF or PS itself. </p> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> </div> </div> </div> </div>  </div> <div class="col-12 col-lg-8" style="min-height:80vh"> <h4 class="mt-3 ms-4">284 results sorted by ID</h5> <div class="ms-lg-4 mt-3 results"> <div class="mb-4"> <div class="d-flex"><a title="2025/406" class="paperlink" href="/2025/406">2025/406</a> <span class="ms-2"><a href="/2025/406.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-03-03</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>AsyRand: fast asynchronous distributed randomness beacon with reconfiguration</strong> <div class="mt-1"><span class="fst-italic">Liang Zhang, Tao Liu, Zhanrong Ou, Haibin Kan, Jiheng Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Distributed randomness beacon protocols, which generate publicly verifiable randomness at regular intervals, are crucial for a wide range of applications. The publicly verifiable secret sharing (PVSS) scheme is a promising cryptographic primitive for implementing beacon protocols, such as Hydrand (S\&P '20) and SPURT (S\&P '22). However, two key challenges for practical deployment remain unresolved: asynchrony and reconfiguration. In this paper, we introduce the $AsyRand$ beacon protocol to...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/303" class="paperlink" href="/2025/303">2025/303</a> <span class="ms-2"><a href="/2025/303.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Algorand: Reaching Agreement with Near Linear Communication and Constant Expected Time</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Eli Chouatt, Ivan Damgård, Yossi Gilad, Gilad Stern, Sophia Yakoubov</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The celebrated Algorand protocol solves validated byzantine agreement in a scalable manner in the synchronous setting. In this paper, we study the feasibility of similar solutions in the asynchronous setting. Our main result is an asynchronous validated byzantine agreement protocol that we call Asynchronous Algorand. As with Algorand, it terminates in an expected constant number of rounds, and honest parties send an expected $O(n ~\mathsf{polylog}~n)$ bits, where $n$ is the number of...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/297" class="paperlink" href="/2025/297">2025/297</a> <span class="ms-2"><a href="/2025/297.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-25</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Zero-Trust Threshold Signatures in Large-Scale Dynamic Asynchronous Networks</strong> <div class="mt-1"><span class="fst-italic">Offir Friedman, Avichai Marmor, Dolev Mutzari, Yehonatan Cohen Scaly, Yuval Spiizer</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Threshold signatures have become a critical tool in cryptocurrency systems, offering enhanced security by distributing the signing process among multiple signers. In this work, we distribute this process between a client and a permissionless decentralized blockchain, and present novel protocols for ECDSA and EdDSA/Schnorr signatures in this setting. Typical threshold access architectures used by trusted custodians suffer from the honeypot problem, wherein the more assets the custodian holds,...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/228" class="paperlink" href="/2025/228">2025/228</a> <span class="ms-2"><a href="/2025/228.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-19</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Network agnostic consensus in constant time</strong> <div class="mt-1"><span class="fst-italic">Simon Holmgaard Kamp, Julian Loss, Jesper Buus Nielsen</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Network agnostic protocols (Blum, Katz, Loss TCC `19) are consensus or MPC protocols that strike a balance between purely synchronous and asynchronous protocols. Given thresholds $t_a,t_s$ that satisfy $t_a<n/3<t_s<n/2$ and $2t_s+t_a<n$, they have the unique property of remaining secure against an adversary that either (1) corrupts up to $t_s$ parties in a synchronous execution where all messages are delivered within a known bound $\Delta$ or (2) corrupts up to $t_a$ in an asynchronous...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/149" class="paperlink" href="/2025/149">2025/149</a> <span class="ms-2"><a href="/2025/149.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-01-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Asynchronous Distributed Key Reconfiguration and Its Applications</strong> <div class="mt-1"><span class="fst-italic">Hanwen Feng, Yingzi Gao, Yuan Lu, Qiang Tang, Jing Xu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In this paper, we study practical constructions of asynchronous distributed key reconfiguration ($\mathsf{ADKR}$), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation ($\mathsf{ADKG}$) protocols theoretically solve $\mathsf{ADKR}$, they fail to deliver satisfactory scalability due to cubic...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/143" class="paperlink" href="/2025/143">2025/143</a> <span class="ms-2"><a href="/2025/143.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement</strong> <div class="mt-1"><span class="fst-italic">Simon Holmgaard Kamp</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We translate the \emph{expand-and-extract} framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with $2^{-\lambda}$ error probability in $\lambda+1$ rounds, we make it work in asynchrony in $\lambda+3$ rounds. At the heart of their solution is a \emph{proxcensus} primitive, which is used to reach graded agreement with $2^r+1$ grades in $r$ rounds by reducing proxcensus with $2s-1$ grades to proxcensus with $s$ grades...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/134" class="paperlink" href="/2025/134">2025/134</a> <span class="ms-2"><a href="/2025/134.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-01-28</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>TockOwl: Asynchronous Consensus with Fault and Network Adaptability</strong> <div class="mt-1"><span class="fst-italic">Minghang Li, Qianhong Wu, Zhipeng Wang, Bo Qin, Bohang Wei, Hang Ruan, Shihong Xiong, Zhenyang Ding</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">BFT protocols usually have a waterfall-like degradation in performance in the face of crash faults. Some BFT protocols may not experience sudden performance degradation under crash faults. They achieve this at the expense of increased communication and round complexity in fault-free scenarios. In a nutshell, existing protocols lack the adaptability needed to perform optimally under varying conditions. We propose TockOwl, the first asynchronous consensus protocol with fault adaptability....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/128" class="paperlink" href="/2025/128">2025/128</a> <span class="ms-2"><a href="/2025/128.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous YOSO a la Paillier</strong> <div class="mt-1"><span class="fst-italic">Ivan Bjerre Damgård, Simon Holmgaard Kamp, Julian Loss, Jesper Buus Nielsen</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present the first complete adaptively secure asynchronous MPC protocol for the YOSO (You Speak Only Once) setting. In contrast to many previous MPC constructions in the YOSO model, we provide a full stack implementation that does MPC, role assignment and total order broadcast. Therefore, our construction is also the first to provide adaptively secure asynchronous total order broadcast and MPC that is sub-quadratic in the number of parties and does not require threshold fully homomorphic...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/098" class="paperlink" href="/2025/098">2025/098</a> <span class="ms-2"><a href="/2025/098.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-01-22</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Fast, private and regulated payments in asynchronous networks</strong> <div class="mt-1"><span class="fst-italic">Maxence Brugeres, Victor Languille, Petr Kuznetsov, Hamza Zarfaoui</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We propose a decentralized asset-transfer system that enjoys full privacy: no party can learn the details of a transaction, except for its issuer and its recipient. Furthermore, the recipient is only aware of the amount of the transaction. Our system does not rely on consensus or synchrony assumptions, and therefore, it is responsive, since it runs at the actual network speed. Under the hood, every transaction creates a consumable coin equipped with a non-interactive zero-knowledge proof...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2025/006" class="paperlink" href="/2025/006">2025/006</a> <span class="ms-2"><a href="/2025/006.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-01-01</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Nearly Quadratic Asynchronous Distributed Key Generation</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Renas Bacho, Julian Loss, Gilad Stern</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We prove that for any $1\le k\le \log n$, given a VRF setup and assuming secure erasures, there exists a protocol for Asynchronous Distributed Key Generation (ADKG) that is resilient to a strongly adaptive adversary that can corrupt up to $f<n/3$ parties. With all but negligible probability, all nonfaulty parties terminate in an expected $O(k)$ rounds and send a total expected $\tilde{O}(n^{2+1/k})$ messages.</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/2098" class="paperlink" href="/2024/2098">2024/2098</a> <span class="ms-2"><a href="/2024/2098.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-18</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asymptotically Optimal Adaptive Asynchronous Common Coin and DKG with Silent Setup</strong> <div class="mt-1"><span class="fst-italic">Hanwen Feng, Qiang Tang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present the first optimal-resilient, adaptively secure asynchronous common coin protocol with $O(\lambda n^2)$ communication complexity and $O(1)$ rounds, requiring only a public silent setup. Our protocol immediately implies a sequence of quadratic-communication, constant-round asynchronous Byzantine agreement protocols, and also asynchronous distributed key generation with a silent setup. Along the way, we formulate a new primitive called {\em asynchronous subset alignment}, and...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1976" class="paperlink" href="/2024/1976">2024/1976</a> <span class="ms-2"><a href="/2024/1976.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-12-06</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>HI-CKKS: Is High-Throughput Neglected? Reimagining CKKS Efficiency with Parallelism</strong> <div class="mt-1"><span class="fst-italic">Fuyuan Chen, Jiankuo Dong, Xiaoyu Hu, Zhenjiang Dong, Wangchen Dai, Jingqiang Lin, Fu Xiao</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-IMPLEMENTATION">Implementation</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The proliferation of data outsourcing and cloud services has heightened privacy vulnerabilities. CKKS, among the most prominent homomorphic encryption schemes, allows computations on encrypted data, serving as a critical privacy safeguard. However, performance remains a central bottleneck, hindering widespread adoption. Existing optimization efforts often prioritize latency reduction over throughput performance. This paper presents HI-CKKS, a throughput-oriented High-performance...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1937" class="paperlink" href="/2024/1937">2024/1937</a> <span class="ms-2"><a href="/2024/1937.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-11-29</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Byzantine Consensus with Trusted Monotonic Counters</strong> <div class="mt-1"><span class="fst-italic">Yackolley Amoussou-Guenou, Maurice Herlihy, Maria Potop Butucaru</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The paper promotes a new design paradigm for Byzantine tolerant distributed algorithms using trusted abstractions (oracles) specified in a functional manner. The contribution of the paper is conceptual. The objective here is to design distributed fundamental algorithms such as reliable broadcast and asynchronous byzantine consensus using trusted execution environments and to help designers to compare various solutions on a common ground. In this framework we revisit the Bracha's seminal...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1878" class="paperlink" href="/2024/1878">2024/1878</a> <span class="ms-2"><a href="/2024/1878.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-11-17</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Tighter Security for Group Key Agreement in the Random Oracle Model</strong> <div class="mt-1"><span class="fst-italic">Andreas Ellison, Karen Klein</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The Messaging Layer Security (MLS) protocol, recently standardized in RFC 9420, aims to provide efficient asynchronous group key establishment with strong security guarantees. The main component of MLS, which is the source of its important efficiency and security properties, is a protocol called TreeKEM. Given that a major vision for the MLS protocol is for it to become the new standard for messaging applications like WhatsApp, Facebook Messenger, Signal, etc., it has the potential to be...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1761" class="paperlink" href="/2024/1761">2024/1761</a> <span class="ms-2"><a href="/2024/1761.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-29</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Resilience-Optimal Lightweight High-threshold Asynchronous Verifiable Secret Sharing</strong> <div class="mt-1"><span class="fst-italic">Hao Cheng, Jiliang Li, Yizhong Liu, Yuan Lu, Weizhi Meng, Zhenfeng Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Shoup and Smart (SS24) recently introduced a lightweight asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience directly from cryptographic hash functions (JoC 2024), offering plausible quantum resilience and computational efficiency. However, SS24 AVSS only achieves standard secrecy to keep the secret confidential against $n/3$ corrupted parties \textit{if no honest party publishes its share}. In contrast, from ``heavyweight'' public-key cryptography, one can...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1717" class="paperlink" href="/2024/1717">2024/1717</a> <span class="ms-2"><a href="/2024/1717.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-21</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Asynchronous MPC from Lightweight Cryptography</strong> <div class="mt-1"><span class="fst-italic">Atsuki Momose</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present an asynchronous secure multi-party computation (MPC) protocol that is practically efficient. Our protocol can evaluate any arithmetic circuit with linear communication in the number of parties per multiplication gate, while relying solely on computationally lightweight cryptography such as hash function and symmetric encryption. Our protocol is optimally resilient and tolerates $t$ malicious parties among $n = 3t+1$ parties. At the technical level, we manage to apply the...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1710" class="paperlink" href="/2024/1710">2024/1710</a> <span class="ms-2"><a href="/2024/1710.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-11-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>$\widetilde{\mbox{O}}$ptimal Adaptively Secure Hash-based Asynchronous Common Subset</strong> <div class="mt-1"><span class="fst-italic">Hanwen Feng, Zhenliang Lu, Qiang Tang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1705" class="paperlink" href="/2024/1705">2024/1705</a> <span class="ms-2"><a href="/2024/1705.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-18</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Dumbo-MPC: Efficient Fully Asynchronous MPC with Optimal Resilience</strong> <div class="mt-1"><span class="fst-italic">Yuan Su, Yuan Lu, Jiliang Li, Yuyi Wang, Chengyi Dong, Qiang Tang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">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....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1682" class="paperlink" href="/2024/1682">2024/1682</a> <span class="ms-2"><a href="/2024/1682.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-28</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Toward Optimal-Complexity Hash-Based Asynchronous MVBA with Optimal Resilience</strong> <div class="mt-1"><span class="fst-italic">Jovan Komatovic, Joachim Neu, Tim Roughgarden</span></div> </div> </div> <p class="mb-0 mt-1 search-abstract">Multi-valued validated Byzantine agreement (MVBA), a fundamental primitive of distributed computing, allows $n$ processes to agree on a valid $\ell$-bit value, despite $t$ faulty processes behaving maliciously. Among hash-based solutions for the asynchronous setting with adaptive faults, the state-of-the-art HMVBA protocol achieves optimal $O(n^2)$ message complexity, (near-)optimal $O(n \ell + n^2 \lambda \log n)$ bit complexity, and optimal $O(1)$ time complexity. However, it only...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1666" class="paperlink" href="/2024/1666">2024/1666</a> <span class="ms-2"><a href="/2024/1666.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-26</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Computationally Efficient Asynchronous MPC with Linear Communication and Low Additive Overhead</strong> <div class="mt-1"><span class="fst-italic">Akhil Bandarupalli, Xiaoyu Ji, Aniket Kate, Chen-Da Liu-Zhang, Yifan Song</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We explore the setting of asynchronous multi-party computation (AMPC) with optimal resilience $n=3t+1$, and develop an efficient protocol that optimizes both communication and computation. The recent work by Goyal, Liu-Zhang, and Song [Crypto' 24] was the first to achieve AMPC with amortized linear communication cost without using computationally heavy public-key cryptography. However, its $\mathcal{O}(n^{14})$ additive communication overhead renders it impractical for most real-world...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1653" class="paperlink" href="/2024/1653">2024/1653</a> <span class="ms-2"><a href="/2024/1653.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>AD-MPC: Fully Asynchronous Dynamic MPC with Guaranteed Output Delivery</strong> <div class="mt-1"><span class="fst-italic">Wenxuan Yu, Minghui Xu, Bing Wu, Sisi Duan, Xiuzhen Cheng</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Traditional secure multiparty computation (MPC) protocols presuppose a fixed set of participants throughout the computational process. To address this limitation, Fluid MPC [CRYPTO 2021] presents a dynamic MPC model that allows parties to join or exit during circuit evaluation dynamically. However, existing dynamic MPC protocols can guarantee safety but not liveness within asynchronous networks. This paper introduces ΠAD-MPC, a fully asynchronous dynamic MPC protocol. ΠAD-MPC ensures both...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1593" class="paperlink" href="/2024/1593">2024/1593</a> <span class="ms-2"><a href="/2024/1593.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-15</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Stateful Communication with Malicious Parties</strong> <div class="mt-1"><span class="fst-italic">Chen-Da Liu-Zhang, Christopher Portmann, Guilherme Rito</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Cryptography's most common use is secure communication---e.g. Alice can use encryption to hide the contents of the messages she sends to Bob (confidentiality) and can use signatures to assure Bob she sent these messages (authenticity). While one typically considers stateless security guarantees---for example a channel that Alice can use to send messages securely to Bob---one can also consider stateful ones---e.g. an interactive conversation between Alice, Bob and their friends where...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1463" class="paperlink" href="/2024/1463">2024/1463</a> <span class="ms-2"><a href="/2024/1463.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-09-19</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Verifiable Secret Sharing with Elastic Thresholds and Distributed Key Generation</strong> <div class="mt-1"><span class="fst-italic">Junming Li, Zhi Lu, Renfei Shen, Yuanqing Feng, Songfeng Lu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PUBLICKEY">Public-key cryptography</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Distributed Key Generation (DKG) is a technique that enables the generation of threshold cryptography keys among a set of mutually untrusting nodes. DKG generates keys for a range of decentralized applications such as threshold signatures, multiparty computation, and Byzantine consensus. Over the past five years, research on DKG has focused on optimizing network communication protocols to improve overall system efficiency by reducing communication complexity. However, SOTA asynchronous...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1365" class="paperlink" href="/2024/1365">2024/1365</a> <span class="ms-2"><a href="/2024/1365.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-08-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>High-Throughput GPU Implementation of Dilithium Post-Quantum Digital Signature</strong> <div class="mt-1"><span class="fst-italic">Shiyu Shen, Hao Yang, Wangchen Dai, Hong Zhang, Zhe Liu, Yunlei Zhao</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-IMPLEMENTATION">Implementation</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Digital signatures are fundamental building blocks in various protocols to provide integrity and authenticity. The development of the quantum computing has raised concerns about the security guarantees aﬀorded by classical signature schemes. CRYSTALS-Dilithium is an eﬃcient post-quantum digital signature scheme based on lattice cryptography and has been selected as the primary algorithm for standardization by the National Institute of Standards and Technology. In this work, we present a...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1285" class="paperlink" href="/2024/1285">2024/1285</a> <span class="ms-2"><a href="/2024/1285.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-11</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Robust Multiparty Computation from Threshold Encryption Based on RLWE</strong> <div class="mt-1"><span class="fst-italic">Antoine Urban, Matthieu Rambaud</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PUBLICKEY">Public-key cryptography</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We consider protocols for secure multi-party computation (MPC) built from FHE under honest majority, i.e., for $n=2t+1$ players of which $t$ are corrupt, that are robust. Surprisingly there exists no robust threshold FHE scheme based on BFV to design such MPC protocols. Precisely, all existing methods for generating a common relinearization key can abort as soon as one player deviates. We address this issue, with a new relinearization key (adapted from [CDKS19, CCS'19]) which we show how to...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1260" class="paperlink" href="/2024/1260">2024/1260</a> <span class="ms-2"><a href="/2024/1260.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-19</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>zk-promises: Anonymous Moderation, Reputation, and Blocking from Anonymous Credentials with Callbacks</strong> <div class="mt-1"><span class="fst-italic">Maurice Shih, Michael Rosenberg, Hari Kailad, Ian Miers</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Anonymity is essential for free speech and expressing dissent, but platform moderators need ways to police bad actors. For anonymous clients, this may involve banning their accounts, docking their reputation, or updating their state in a complex access control scheme. Frequently, these operations happen asynchronously when some violation, e.g., a forum post, is found well after the offending action occurred. Malicious clients, naturally, wish to evade this asynchronous negative feedback....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/1108" class="paperlink" href="/2024/1108">2024/1108</a> <span class="ms-2"><a href="/2024/1108.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-07-08</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Faster Asynchronous Blockchain Consensus and MVBA</strong> <div class="mt-1"><span class="fst-italic">Matthieu Rambaud</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Blockchain consensus, a.k.a. BFT SMR, are protocols enabling $n$ processes to decide on an ever-growing chain. The fastest known asynchronous one is called 2-chain VABA (PODC'21 and FC'22), and is used as fallback chain in Abraxas* (CCS'23). It has a claimed $9.5\delta$ expected latency when used for a single shot instance, a.k.a. an MVBA. We exhibit attacks breaking it. Hence, the title of the fastest asynchronous MVBA with quadratic messages complexity goes to sMVBA (CCS'22), with...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/990" class="paperlink" href="/2024/990">2024/990</a> <span class="ms-2"><a href="/2024/990.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-17</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Perfectly-secure Network-agnostic MPC with Optimal Resiliency</strong> <div class="mt-1"><span class="fst-italic">Shravani Patil, Arpita Patra</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We study network-agnostic secure multiparty computation with perfect security. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous. The feasibility of perfectly-secure MPC in synchronous and asynchronous networks has been settled a long ago. The landmark work of [Ben-Or, Goldwasser, and Wigderson, STOC'88] shows that $n...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/942" class="paperlink" href="/2024/942">2024/942</a> <span class="ms-2"><a href="/2024/942.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-06-12</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Let Them Drop: Scalable and Efficient Federated Learning Solutions Agnostic to Client Stragglers</strong> <div class="mt-1"><span class="fst-italic">Riccardo Taiello, Melek Önen, Clémentine Gritti, Marco Lorenzi</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Secure Aggregation (SA) stands as a crucial component in modern Federated Learning (FL) systems, facilitating collaborative training of a global machine learning model while protecting the privacy of individual clients' local datasets. Many existing SA protocols described in the FL literature operate synchronously, leading to notable runtime slowdowns due to the presence of stragglers (i.e. late-arriving clients). To address this challenge, one common approach is to consider stragglers as...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/885" class="paperlink" href="/2024/885">2024/885</a> <span class="ms-2"><a href="/2024/885.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-06-03</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Bruisable Onions: Anonymous Communication in the Asynchronous Model</strong> <div class="mt-1"><span class="fst-italic">Megumi Ando, Anna Lysyanskaya, Eli Upfal</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In onion routing, a message travels through the network via a series of intermediaries, wrapped in layers of encryption to make it difficult to trace. Onion routing is an attractive approach to realizing anonymous channels because it is simple and fault tolerant. Onion routing protocols provably achieving anonymity in realistic adversary models are known for the synchronous model of communication so far. In this paper, we give the first onion routing protocol that achieves anonymity in...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/846" class="paperlink" href="/2024/846">2024/846</a> <span class="ms-2"><a href="/2024/846.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-12-18</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Distributed Asynchronous Remote Key Generation</strong> <div class="mt-1"><span class="fst-italic">Mark Manulis, Hugo Nartz</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous Remote Key Generation (ARKG) is a primitive introduced by Frymann et al. at ACM CCS 2020. It enables a sender to generate a new public key $pk'$ for a receiver ensuring only it can, at a later time, compute the corresponding private key $sk'$. These key pairs are indistinguishable from freshly generated ones and can be used in various public-key cryptosystems such as digital signatures and public-key encryption. ARKG has been explored for applications in WebAuthn credential...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/774" class="paperlink" href="/2024/774">2024/774</a> <span class="ms-2"><a href="/2024/774.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-05-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Byzantine Reliable Broadcast with One Trusted Monotonic Counter</strong> <div class="mt-1"><span class="fst-italic">Yackolley Amoussou-Guenou, Lionel Beltrando, Maurice Herlihy, Maria Potop-Butucaru</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator even if some processes (perhaps including the initiator) are Byzantine. In asynchronous settings it is known since the prominent work of Bracha [Bracha87] that Byzantine reliable broadcast can be implemented deterministically if $n \geq 3t+1$ where $t$ is an upper bound on the...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/696" class="paperlink" href="/2024/696">2024/696</a> <span class="ms-2"><a href="/2024/696.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-06-21</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>A Theoretical Take on a Practical Consensus Protocol</strong> <div class="mt-1"><span class="fst-italic">Victor Shoup</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The Asynchronous Common Subset (ACS) problem is a fundamental problem in distributed computing. Very recently, Das et al. (2024) developed a new ACS protocol with several desirable properties: (i) it provides optimal resilience, tolerating up to $t < n/3$ corrupt parties out of $n$ parties in total, (ii) it does not rely on a trusted set up, (iii) it utilizes only "lighweight" cryptography, which can be instantiated using just a hash function, and (iv) it has expected round complexity...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/685" class="paperlink" href="/2024/685">2024/685</a> <span class="ms-2"><a href="/2024/685.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-05-04</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Committing AVID with Partial Retrieval and Optimal Storage</strong> <div class="mt-1"><span class="fst-italic">Nicolas Alhaddad, Leonid Reyzin, Mayank Varia</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous Verifiable Information Dispersal (AVID) allows a dealer to disperse a message $M$ across a collection of server replicas consistently and efficiently, such that any future client can reliably retrieve the message $M$ if some servers fail. Since AVID was introduced by Cachin and Tessaro in 2005, several works improved the asymptotic communication complexity of AVID protocols. However, recent gains in communication complexity have come at the expense of sub-optimal storage,...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/677" class="paperlink" href="/2024/677">2024/677</a> <span class="ms-2"><a href="/2024/677.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-06-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Consensus without Trusted Setup or Public-Key Cryptography</strong> <div class="mt-1"><span class="fst-italic">Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, Victor Shoup</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/653" class="paperlink" href="/2024/653">2024/653</a> <span class="ms-2"><a href="/2024/653.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-09-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Aether: Approaching the Holy Grail in Asynchronous BFT</strong> <div class="mt-1"><span class="fst-italic">Xiaohai Dai, Chaozheng Ding, Hai Jin, Julian Loss, Ling Ren</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">State-of-the-art asynchronous Byzantine Fault Tolerance (BFT) protocols integrate a partially-synchronous optimistic path. The holy grail in this paradigm is to match the performance of a partially-synchronous protocol in favorable situations and match the performance of a purely asynchronous protocol in unfavorable situations. Several prior works have made progress toward this goal by matching the efficiency of a partially-synchronous protocol in favorable conditions. However, their...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/641" class="paperlink" href="/2024/641">2024/641</a> <span class="ms-2"><a href="/2024/641.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon</strong> <div class="mt-1"><span class="fst-italic">Xuanji Meng, Xiao Sui, Zhaoxin Yang, Kang Rong, Wenbo Xu, Shenglong Chen, Ying Yan, Sisi Duan</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present Rondo, a scalable and reconfiguration-friendly distributed randomness beacon (DRB) protocol in the partially synchronous model. Rondo is the first DRB protocol that is built from batched asynchronous verifiable secret sharing (bAVSS) and meanwhile avoids the high $O(n^3)$ message cost, where $n$ is the number of nodes. Our key contribution lies in the introduction of a new variant of bAVSS called batched asynchronous verifiable secret sharing with partial output (bAVSS-PO)....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/614" class="paperlink" href="/2024/614">2024/614</a> <span class="ms-2"><a href="/2024/614.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-12-03</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Non-interactive Blind Signatures: Post-quantum and Stronger Security</strong> <div class="mt-1"><span class="fst-italic">Foteini Baldimtsi, Jiaqi Cheng, Rishab Goyal, Aayush Yadav</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PUBLICKEY">Public-key cryptography</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Incidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver. With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23)...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/571" class="paperlink" href="/2024/571">2024/571</a> <span class="ms-2"><a href="/2024/571.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-04-26</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>MiniCast: Minimizing the Communication Complexity of Reliable Broadcast</strong> <div class="mt-1"><span class="fst-italic">Thomas Locher, Victor Shoup</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We give a new protocol for reliable broadcast with improved communication complexity for long messages. Namely, to reliably broadcast a message a message $m$ over an asynchronous network to a set of $n$ parties, of which fewer than $n/3$ may be corrupt, our protocol achieves a communication complexity of $1.5 |m| n + O( \kappa n^2 \log(n) )$, where $\kappa$ is the output length of a collision-resistant hash function. This result improves on the previously best known bound for long...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/545" class="paperlink" href="/2024/545">2024/545</a> <span class="ms-2"><a href="/2024/545.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-04-08</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Optimal Asynchronous Byzantine Consensus with Fair Separability</strong> <div class="mt-1"><span class="fst-italic">Vincent Gramoli, Zhenliang Lu, Qiang Tang, Pouriya Zarbafian</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Despite ensuring both consistency and liveness, state machine replication protocols remain vulnerable to adversaries who manipulate the transaction order. To address this, researchers have proposed order-fairness techniques that rely either on building dependency graphs between transactions, or on assigning sequence numbers to transactions. Existing protocols that handle dependency graphs suffer from sub-optimal performance, resilience, or security. On the other hand, Pompe (OSDI '20)...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/479" class="paperlink" href="/2024/479">2024/479</a> <span class="ms-2"><a href="/2024/479.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-03-25</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Making Hash-based MVBA Great Again</strong> <div class="mt-1"><span class="fst-italic">Hanwen Feng, Zhenliang Lu, Tiancheng Mai, Qiang Tang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others. Recent efforts (Lu et al, PODC' 20) have pushed the communication complexity of $\mathsf{MVBA}$ to optimal $O(\ell n + \lambda n^2)$, which, however, heavily rely on ``heavyweight'' cryptographic tools,...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/452" class="paperlink" href="/2024/452">2024/452</a> <span class="ms-2"><a href="/2024/452.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-05-13</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Modeling Mobile Crash in Byzantine Consensus</strong> <div class="mt-1"><span class="fst-italic">Hans Schmiedel, Runchao Han, Qiang Tang, Ron Steinfeld, Jiangshan Yu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Targeted Denial-of-Service (DoS) attacks have been a practical concern for permissionless blockchains. Potential solutions, such as random sampling, are adopted by blockchains. However, the associated security guarantees have only been informally discussed in prior work. This is due to the fact that existing adversary models are either not fully capturing this attack or giving up certain design choices (as in the sleepy model or asynchronous network model), or too strong to be...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/432" class="paperlink" href="/2024/432">2024/432</a> <span class="ms-2"><a href="/2024/432.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-03-13</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Perfect Asynchronous MPC with Linear Communication Overhead</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Gilad Asharov, Shravani Patil, Arpita Patra</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We study secure multiparty computation in the asynchronous setting with perfect security and optimal resilience (less than one-fourth of the participants are malicious). It has been shown that every function can be computed in this model [Ben-OR, Canetti, and Goldreich, STOC'1993]. Despite 30 years of research, all protocols in the asynchronous setting require $\Omega(n^2C)$ communication complexity for computing a circuit with $C$ multiplication gates. In contrast, for nearly 15 years, in...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/326" class="paperlink" href="/2024/326">2024/326</a> <span class="ms-2"><a href="/2024/326.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-02-25</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications</strong> <div class="mt-1"><span class="fst-italic">Nicolas Alhaddad, Mayank Varia, Ziling Yang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require confidentiality. ACSS permits a dealer to distribute a secret to a collection of $n$ servers so that everyone holds shares of a polynomial containing the dealer's secret. This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for large...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/317" class="paperlink" href="/2024/317">2024/317</a> <span class="ms-2"><a href="/2024/317.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-05-24</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Closing the Efficiency Gap between Synchronous and Network-Agnostic Consensus</strong> <div class="mt-1"><span class="fst-italic">Giovanni Deligios, Mose Mizrahi Erbes</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In the consensus problem, $n$ parties want to agree on a common value, even if some of them are corrupt and arbitrarily misbehave. If the parties have a common input $m$, then they must agree on $m$. Protocols solving consensus assume either a synchronous communication network, where messages are delivered within a known time, or an asynchronous network with arbitrary delays. Asynchronous protocols only tolerate $t_a < n/3$ corrupt parties. Synchronous ones can tolerate $t_s < n/2$...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/280" class="paperlink" href="/2024/280">2024/280</a> <span class="ms-2"><a href="/2024/280.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures</strong> <div class="mt-1"><span class="fst-italic">Renas Bacho, Julian Loss, Gilad Stern, Benedikt Wagner</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Threshold variants of the Schnorr signature scheme have recently been at the center of attention due to their applications to cryptocurrencies. However, existing constructions for threshold Schnorr signatures among a set of $n$ parties with corruption threshold $t_c$ suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) cubic or higher communication cost to generate a single signature, (iii) strong synchrony assumptions...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/263" class="paperlink" href="/2024/263">2024/263</a> <span class="ms-2"><a href="/2024/263.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-02-16</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Threshold Encryption with Silent Setup</strong> <div class="mt-1"><span class="fst-italic">Sanjam Garg, Dimitris Kolonelos, Guru-Vamsi Policharla, Mingyuan Wang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PUBLICKEY">Public-key cryptography</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We build a concretely efficient threshold encryption scheme where the joint public key of a set of parties is computed as a deterministic function of their locally computed public keys, enabling a silent setup phase. By eliminating interaction from the setup phase, our scheme immediately enjoys several highly desirable features such as asynchronous setup, multiverse support, and dynamic threshold. Prior to our work, the only known constructions of threshold encryption with silent setup...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/245" class="paperlink" href="/2024/245">2024/245</a> <span class="ms-2"><a href="/2024/245.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-07-09</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Linear-Communication Asynchronous Complete Secret Sharing with Optimal Resilience</strong> <div class="mt-1"><span class="fst-italic">Xiaoyu Ji, Junru Li, Yifan Song</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Secure multiparty computation (MPC) allows a set of $n$ parties to jointly compute a function on their private inputs. In this work, we focus on the information-theoretic MPC in the \emph{asynchronous network} setting with optimal resilience ($t<n/3$). The best-known result in this setting is achieved by Choudhury and Patra [J. Cryptol '23], which requires $O(n^4\kappa)$ bits per multiplication gate, where $\kappa$ is the size of a field element. An asynchronous complete secret...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/243" class="paperlink" href="/2024/243">2024/243</a> <span class="ms-2"><a href="/2024/243.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-07-10</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience</strong> <div class="mt-1"><span class="fst-italic">Vipul Goyal, Chen-Da Liu-Zhang, Yifan Song</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Secure multi-party computation (MPC) allows a set of $n$ parties to jointly compute a function over their private inputs. The seminal works of Ben-Or, Canetti and Goldreich [STOC '93] and Ben-Or, Kelmer and Rabin [PODC '94] settled the feasibility of MPC over asynchronous networks. Despite the significant line of work devoted to improving the communication complexity, current protocols with information-theoretic security and optimal resilience $t<n/3$ communicate $\Omega(n^4C)$ field...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/206" class="paperlink" href="/2024/206">2024/206</a> <span class="ms-2"><a href="/2024/206.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-09-24</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Kronos: A Secure and Generic Sharding Blockchain Consensus with Optimized Overhead</strong> <div class="mt-1"><span class="fst-italic">Yizhong Liu, Andi Liu, Yuan Lu, Zhuocheng Pan, Yinuo Li, Jianwei Liu, Song Bian, Mauro Conti</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Sharding enhances blockchain scalability by dividing the network into shards, each managing specific unspent transaction outputs or accounts. As an introduced new transaction type, cross-shard transactions pose a critical challenge to the security and efficiency of sharding blockchains. Currently, there is a lack of a generic sharding blockchain consensus pattern that achieves both security and low overhead. In this paper, we present Kronos, a secure sharding blockchain consensus...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/142" class="paperlink" href="/2024/142">2024/142</a> <span class="ms-2"><a href="/2024/142.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-04-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>GradedDAG: An Asynchronous DAG-based BFT Consensus with Lower Latency</strong> <div class="mt-1"><span class="fst-italic">Xiaohai Dai, Zhaonan Zhang, Jiang Xiao, Jingtao Yue, Xia Xie, Hai Jin</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">To enable parallel processing, the Directed Acyclic Graph (DAG) structure is introduced to the design of asynchronous Byzantine Fault Tolerant (BFT) consensus protocols, known as DAG-based BFT. Existing DAG-based BFT protocols operate in successive waves, with each wave containing three or four Reliable Broadcast (RBC) rounds to broadcast data, resulting in high latency due to the three communication steps required in each RBC. For instance, Tusk, a state-of-the-art DAG-based BFT protocol,...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/134" class="paperlink" href="/2024/134">2024/134</a> <span class="ms-2"><a href="/2024/134.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-12-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Byzantine Fault Tolerance with Non-Determinism, Revisited</strong> <div class="mt-1"><span class="fst-italic">Yue Huang, Huizhong Li, Yi Sun, Sisi Duan</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The conventional Byzantine fault tolerance (BFT) paradigm requires replicated state machines to execute deterministic operations only. In practice, numerous applications and scenarios, especially in the era of blockchains, contain various sources of non-determinism. Despite decades of research on BFT, we still lack an efficient and easy-to-deploy solution for BFT with non-determinism—BFT-ND, especially in the asynchronous setting. We revisit the problem of BFT-ND and provide a formal and...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/132" class="paperlink" href="/2024/132">2024/132</a> <span class="ms-2"><a href="/2024/132.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-01-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>SimpleFT: A Simple Byzantine Fault Tolerant Consensus</strong> <div class="mt-1"><span class="fst-italic">Rui Hao, Chenglong Yi, Weiqi Dai, Zhaonan Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Although having been popular for a long time, Byzantine Fault Tolerance (BFT) consensus under the partially-synchronous network is denounced to be inefficient or even infeasible in recent years, which calls for a more robust asynchronous consensus. On the other hand, almost all the existing asynchronous consensus are too complicated to understand and even suffer from the termination problem. Motivated by the above problems, we propose SimpleFT in this paper, which is a simple asynchronous...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2024/120" class="paperlink" href="/2024/120">2024/120</a> <span class="ms-2"><a href="/2024/120.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-01-29</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures</strong> <div class="mt-1"><span class="fst-italic">Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, Serge Vaudenay</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1903" class="paperlink" href="/2023/1903">2023/1903</a> <span class="ms-2"><a href="/2023/1903.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2025-03-04</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Quarantined-TreeKEM: a Continuous Group Key Agreement for MLS, Secure in Presence of Inactive Users</strong> <div class="mt-1"><span class="fst-italic">Céline Chevalier, Guirec Lebrun, Ange Martinelli, Abdul Rahman Taleb</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The recently standardized secure group messaging protocol Messaging Layer Security (MLS) is designed to ensure asynchronous communications within large groups, with an almost-optimal communication cost and the same security level as point-to-point se- cure messaging protocols such as Signal. In particular, the core sub-protocol of MLS, a Continuous Group Key Agreement (CGKA) called TreeKEM, must generate a common group key that respects the fundamental security properties of post-compromise...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1887" class="paperlink" href="/2023/1887">2023/1887</a> <span class="ms-2"><a href="/2023/1887.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-09-03</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>GRandLine: Adaptively Secure DKG and Randomness Beacon with (Log-)Quadratic Communication Complexity</strong> <div class="mt-1"><span class="fst-italic">Renas Bacho, Christoph Lenzen, Julian Loss, Simon Ochsenreither, Dimitrios Papachristoudis</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1829" class="paperlink" href="/2023/1829">2023/1829</a> <span class="ms-2"><a href="/2023/1829.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-12-01</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>End-to-End Encrypted Zoom Meetings: Proving Security and Strengthening Liveness</strong> <div class="mt-1"><span class="fst-italic">Yevgeniy Dodis, Daniel Jost, Balachandar Kesavan, Antonio Marcedone</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In May 2020, Zoom Video Communications, Inc. (Zoom) announced a multi-step plan to comprehensively support end-to-end encrypted (E2EE) group video calls and subsequently rolled out basic E2EE support to customers in October 2020. In this work we provide the first formal security analysis of Zoom's E2EE protocol, and also lay foundation to the general problem of E2EE group video communication. We observe that the vast security literature analyzing asynchronous messaging does not translate...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1755" class="paperlink" href="/2023/1755">2023/1755</a> <span class="ms-2"><a href="/2023/1755.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-07-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Random Beacons in Monte Carlo: Efficient Asynchronous Random Beacon without Threshold Cryptography</strong> <div class="mt-1"><span class="fst-italic">Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Michael Reiter</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. Numerous applications across the blockchain space have led to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1738" class="paperlink" href="/2023/1738">2023/1738</a> <span class="ms-2"><a href="/2023/1738.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-04-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Byzantine Agreement Decomposed: Honest Majority Asynchronous Atomic Broadcast from Reliable Broadcast</strong> <div class="mt-1"><span class="fst-italic">Simon Holmgaard Kamp, Jesper Buus Nielsen</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1660" class="paperlink" href="/2023/1660">2023/1660</a> <span class="ms-2"><a href="/2023/1660.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-10-27</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>FaBFT: Flexible Asynchronous BFT Protocol Using DAG</strong> <div class="mt-1"><span class="fst-italic">Yu Song, Yu Long, Xian Xu, Dawu Gu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The Byzantine Fault Tolerance (BFT) protocol is a long-standing topic. Recently, a lot of efforts have been made in the research of asynchronous BFT. However, the existing solutions cannot adapt well to the flexible network environment, and suffer from problems such as high communication complexity or long latency. To improve the efficiency of BFT consensus in flexible networks, we propose FaBFT. FaBFT's clients can make their own assumptions about the network conditions, and make the most...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1586" class="paperlink" href="/2023/1586">2023/1586</a> <span class="ms-2"><a href="/2023/1586.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-10-13</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>On the Round Complexity of Asynchronous Crusader Agreement</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Naama Ben-David, Gilad Stern, Sravya Yandamuri</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-FOUNDATIONS">Foundations</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1549" class="paperlink" href="/2023/1549">2023/1549</a> <span class="ms-2"><a href="/2023/1549.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-05-08</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Signature-Free Atomic Broadcast with Optimal $O(n^2)$ Messages and $O(1)$ Expected Time</strong> <div class="mt-1"><span class="fst-italic">Xiao Sui, Xin Wang, Sisi Duan</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Byzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first information-theoretic (IT) and signature-free asynchronous ABC protocol that achieves optimal $O(n^2)$ messages and $O(1)$ expected time. Our ABC protocol adopts a new design, relying on a reduction from---perhaps surprisingly---a somewhat neglected primitive called multivalued Byzantine agreement (MBA).</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1364" class="paperlink" href="/2023/1364">2023/1364</a> <span class="ms-2"><a href="/2023/1364.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-23</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Convex Consensus with Asynchronous Fallback</strong> <div class="mt-1"><span class="fst-italic">Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, Floris Westermann</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Convex Consensus (CC) allows a set of parties to agree on a value $v$ inside the convex hull of their inputs with respect to a predefined abstract convexity notion, even in the presence of byzantine parties. In this work, we focus on achieving CC in the best-of-both-worlds paradigm, i.e., simultaneously tolerating at most $t_s$ corruptions if communication is synchronous, and at most $t_a \leq t_s$ corruptions if it is asynchronous. Our protocol is randomized, which is a requirement under...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1275" class="paperlink" href="/2023/1275">2023/1275</a> <span class="ms-2"><a href="/2023/1275.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-09-23</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Post-Quantum Asynchronous Remote Key Generation for FIDO2 Account Recovery</strong> <div class="mt-1"><span class="fst-italic">Jacqueline Brendel, Sebastian Clermont, Marc Fischlin</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PUBLICKEY">Public-key cryptography</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The Fast IDentity Online (FIDO) Alliance has developed the widely adopted FIDO2 protocol suite that allows for passwordless online authentication. Cryptographic keys stored on a user's device (e.g. their smartphone) are used as credentials to authenticate to services by performing a challenge-response protocol. Yet, this approach leaves users unable to access their accounts in case their authenticator is lost. The device manufacturer Yubico thus proposed a FIDO2-compliant mechanism that...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1196" class="paperlink" href="/2023/1196">2023/1196</a> <span class="ms-2"><a href="/2023/1196.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-10-12</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Verifiable Secret Sharing Simplified</strong> <div class="mt-1"><span class="fst-italic">Sourav Das, Zhuolun Xiang, Alin Tomescu, Alexander Spiegelman, Benny Pinkas, Ling Ren</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Verifiable Secret Sharing (VSS) is a fundamental building block in cryptography. Despite its importance and extensive studies, existing VSS protocols are often complex and inefficient. Many of them do not support dual thresholds, are not publicly verifiable, or do not properly terminate in asynchronous networks. This paper presents a new and simple approach for designing VSS protocols in synchronous and asynchronous networks. Our VSS protocols are optimally fault-tolerant, i.e., they...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1187" class="paperlink" href="/2023/1187">2023/1187</a> <span class="ms-2"><a href="/2023/1187.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-08-03</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Broadcast-Optimal Two Round MPC with Asynchronous Peer-to-Peer Channels</strong> <div class="mt-1"><span class="fst-italic">Ivan Damgård, Divya Ravi, Luisa Siniscalchi, Sophia Yakoubov</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In this paper we continue the study of two-round broadcast-optimal MPC, where broadcast is used in one of the two rounds, but not in both. We consider the realistic scenario where the round that does not use broadcast is asynchronous. Since a first asynchronous round (even when followed by a round of broadcast) does not admit any secure computation, we introduce a new notion of asynchrony which we call $(t_d, t_m)$-asynchrony. In this new notion of asynchrony, an adversary can delay or...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1175" class="paperlink" href="/2023/1175">2023/1175</a> <span class="ms-2"><a href="/2023/1175.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-12-13</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Fast batched asynchronous distributed key generation</strong> <div class="mt-1"><span class="fst-italic">Jens Groth, Victor Shoup</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present new protocols for threshold Schnorr signatures that work in an asynchronous communication setting, providing robustness and optimal resilience. These protocols provide unprecedented performance in terms of communication and computational complexity. In terms of communication complexity, for each signature, a single party must transmit a few dozen group elements and scalars across the network (independent of the size of the signing committee). In terms of computational...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1164" class="paperlink" href="/2023/1164">2023/1164</a> <span class="ms-2"><a href="/2023/1164.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-11-04</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Swiper: a new paradigm for efficient weighted distributed protocols</strong> <div class="mt-1"><span class="fst-italic">Andrei Tonkikh, Luciano Freitas</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The majority of fault-tolerant distributed algorithms are designed assuming a nominal corruption model, in which at most a fraction $f_n$ of parties can be corrupted by the adversary. However, due to the infamous Sybil attack, nominal models are not sufficient to express the trust assumptions in open (i.e., permissionless) settings. Instead, permissionless systems typically operate in a weighted model, where each participant is associated with a weight and the adversary can corrupt a set of...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1130" class="paperlink" href="/2023/1130">2023/1130</a> <span class="ms-2"><a href="/2023/1130.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-12-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Agreement on a Core Set in Constant Expected Time and More Efficient Asynchronous VSS and MPC</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Gilad Asharov, Arpita Patra, Gilad Stern</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">A major challenge of any asynchronous MPC protocol is the need to reach an agreement on the set of private inputs to be used as input for the MPC functionality. Ben-Or, Canetti and Goldreich [STOC 93] call this problem Agreement on a Core Set (ACS) and solve it by running $n$ parallel instances of asynchronous binary Byzantine agreements. To the best of our knowledge, all results in the perfect and statistical security setting used this same paradigm for solving ACS. Using all known...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1123" class="paperlink" href="/2023/1123">2023/1123</a> <span class="ms-2"><a href="/2023/1123.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-12-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>On the Cost of Post-Compromise Security in Concurrent Continuous Group-Key Agreement</strong> <div class="mt-1"><span class="fst-italic">Benedikt Auerbach, Miguel Cueto Noval, Guillermo Pascual-Perez, Krzysztof Pietrzak</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1103" class="paperlink" href="/2023/1103">2023/1103</a> <span class="ms-2"><a href="/2023/1103.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-07-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Large-Scale Proof-of-Stake Asynchronous Total-Order Broadcast</strong> <div class="mt-1"><span class="fst-italic">Orestis Alpos, Christian Cachin, Simon Holmgaard Kamp, Jesper Buus Nielsen</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present simple and practical protocols for generating randomness as used by asynchronous total-order broadcast. The protocols are secure in a proof-of-stake setting with dynamically changing stake. They can be plugged into existing protocols for asynchronous total-order broadcast and will turn these into asynchronous total-order broadcast with dynamic stake. Our contribution relies on two important techniques. The paper ``Random Oracles in Constantinople: Practical Asynchronous Byzantine...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1053" class="paperlink" href="/2023/1053">2023/1053</a> <span class="ms-2"><a href="/2023/1053.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-09-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>ASMesh: Anonymous and Secure Messaging in Mesh Networks Using Stronger, Anonymous Double Ratchet</strong> <div class="mt-1"><span class="fst-italic">Alexander Bienstock, Paul Rösler, Yi Tang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1022" class="paperlink" href="/2023/1022">2023/1022</a> <span class="ms-2"><a href="/2023/1022.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-11-13</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Zombie: Middleboxes that Don’t Snoop</strong> <div class="mt-1"><span class="fst-italic">Collin Zhang, Zachary DeStefano, Arasu Arun, Joseph Bonneau, Paul Grubbs, Michael Walfish</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Zero-knowledge middleboxes (ZKMBs) are a recent paradigm in which clients get privacy while middleboxes enforce policy: clients prove in zero knowledge that the plaintext underlying their encrypted traffic complies with network policies, such as DNS filtering. However, prior work had impractically poor performance and was limited in functionality. This work presents Zombie, the first system built using the ZKMB paradigm. Zombie introduces techniques that push ZKMBs to the verge of...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/1003" class="paperlink" href="/2023/1003">2023/1003</a> <span class="ms-2"><a href="/2023/1003.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-12-22</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Concurrent Asynchronous Byzantine Agreement in Expected-Constant Rounds, Revisited</strong> <div class="mt-1"><span class="fst-italic">Ran Cohen, Pouyan Forghani, Juan Garay, Rutvik Patel, Vassilis Zikas</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">It is well known that without randomization, Byzantine agreement (BA) requires a linear number of rounds in the synchronous setting, while it is flat out impossible in the asynchronous setting. The primitive which allows to bypass the above limitation is known as oblivious common coin (OCC). It allows parties to agree with constant probability on a random coin, where agreement is oblivious, i.e., players are not aware whether or not agreement has been achieved. The starting point of our...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/820" class="paperlink" href="/2023/820">2023/820</a> <span class="ms-2"><a href="/2023/820.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-06-02</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Network Agnostic MPC with Statistical Security</strong> <div class="mt-1"><span class="fst-italic">Ananya Appan, Ashish Choudhury</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">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...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/689" class="paperlink" href="/2023/689">2023/689</a> <span class="ms-2"><a href="/2023/689.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-11-26</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Abraxas: Throughput-Efficient Hybrid Asynchronous Consensus</strong> <div class="mt-1"><span class="fst-italic">Erica Blum, Jonathan Katz, Julian Loss, Kartik Nayak, Simon Ochsenreither</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Protocols for state-machine replication (SMR) often trade off performance for resilience to network delay. In particular, protocols for asynchronous SMR tolerate arbitrary network delay but sacrifice throughput/latency when the network is fast, while partially synchronous protocols have good performance in a fast network but fail to make progress if the network experiences high delay. Existing hybrid protocols are resilient to arbitrary network delay and have good performance when the...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/679" class="paperlink" href="/2023/679">2023/679</a> <span class="ms-2"><a href="/2023/679.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-01-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic Path</strong> <div class="mt-1"><span class="fst-italic">Xiaohai Dai, Bolin Zhang, Hai Jin, Ling Ren</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">To reduce latency and communication overhead of asynchronous Byzantine Fault Tolerance (BFT) consensus, an optimistic path is often added, with Ditto and BDT as state-of-the-art representatives. These protocols first attempt to run an optimistic path that is typically adapted from partially-synchronous BFT and promises good performance in good situations. If the optimistic path fails to make progress, these protocols switch to a pessimistic path after a timeout, to guarantee liveness in an...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/536" class="paperlink" href="/2023/536">2023/536</a> <span class="ms-2"><a href="/2023/536.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-03-07</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience</strong> <div class="mt-1"><span class="fst-italic">Victor Shoup, Nigel P. Smart</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present new protocols for *Asynchronous Verifiable Secret Sharing* for Shamir (i.e., threshold $t<n$) sharing of secrets. Our protocols: * Use only "lightweight" cryptographic primitives, such as hash functions; * Can share secrets over rings such as $\mathbb{Z}_{p^k}$ as well as finite fields $\mathbb{F}_q$; * Provide *optimal resilience*, in the sense that they tolerate up to $t < n/3$ corruptions, where $n$ is the total number of parties; * Are *complete*, in the sense that they...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/456" class="paperlink" href="/2023/456">2023/456</a> <span class="ms-2"><a href="/2023/456.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-03-29</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Generalised Asynchronous Remote Key Generation for Pairing-based Cryptosystems</strong> <div class="mt-1"><span class="fst-italic">Nick Frymann, Daniel Gardham, Mark Manulis, Hugo Nartz</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous Remote Key Generation (ARKG, introduced in ACM CCS 2020) allows for a party to create public keys for which corresponding private keys may be later computed by another intended party only. ARKG can be composed with standard public-key cryptosystems and has been used to construct a new class of privacy-preserving proxy signatures. The original construction of ARKG, however, generates discrete logarithm key pairs of the form $(x, g^x)$. In this paper we define a generic...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/449" class="paperlink" href="/2023/449">2023/449</a> <span class="ms-2"><a href="/2023/449.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-03-27</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Multidimensional Approximate Agreement with Asynchronous Fallback</strong> <div class="mt-1"><span class="fst-italic">Diana Ghinea, Chen-Da Liu-Zhang, Roger Wattenhofer</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in $\mathbb{R}^D$ as input. The honest parties are required to obtain very close outputs in $\mathbb{R}^D$ that lie inside the convex hull of their inputs. Existing Multidimensional Approximate Agreement protocols achieve resilience against $t_s < n / (D + 1)$ corruptions under a synchronous network where messages are delivered within some time $\Delta$, but become completely...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/427" class="paperlink" href="/2023/427">2023/427</a> <span class="ms-2"><a href="/2023/427.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-06-02</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>SPRINT: High-Throughput Robust Distributed Schnorr Signatures</strong> <div class="mt-1"><span class="fst-italic">Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk, Yiping Ma, Tal Rabin</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/419" class="paperlink" href="/2023/419">2023/419</a> <span class="ms-2"><a href="/2023/419.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-03-31</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Remote Key Generation for Post-Quantum Cryptosystems from Lattices</strong> <div class="mt-1"><span class="fst-italic">Nick Frymann, Daniel Gardham, Mark Manulis</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous Remote Key Generation (ARKG), introduced by Frymann et al. at CCS 2020, allows for the generation of unlinkable public keys by third parties, for which corresponding private keys may be later learned only by the key pair's legitimate owner. These key pairs can then be used in common public-key cryptosystems, including signatures, PKE, KEMs, and schemes supporting delegation, such as proxy signatures. The only known instance of ARKG generates discrete-log-based keys. In this...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/394" class="paperlink" href="/2023/394">2023/394</a> <span class="ms-2"><a href="/2023/394.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-02-22</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Fork-Resilient Continuous Group Key Agreement</strong> <div class="mt-1"><span class="fst-italic">Joël Alwen, Marta Mularczyk, Yiannis Tselekounis</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Continuous Group Key Agreement (CGKA) lets a evolving group of clients agree on a sequence of group keys. An important application of CGKA is scalable asynchronous end-to-end (E2E) encrypted group messaging. A major problem preventing the use of CGKA over unreliable infrastructure are so-called forks. A fork occurs when group members have diverging views of the group's history (and thus its current state); e.g. due to network or server failures. Once communication channels are restored,...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/192" class="paperlink" href="/2023/192">2023/192</a> <span class="ms-2"><a href="/2023/192.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-08-07</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Faithful Simulation of Randomized BFT Protocols on Block DAGs</strong> <div class="mt-1"><span class="fst-italic">Hagit Attiya, Constantin Enea, Shafik Nassar</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Byzantine Fault-Tolerant (BFT) protocols that are based on Directed Acyclic Graphs (DAGs) are attractive due to their many advantages in asynchronous blockchain systems. These DAG-based protocols can be viewed as a simulation of some BFT protocol on a DAG. Many DAG-based BFT protocols rely on randomization, since they are used for agreement and ordering of transactions, which cannot be achieved deterministically in asynchronous systems. Randomization is achieved either through local sources...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/154" class="paperlink" href="/2023/154">2023/154</a> <span class="ms-2"><a href="/2023/154.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-07-11</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>FIN: Practical Signature-Free Asynchronous Common Subset in Constant Time</strong> <div class="mt-1"><span class="fst-italic">Sisi Duan, Xin Wang, Haibin Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous common subset (ACS) is a powerful paradigm enabling applications such as Byzantine fault-tolerance (BFT) and multi-party computation (MPC). The most efficient ACS framework in the information-theoretic setting is due to Ben-Or, Kelmer, and Rabin (BKR, 1994). The BKR ACS protocol has been both theoretically and practically impactful. However, the BKR protocol has an $O(\log n)$ running time (where $n$ is the number of replicas) due to the usage of $n$ parallel asynchronous...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/113" class="paperlink" href="/2023/113">2023/113</a> <span class="ms-2"><a href="/2023/113.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-01-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Homomorphic Sortition – Single Secret Leader Election for PoS Blockchains</strong> <div class="mt-1"><span class="fst-italic">Luciano Freitas, Andrei Tonkikh, Adda-Akram Bendoukha, Sara Tucci-Piergiovanni, Renaud Sirdey, Oana Stan, Petr Kuznetsov</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">In a single secret leader election protocol (SSLE), one of the system participants is chosen and, unless it decides to reveal itself, no other participant can identify it. SSLE has a great potential in protecting blockchain consensus protocols against denial of service (DoS) attacks. However, all existing solutions either make strong synchrony assumptions or have expiring registration, meaning that they require elected processes to re-register themselves before they can be re-elected...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2023/063" class="paperlink" href="/2023/063">2023/063</a> <span class="ms-2"><a href="/2023/063.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-01-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Threshold Signatures in the Multiverse</strong> <div class="mt-1"><span class="fst-italic">Leemon Baird, Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, Yinuo Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes....</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1778" class="paperlink" href="/2022/1778">2022/1778</a> <span class="ms-2"><a href="/2022/1778.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2022-12-30</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Delegated Private Set Intersection with Hiding of Intersection Size</strong> <div class="mt-1"><span class="fst-italic">Wyatt Howe, Andrei Lapets, Frederick Jansen, Tanner Braun, Ben Getchell</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Integrating private set intersection (PSI) protocols within real-world data workflows, software applications, or web services can be challenging. This can occur because data contributors and result recipients do not have the technical expertise, information technology infrastructure, or other resources to participate throughout the execution of a protocol and/or to incur all the communication costs associated with participation. Furthermore, contemporary workflows, applications, and services...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1759" class="paperlink" href="/2022/1759">2022/1759</a> <span class="ms-2"><a href="/2022/1759.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-06-08</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Bingo: Adaptivity and Asynchrony in Verifiable Secret Sharing and Distributed Key Generation</strong> <div class="mt-1"><span class="fst-italic">Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets with a total communication complexity of $O(\lambda n^2)$ words, where $\lambda$ is the security parameter and $n$ is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time, which we in...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1732" class="paperlink" href="/2022/1732">2022/1732</a> <span class="ms-2"><a href="/2022/1732.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-04-18</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>TreeSync: Authenticated Group Management for Messaging Layer Security</strong> <div class="mt-1"><span class="fst-italic">Théophile Wallez, Jonathan Protzenko, Benjamin Beurdouche, Karthikeyan Bhargavan</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Messaging Layer Security (MLS), currently undergoing standardization at the IETF, is an asynchronous group messaging protocol that aims to be efficient for large dynamic groups, while providing strong guarantees like forward secrecy (FS) and post-compromise security (PCS). While prior work on MLS has extensively studied its group key establishment component (called TreeKEM), many flaws in early designs of MLS have stemmed from its group integrity and authentication mechanisms that are not as...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1709" class="paperlink" href="/2022/1709">2022/1709</a> <span class="ms-2"><a href="/2022/1709.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-12-20</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Dory: Faster Asynchronous BFT with Reduced Communication for Permissioned Blockchains</strong> <div class="mt-1"><span class="fst-italic">Zongyang Zhang, You Zhou, Sisi Duan, Haibin Zhang, Bin Hu, Licheng Wang, Jianwei Liu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Asynchronous Byzantine fault-tolerance (BFT) protocols (e.g., HoneyBadger and Dumbo family protocols) have received increasing attention as the consensus mechanism of permissioned blockchains, given their particular robustness against timing and performance attacks. However, there is a substantial performance gap before they can be applied in real systems. In this paper, we identify and address two critical issues, and design Dory, an asynchronous BFT consensus protocol with improved...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1683" class="paperlink" href="/2022/1683">2022/1683</a> <span class="ms-2"><a href="/2022/1683.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2024-01-23</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Powers of Tau in Asynchrony</strong> <div class="mt-1"><span class="fst-italic">Sourav Das, Zhuolun Xiang, Ling Ren</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">The $q$-Strong Diffie-Hellman ($q$-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive arguments of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon. The only existing method to generate these parameters securely is highly sequential, requires synchrony assumptions, and has very high communication and computation costs. For example, to generate parameters for any...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1678" class="paperlink" href="/2022/1678">2022/1678</a> <span class="ms-2"><a href="/2022/1678.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-07-11</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Asynchronous Distributed Key Generation: Improved Efficiency, Weaker Assumption, and Standard Model</strong> <div class="mt-1"><span class="fst-italic">Haibin Zhang, Sisi Duan, Chao Liu, Boxin Zhao, Xuanji Meng, Shengli Liu, Yong Yu, Fangguo Zhang, Liehuang Zhu</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1586" class="paperlink" href="/2022/1586">2022/1586</a> <span class="ms-2"><a href="/2022/1586.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2022-11-15</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Asynchronous Proactive Secret Sharing and Key Refresh</strong> <div class="mt-1"><span class="fst-italic">Christoph U. Günther, Sourav Das, Lefteris Kokoris-Kogias</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">With the emergence of decentralized systems, spearheaded by blockchains, threshold cryptography has seen unprecedented adoption. Just recently, the trustless distribution of threshold keys over an unreliable network has started to become practical. The next logical step is ensuring the security of these keys against persistent adversaries attacking the system over long periods of time. In this work, we tackle this problem and give two practical constructions for Asynchronous Proactive...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1583" class="paperlink" href="/2022/1583">2022/1583</a> <span class="ms-2"><a href="/2022/1583.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2022-11-14</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Asynchronous Multi-Party Quantum Computation</strong> <div class="mt-1"><span class="fst-italic">Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, João Ribeiro</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Multi-party quantum computation (MPQC) allows a set of parties to securely compute a quantum circuit over private quantum data. Current MPQC protocols rely on the fact that the network is synchronous, i.e., messages sent are guaranteed to be delivered within a known fixed delay upper bound, and unfortunately completely break down even when only a single message arrives late. Motivated by real-world networks, the seminal work of Ben-Or, Canetti and Goldreich (STOC'93) initiated the study...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1544" class="paperlink" href="/2022/1544">2022/1544</a> <span class="ms-2"><a href="/2022/1544.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2022-11-07</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Towards Efficient Decentralized Federated Learning</strong> <div class="mt-1"><span class="fst-italic">Christodoulos Pappas, Dimitrios Papadopoulos, Dimitris Chatzopoulos, Eleni Panagou, Spyros Lalis, Manolis Vavalis</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-APPLICATIONS">Applications</small> </div> </div> <p class="mb-0 mt-1 search-abstract">We focus on the problem of efficiently deploying a federated learning training task in a decentralized setting with multiple aggregators. To that end, we introduce a number of improvements and modifications to the recently proposed IPLS protocol. In particular, we relax its assumption for direct communication across participants, using instead indirect communication over a decentralized storage system, effectively turning it into a partially asynchronous protocol. Moreover, we secure it...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1533" class="paperlink" href="/2022/1533">2022/1533</a> <span class="ms-2"><a href="/2022/1533.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2022-11-05</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum</strong> <div class="mt-1"><span class="fst-italic">Keitaro Hashimoto, Shuichi Katsumata, Thomas Prest</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1397" class="paperlink" href="/2022/1397">2022/1397</a> <span class="ms-2"><a href="/2022/1397.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-10-09</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees</strong> <div class="mt-1"><span class="fst-italic">Giovanni Deligios, Chen-Da Liu-Zhang</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary. Perfectly-secure SMT protocols in synchronous and asynchronous networks are resilient up to $\ell/2$ and $\ell/3$ corruptions respectively. In this work, we ask whether it is...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1389" class="paperlink" href="/2022/1389">2022/1389</a> <span class="ms-2"><a href="/2022/1389.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-04-24</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Practical Asynchronous High-threshold Distributed Key Generation and Distributed Polynomial Sampling</strong> <div class="mt-1"><span class="fst-italic">Sourav Das, Zhuolun Xiang, Lefteris Kokoris-Kogias, Ling Ren</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple...</p> </div> </div> <div class="mb-4"> <div class="d-flex"><a title="2022/1369" class="paperlink" href="/2022/1369">2022/1369</a> <span class="ms-2"><a href="/2022/1369.pdf">(PDF)</a></span> <small class="ms-auto">Last updated: 2023-09-26</small> </div> <div class="ms-md-4"> <div class="d-flex flex-column flex-md-row justify-content-between"> <div> <strong>Network-Agnostic Security Comes (Almost) for Free in DKG and MPC</strong> <div class="mt-1"><span class="fst-italic">Renas Bacho, Daniel Collins, Chen-Da Liu-Zhang, Julian Loss</span></div> </div> <div class="float-end mt-1 ms-md-3"> <small class="badge category category-PROTOCOLS">Cryptographic protocols</small> </div> </div> <p class="mb-0 mt-1 search-abstract">Distributed key generation (DKG) protocols are an essential building block for threshold cryptosystems. Many DKG protocols tolerate up to $t_s<n/2$ corruptions assuming a well-behaved synchronous network, but become insecure as soon as the network delay becomes unstable. On the other hand, solutions in the asynchronous model operate under arbitrary network conditions, but only tolerate $t_a<n/3$ corruptions, even when the network is well-behaved. In this work, we ask whether one can...</p> </div> </div> <div class="w-75 mx-auto"> <ul class="pagination mt-5 mb-5"> <li class="page-item active"><span class="page-link">1</span></li> <li class="page-item"><a rel="nofollow" class="page-link" href="/search?q=asynchronous&offset=100">2</a></li> <li class="page-item"><a rel="nofollow" class="page-link" href="/search?q=asynchronous&offset=200">3</a></li> <li class="page-item"> <a rel="nofollow" class="page-link" href="/search?q=asynchronous&offset=100">Next »</a> </li> </ul> </div> </div> </div> </div> <script> document.getElementById('clearButton').addEventListener('click', function(ev) { document.querySelectorAll('input').forEach(el => { el.value = ''; }); document.getElementById('category').selectedIndex = "0"; }); function validateForm() { // check that dates are compatible. let submittedAfter = document.getElementById('submittedafter'); let submittedBefore = document.getElementById('submittedbefore'); let revisedAfter = document.getElementById('revisedafter'); let revisedBefore = document.getElementById('revisedbefore'); if (submittedAfter.value && submittedBefore.value && submittedAfter.value > submittedBefore.value) { submittedAfter.classList.add('is-invalid'); submittedBefore.classList.add('is-invalid'); return false; } if (revisedAfter.value && revisedBefore.value && revisedAfter.value > revisedBefore.value) { revisedAfter.classList.add('is-invalid'); revisedBefore.classList.add('is-invalid'); return false; } if (revisedBefore.value && submittedAfter.value && revisedBefore.value < submittedAfter.value) { revisedBefore.classList.add('is-invalid'); submittedAfter.classList.add('is-invalid'); return false; } return true; } </script> <script src="/js/mark.min.js"></script> <script> var instance = new Mark("div.results"); let urlParams = new URLSearchParams(window.location.search); if (urlParams.get('q')) { instance.mark(urlParams.get('q')); } if (urlParams.get('title')) { instance.mark(urlParams.get('title')); } if (urlParams.get('authors')) { instance.mark(urlParams.get('authors')); } </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>

CINXE.COM

Search results