Cryptology ePrint Archive: Report 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.

Category / Keywords: Secret sharing, Non-perfect secret sharing, Information Ratio, Polymatroid

Date: received 17 Feb 2014, last revised 24 Apr 2014

Contact author: oriol farras at urv cat

Available format(s): PDF | BibTeX Citation

Version: 20140424:182844 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]