Paper 2017/948

Evolving Secret Sharing: Dynamic Thresholds and Robustness

Ilan Komargodski and Anat Paskin-Cherniavsky

Abstract

Threshold secret sharing schemes enable a dealer to share a secret among $n$ parties such that only subsets of parties of cardinality at least $k = k(n)$ can reconstruct the secret. Komargodski, Naor and Yogev (TCC 2016-B) proposed an efficient scheme for sharing a secret among an unbounded number of parties such that only subsets of $k$ parties can recover the secret, where $k$ is any fixed constant. This access structure is known as $k$-threshold. They left open the possibility of an efficient scheme for the dynamic threshold access structure, in which the qualified sets are of increasing size as the number of parties increases. We resolve this open problem and present a construction in which the share size of the $t$-th party is $O(t^4\cdot \log t)$ bits. Furthermore, we show how to generically translate any scheme for $k$-threshold into a scheme which is robust, where a shared secret can be recovered even if some parties hand-in incorrect shares. This answers another open problem of Komargodski et al. Our construction is based on the construction of robust (classical) secret sharing schemes of Cramer et al. (EUROCRYPT 2008) using algebraic manipulation detection codes.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2017
Keywords
secret sharingevolving access structurerobustnessthreshold secret sharingAMD codes
Contact author(s)
komargodski @ cornell edu
History
2017-09-27: revised
2017-09-27: received
See all versions
Short URL
https://ia.cr/2017/948
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/948,
      author = {Ilan Komargodski and Anat Paskin-Cherniavsky},
      title = {Evolving Secret Sharing: Dynamic Thresholds and Robustness},
      howpublished = {Cryptology ePrint Archive, Paper 2017/948},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/948}},
      url = {https://eprint.iacr.org/2017/948}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.