Matroids Can Be Far from Ideal Secret Sharing
In a secret-sharing scheme, a secret value is distributed among a set of parties by giving each party a share. The requirement is that only predefined subsets of parties can recover the secret from their shares. The family of the predefined authorized sub
- PDF / 570,875 Bytes
- 19 Pages / 430 x 660 pts Page_size
- 100 Downloads / 177 Views
Dept. of Computer Science Ben-Gurion University Beer-Sheva, Israel [email protected] 2 Weizmann Institute of Science Rehovot, Israel [email protected] 3 Dept. of Applied Mathematics 4 Universitat Polit`ecnica de Catalunya Barcelona, Spain [email protected]
Abstract. In a secret-sharing scheme, a secret value is distributed among a set of parties by giving each party a share. The requirement is that only predefined subsets of parties can recover the secret from their shares. The family of the predefined authorized subsets is called the access structure. An access structure is ideal if there exists a secret-sharing scheme realizing it in which the shares have optimal length, that is, in which the shares are taken from the same domain as the secrets. Brickell and Davenport (J. of Cryptology, 1991) proved that ideal access structures are induced by matroids. Subsequently, ideal access structures and access structures induced by matroids have received a lot of attention. Seymour (J. of Combinatorial Theory, 1992) gave the first example of an access structure induced by a matroid, namely the Vamos matroid, that is non-ideal. Beimel and Livne (TCC 2006) presented the first non-trivial lower bounds on the size of the domain of the shares for secret-sharing schemes realizing an access structure induced by the Vamos matroid. In this work, we substantially improve those bounds by proving that the size of the domain of the shares in every secret-sharing scheme for those access structures is at least k1.1 √ , where k is the size of the domain of the secrets (compared to k + Ω( k) in previous works). Our bounds are obtained by using non-Shannon inequalities for the entropy function. The importance of our results are: (1) we present the first proof that there exists an access structure induced by a matroid which is not nearly ideal, and (2) we present the first proof that there is an access structure whose information rate is strictly between 2/3 and 1. In addition, we present a better lower bound that applies only to linear secret-sharing schemes realizing the access structures induced by the Vamos matroid.
Partially supported by the Frankel Center for Computer Science at the Ben-Gurion University. Partially supported by the Israel Science Foundation (grant No. 460/05). Partially supported by the Spanish Ministry of Education and Science under project TSI2006-02731.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 194–212, 2008. c International Association for Cryptologic Research 2008
Matroids Can Be Far from Ideal Secret Sharing
1 1.1
195
Introduction Ideal Secret-Sharing Schemes and Matroids
Secret-sharing schemes, which were introduced by Shamir [31] and Blakley [5] nearly 30 years ago, are nowadays used in many cryptographic protocols. In these schemes there is a finite set of parties, and a collection A of subsets of the parties (called the access structure). A secret-sharing scheme for A is a method by which a dealer distributes shares of a secret value to the parties such that (1) any subset in A can re
Data Loading...
