On some methods for unconditionally secure key distribution and broadcast encryption (Q1369720)

To make full use of cryptographic methods -- especially conventional private-key cryptosystems -- to protect communications in a network, proper keys need to be distributed to network users in a secure fashion. One possible approach is based on key predistribution, i.e. methods whereby a trusted authority distributes secret information in such a way that only specified subsets of network users are able to compute certain keys. The key predistribution problem, while interesting on its own, is closely related to the broadcast encryption problem. Broadcast encryption consists of a key predistribution phase followed at some later time by a broadcast message which is to be decrypted by a specified (but not known ahead of time) subset of network users only. In practice for both problems special attention is paid to the information rate, i.e. to the amount of secret information that needs to be stored by each user. In the paper both problems are studied using the tools of information theory, so the security provided is unconditional. In the first part of the paper the key predistribution problem is studied. First, formal definitions of a Key Predistribution Scheme (KPS) and its information rate are introduced together with the notation used in the rest of the paper. Then some known KPSs are surveyed and their information rate investigated. The attractive idea of Key Distribution Pattern (KDP) is studied more closely and a new technique that makes use of resilient functions and leads to an improvement in the information rate of KDP is presented. In the second part of the paper the one-time broadcast encryption problem is studied. Again, formal definitions of One-Time Broadcast Encryption Scheme (OTBES) and its information rate are introduced and some constructions are given. Then, a general approach to construct OTBES by combining several KPSs with an ideal secret sharing scheme is presented. This approach is then illustrated by using a combination of balanced incomplete block designs and threshold schemes to construct a new broadcast encryption scheme.