Linear Secret-Sharing Schemes for Forbidden Graph Access Structures
A secret-sharing scheme realizes the forbidden graph access structure determined by a graph \(G=(V,E)\) if a pair of vertices can reconstruct the secret if and only if it is an edge in G. Secret-sharing schemes for forbidden graph access structures of bip
- PDF / 450,026 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 251 Views
Ben Gurion University of the Negev, Be’er Sheva, Israel [email protected], [email protected], [email protected] 2 Universitat Rovira i Virgili, Tarragona, Catalonia, Spain [email protected]
Abstract. A secret-sharing scheme realizes the forbidden graph access structure determined by a graph G = (V, E) if a pair of vertices can reconstruct the secret if and only if it is an edge in G. Secret-sharing schemes for forbidden graph access structures of bipartite graphs are equivalent to conditional disclosure of secrets protocols, a primitive that is used to construct attributed-based encryption schemes. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes. A secret-sharing scheme is linear if the reconstruction of the secret from the shares is a linear mapping. In many applications of secret-sharing, it is required that the scheme will be linear. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and dense graphs, closing the gap between upper and lower bounds: Given a sparse graph with n vertices and at most n1+β edges, for some 0 ≤ β < 1, we construct a linear secret-sharing scheme realizing its forbidden graph access struc˜ 1+β/2 ). We provide an ture in which the total size of the shares is O(n additional construction showing that every dense graph with n vertices and at least n2 − n1+β edges can be realized by a linear secret-sharing scheme with the same total share size. We provide lower bounds on the share size of linear secret-sharing schemes realizing forbidden graph access structures. We prove that for most forbidden graph access structures, the total share size of every linear secret-sharing scheme realizing these access structures is Ω(n3/2 ), which shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every 0 ≤ β < there exist a 1 graph with at most n1+β edges and a graph with at least n2 −n1+β edges, such that the total share size of every linear secret-sharing scheme realizing these forbidden graph access structures is Ω(n1+β/2 ). This shows that our constructions are optimal (up to poly-logarithmic factors). Keywords: Secret-sharing · Share size Conditional disclosure of secrets
·
Monotone span program
·
The first and the forth authors are supported by ISF grants 544/13 and 152/17 and by the Frankel center for computer science. The second author is supported by the European Union through H2020-ICT-2014-1-644024 and H2020-DS-2015-1-700540, and by the Spanish Government through TIN2014-57364-C2-1-R. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 394–423, 2017. https://doi.org/10.1007/978-3-319-70503-3_13
Linear Secret-Sharing Schemes for Forbidden Graph Access Structures
1
395
Introduction
A secret-sharing scheme, introduced by [14,35,43], is a method in which a dealer, which holds a secret, can distribute shares to a set of parties
Data Loading...
