New Lower Bounds for Secure Codes and Related Hash Families: A Hypergraph Theoretical Approach
Yiting Yang, Yiwei Zhang, Gennian Ge · IEEE Transactions on Information Theory · 2016
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$Q^{N}$, 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 Dukeet 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.