Laszlo 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 {\em
perfect}. The {\em 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 
{\it 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.