Generalized hashing and parent-identifying codes

Let C be a code of length it over an alphabet of q letters. For a pair of integers 2 less than or equal to t < u, C is (t, u)-hashing if for any two subsets T, U subset of C, satisfying T subset of U, \T\ - t, \U\ = u, there is a coordinate 1 less than or equal to i less than or equal to n such that for any x is an element of T, y is an element of U - x, x and y differ in the ith coordinate. This definition, generalizing the standard notion of a t-hashing family, is motivated by an application in designing the so-called parent identifying codes, used in digital fingerprinting. In this paper, we provide lower and upper bounds on the best possible rate of (t, it)-hashing families for fixed t, it and growing n. We also describe an explicit construction of (t, it)-hashing families. The obtained lower bound on the rate of (t, it)-hashing families is applied to get a new lower bound on the rate of t-parent identifying codes. (C) 2003 Elsevier Inc. All rights reserved.