Evolving Secret Sharing: Dynamic Thresholds and Robustness
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
- PDF / 265,809 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 218 Views
2
Cornell Tech, New York, USA [email protected] Department of Computer Science, Ariel University, Ariel, Israel [email protected]
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(t4 · 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.
1
Introduction
Secret sharing schemes, introduced by Shamir [17] and Blakley [5], are methods that enable a dealer, that holds a secret piece of information, to distribute this secret among n parties such that predefined qualified subsets can reconstruct the secret, while others learn nothing about it. The monotone collection of qualified subsets is known as an access structure. Secret sharing schemes are a basic primitive and have found numerous applications in cryptography and distributed computing; see the extensive survey of Beimel [2] and the book of Cramer et al. [9]. Any access structure admits a secret sharing scheme but the share size could be as large as O(2n ), the maximal number of possible qualified sets [12]. This paper incorporates the manuscript of Paskin-Cherniavsky [15]. I. Komargodski—Supported in part by Elaine Shi’s Packard Foundation Fellowship. Part of this work done while being a Ph.D student at the Weizmann Institute of Science, supported in part by grants from the Israel Science Foundation and by a Levzion Fellowship. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 379–393, 2017. https://doi.org/10.1007/978-3-319-70503-3_12
380
I. Komargodski and A. Paskin-Cherniavsky
A significant goal in secret sharing is thus to minimize the share size, namely, the amount of information distributed to the parties.1 Almost all known secret sharing schemes assume that the number of parties n and the access structure are known in advance. However, in many scenarios these assumptions have a cost: First, the eventual set might turn out to be much smaller than n. Second, the access structure may change with time, forcing the dealer to re-shar
Data Loading...
