Threshold Secret Sharing Requires a Linear Size Alphabet
We prove that for every n and \(1< t < n\) any t-out-of-n threshold secret sharing scheme for one-bit secrets requires share size \(\log (t + 1)\) . Our bound is tight when \(t = n - 1\) and n is a prime power. In 1990 Kilian and Nisan proved the in
- PDF / 268,407 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 10 Downloads / 197 Views
Chinese University of Hong Kong, Hong Kong, China [email protected] 2 New York University, New York, USA [email protected] 3 Weizmann Institute of Science, Rehovot, Israel [email protected]
Abstract. We prove that for every n and 1 < t < n any t-out-of-n threshold secret sharing scheme for one-bit secrets requires share size log(t + 1). Our bound is tight when t = n − 1 and n is a prime power. In 1990 Kilian and Nisan proved the incomparable bound log(n − t + 2). Taken together, the two bounds imply that the share size of Shamir’s secret sharing scheme (Comm. ACM ’79) is optimal up to an additive constant even for one-bit secrets for the whole range of parameters 1 < t < n. More generally, we show that for all 1 < s < r < n, any ramp secret sharing scheme with secrecy threshold s and reconstruction threshold r requires share size log((r + 1)/(r − s)). As part of our analysis we formulate a simple game-theoretic relaxation of secret sharing for arbitrary access structures. We prove the optimality of our analysis for threshold secret sharing with respect to this method and point out a general limitation.
1
Introduction
In 1979, Shamir [30] and Blakley [11] presented a method for sharing a piece of secret information among n parties such that any 1 < t < n parties can recover the secret while any t − 1 parties learn nothing about the secret. These methods are called (t, n)-threshold secret sharing schemes. This sharp threshold between secrecy and reconstruction is fundamental in applications where a group of mutually suspicious individuals with conflicting interests must cooperate. Indeed, threshold secret sharing schemes have found many applications in A. Bogdanov—Supported by RGC GRF grants CUHK410113 and CUHK14208215. S. Guo—Part of the work done in the Chinese University of Hong Kong supported by RGC GRF grants CUHK410112 and CUHK410113. I. Komargodski—Part of this work done while visiting CUHK, supported by RGC GRF grant CUHK410113. Supported in part by a Levzion fellowship, by a grant from the I-CORE Program of the Planning and Budgeting Committee, the Israel Science Foundation, BSF and the Israeli Ministry of Science and Technology. c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part II, LNCS 9986, pp. 471–484, 2016. DOI: 10.1007/978-3-662-53644-5 18
472
A. Bogdanov et al.
cryptography and distributed computing; see the extensive survey of Beimel [3] and the recent book of Cramer et al. [17]. Threshold secret sharing was generalized by Ito et al. [23] to allow more general structures of subsets to learn the secret, while keeping the secret perfectly hidden from all other subsets. The collection of qualified subsets is called an access structure. A significant goal in secret sharing is to minimize the share size, namely, the amount of information distributed to the parties. Despite the long history of the subject, there are significant gaps between lower and upper bounds both for general access structures and for the special case of th
Data Loading...
