Paper 2022/971

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

Thomas Yurek, University of Illinois Urbana-Champaign, NTT (Japan)
Zhuolun Xiang, Carnegie Mellon University
Yu Xia, Massachusetts Institute of Technology, NTT (Japan)
Andrew Miller

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.

Available format(s)
Cryptographic protocols
Publication info
verifiable secret sharing multiparty computation proactive secret sharing asynchronous VSS AVSS ACSS DPSS
Contact author(s)
yurek2 @ illinois edu
zhuolunx @ andrew cmu edu
yuxia @ mit edu
soc1024 @ illinois edu
2022-07-29: approved
2022-07-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Yurek and Zhuolun Xiang and Yu Xia and Andrew Miller},
      title = {Long Live The Honey Badger: Robust Asynchronous DPSS and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/971},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.