Long Live The Honey Badger: Robust Asynchronous DPSS and its Applications


Thomas Yurek, University of Illinois at Urbana-Champaign, NTT Research, and IC3; Zhuolun Xiang, Aptos; Yu Xia, MIT CSAIL and NTT Research; Andrew Miller, University of Illinois at Urbana-Champaign and IC3


Secret sharing is an essential tool for many distributed applications, including distributed key generation and multiparty computation. For many practical applications, we would like to tolerate network churn, meaning participants can dynamically enter and leave the pool of protocol participants as they please. Such protocols, called Dynamic-committee Proactive Secret Sharing (DPSS) have recently been studied; however, existing DPSS protocols do not gracefully handle faults: the presence of even one unexpectedly slow node can often slow down the whole protocol by a factor of O(n).

In this work, we explore optimally fault-tolerant asynchronous DPSS that is not slowed down by crash faults and even handles byzantine faults while maintaining the same performance. We first introduce the first high-threshold DPSS, which offers favorable characteristics relative to prior non-synchronous works in the presence of faults while simultaneously supporting higher privacy thresholds. We then batch-amortize this scheme along with a parallel non-high-threshold scheme which achieves optimal bandwidth characteristics. We implement our schemes and demonstrate that they can compete with prior work in best-case performance while outperforming it in non-optimal settings.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {287160,
author = {Thomas Yurek and Zhuolun Xiang and Yu Xia and Andrew Miller},
title = {Long Live The Honey Badger: Robust Asynchronous {DPSS} and its Applications},
booktitle = {32nd USENIX Security Symposium (USENIX Security 23)},
year = {2023},
isbn = {978-1-939133-37-3},
address = {Anaheim, CA},
pages = {5413--5430},
url = {https://www.usenix.org/conference/usenixsecurity23/presentation/yurek},
publisher = {USENIX Association},
month = aug

Presentation Video