New Lower Bounds for Secure Codes and Related Hash Families: A Hypergraph Theoretical Approach

摘要

Various kinds of secure codes and their related hash families are broadly studied combinatorial structures for protecting copyrighted materials. The codewords in such a structure can be regarded as a subset of QN , the set of all q-ary vectors of given length N, satisfying some constraints. We use a hypergraph model to characterize the combinatorial structure. By applying a result of Duke et al. on the lower bound of the independence number of hypergraphs, we provide a new approach to evaluate the lower bounds for several kinds of secure codes and related hash families. In particular, the general method is illustrated via the examples of existence results on some perfect hash families, frameproof codes, and separable codes.