Dealer's random bits in perfect secret sharing schemes
Dealer's random bits in perfect secret sharing schemes
L. Csirmaz:
The dealer's random bits in perfect secret sharing schemes
A secret sharing scheme permits a secret to be shared among participants of
an n-element group in such a way that only qualified subsets of
participants can recover the secret. If any non-qualified subset has
absolutely no information on the secret, then the scheme is called
perfect. The share in a scheme is the information what a
participant must remember. It was known that in any perfect secret
sharing scheme realizing a certain collection of qualified sets over
n participant, at least one participant must use at least
O(n/log n) random bits for each bit
in the secret. Here we present a collection of qualified sets so that the
total number of random bits used by all the participants, i.e. the
dealer's random bits is at least O(n^2/log n) for
each bit in the secret.
Key words: Secret sharing, perfect secret sharing schemes, polymatroid
structures, information theory.