Parent-identifying codes

For a set C of words of length 4 over an alphabet of size n, and for a, b i s an element of C, let D (a, b) be the set of all descendants of a and b, t hat is, all words x of length 4 where x(i) is an element of {a(i), b(i)} fo r all 1 less than or equal to i less than or equal to 4. The code C satisfi es the Identifiable Parent Property if for any descendant of two code-words one can identify at least one parent. The study of such codes is motivated by questions about schemes that protect against piracy of software. Here w e show that for any epsilon > 0, if the alphabet size is n > n(0)(epsilon) then the maximum possible cardinality of such a code is less than epsilonn( 2) and yet it is bigger than n(2-epsilon). This answers a question of Hollm ann, van Lint, Linnartz, and Tolhuizen. The proofs combine graph theoretic tools with techniques in additive number theory. (C) 2001 Academic Press.