You are looking at a specific version 20140424:182844 of this paper. See the latest version.

Paper 2014/124

Optimal Non-Perfect Uniform Secret Sharing Schemes

Oriol Farràs and Torben Hansen and Tarik Kaced and Carles Padró

Abstract

A secret sharing scheme is non-perfect if some subsets of participants that cannot recover the secret value have partial information about it. The information ratio of a secret sharing scheme is the ratio between the maximum length of the shares and the length of the secret. This work is dedicated to the search of bounds on the information ratio of non-perfect secret sharing schemes. To this end, we extend the known connections between polymatroids and perfect secret sharing schemes to the non-perfect case. In order to study non-perfect secret sharing schemes in all generality, we describe their structure through their access function, a real function that measures the amount of information that every subset of participants obtains about the secret value. We prove that there exists a secret sharing scheme for every access function. Uniform access functions, that is, the ones whose values depend only on the number of participants, generalize the threshold access strcutures. Our main result is to determine the optimal information ratio of the uniform access functions. Moreover, we present a construction of linear secret sharing schemes with optimal information ratio for the rational uniform access functions.

Metadata
Available format(s)
PDF
Publication info
Preprint. MAJOR revision.
Keywords
Secret sharingNon-perfect secret sharingInformation RatioPolymatroid
Contact author(s)
oriol farras @ urv cat
History
2016-09-02: last of 4 revisions
2014-02-24: received
See all versions
Short URL
https://ia.cr/2014/124
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.