THE SIZE OF A SHARE MUST BE LARGE

A secret sharing scheme permits a secret to be shared among participan ts of an n-element group in such a way that only qualified subsets of participants can recover the secret. If any nonqualified subset has ab solutely no information on the secret, then the scheme is called perfe ct. The share in a scheme is the information that a participant must r emember. In [3] it was proved that for a certain access structure any perfect secret sharing scheme must give some participant a share which is at least 50% larger than the secret size. We prove that for each n there exists an access structure on n participants so that any perfec t sharing scheme must give some participant a share which is at least about n/log n times the secret size.(1) We also show that the best pos sible result achievable by the information-theoretic method used here is n times the secret size.