Cryptographic Security of Individual Instances for Conference Key Distribution

A conference key distribution is a scheme that allows the designated subset of users to compute a shared key for secure communication. In this paper we analyze secure instances of conference key distribution based on the ideas of Kolmogorov complexity. First, Kolmogorov complexity is used as a measure of the individual security in conference key distribution, we present a model for conference key distribution in terms of Kolmogorov complexity. Then, Kolmogorov complexity is used as a measure of the amount of randomness needed by secure instances of conference key distribution. Thus we give the lower bounds holding in the model for each user needed to store. Moreover, we give lower bounds on the amount of information in conference key distribution for various types of combinatorial structures