CHURP: Dynamic-Committee Proactive Secret Sharing

Sai Krishna Deepak Maram; Fan Zhang; Lun Wang; Andrew Low; Yupeng Zhang; Ari Juels; Dawn Song

Paper 2019/017

CHURP: Dynamic-Committee Proactive Secret Sharing

Sai Krishna Deepak Maram, Fan Zhang, Lun Wang, Andrew Low, Yupeng Zhang, Ari Juels, and Dawn Song

Abstract

We introduce CHURP (CHUrn-Robust Proactive secret sharing). CHURP enables secure secret-sharing in dynamic settings, where the committee of nodes storing a secret changes over time. Designed for blockchains, CHURP has lower communication complexity than previous schemes: $O (n)$ on-chain and $O (n^{2})$ off-chain in the optimistic case of no node failures. CHURP includes several technical innovations: An efficient new proactivization scheme of independent interest, a technique (using asymmetric bivariate polynomials) for efficiently changing secret-sharing thresholds, and a hedge against setup failures in an efficient polynomial commitment scheme. We also introduce a general new technique for inexpensive off-chain communication across the peer-to-peer networks of permissionless blockchains. We formally prove the security of CHURP, report on an implementation, and present performance measurements.

Note: Final CCS version, minor error fixes.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. ACM CCS'19
DOI: 10.1145/3319535.3363203
Keywords: secret sharing threshold cryptography blockchains
Contact author(s): sm2686 @ cornell edu
History: 2019-10-02: last of 5 revisions; 2019-01-09: received; See all versions
Short URL: https://ia.cr/2019/017
License: CC BY

BibTeX

@misc{cryptoeprint:2019/017,
      author = {Sai Krishna Deepak Maram and Fan Zhang and Lun Wang and Andrew Low and Yupeng Zhang and Ari Juels and Dawn Song},
      title = {{CHURP}: Dynamic-Committee Proactive Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/017},
      year = {2019},
      doi = {10.1145/3319535.3363203},
      url = {https://eprint.iacr.org/2019/017}
}