RANDOMNESS IN DISTRIBUTION PROTOCOLS

Randomness is a useful computation resource due to its ability to enha nce the capabilities of other resources. its interaction with resource s such as time, space, interaction with provers and its role in severa l areas of computer science has been extensively studied. In this pape r we give a systematic analysis of the amount of randomness needed by secret sharing schemes and secure key distribution schemes. We give bo th upper and lower bounds on the number of random bits needed by secre t sharing schemes. The bounds are tight for several classes of secret sharing schemes. For secure key distribution schemes we provide a lowe r bound on the amount of randomness needed, thus showing the optimalit y of a recently proposed key distribution protocol. (C) 1996 Academic Press.