Generalized hashing and applications to digital fingerprinting

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x¹, ..., x^t if yi ∈ {x_i¹, ..., x_i^t} for all i=1, ..., n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We study a generalization of hashing, (t, u)-hashing, which ensures identification, and provide tight estimates of the rates.