Paper Info
Title
An impossibility result on graph secret sharing
Abstract
A perfect secret sharing scheme based on a graph G is a randomized distribution of a secret among the vertices of the graph so that the secret can be recovered from the information assigned to vertices at the endpoints of any edge, while the total information assigned to an independent set of vertices is independent (in statistical sense) of the secret itself. The efficiency of a scheme is measured by the amount of information the most heavily loaded vertex receives divided by the amount of information in the secret itself. The (worst case) information ratio of G is the infimum of this number. We calculate the best lower bound on the information ratio for an infinite family of graphs the entropy method can give. We argue that almost all existing constructions for secret sharing schemes are special cases of the generalized vector space construction. We give direct constructions of this type for the first two members of the family, and show that for the other members no such construction exists which would match the bound yielded by the entropy method.
Year
DOI
Venue
2009
10.1007/s10623-009-9304-0
Des. Codes Cryptography
Keywords
Field
DocType
Secret sharing,Matroid,Entropy method,Information ratio,Secret sharing on graphs,94A60,94A62,15A03,94A17,05B35,90C05
Discrete mathematics,Combinatorics,Secure multi-party computation,Secret sharing,Vertex (geometry),Upper and lower bounds,Independent set,Verifiable secret sharing,Shamir's Secret Sharing,Homomorphic secret sharing,Mathematics
Journal
Volume
Issue
ISSN
53
3
0925-1022
Citations 
PageRank 
References 
7
0.52
19
Authors
1
Name
Order
Citations
PageRank
László Csirmaz116315.86