TY - JOUR

T1 - Parent-Identifying Codes

AU - Alon, Noga

AU - Fischer, Eldar

AU - Szegedy, Mario

N1 - Funding Information:
For a set C of words of length 4 over an alphabet of size n, and for a, b # C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi # [ai, bi] for all 1 i 4. The code C satisfies 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 we show that for any =>0, if the alphabet size is n>n0(=) then the maximum possible cardinality of such a code is less than =n2 and yet it is bigger than n2&=. This answers a question of Hollmann, van Lint, Linnartz, and Tolhuizen. The proofs combine graph theoretic tools with techniques in additive number theory. ν 2001 Academic Press 1Research supported in part by a USA Israeli BSF grant, by the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Part of this work was done while visiting the School of Mathematics, Institute for Advanced study, Princeton, NJ 08540.

PY - 2001/8

Y1 - 2001/8

N2 - For a set C of words of length 4 over an alphabet of size n, and for a, b ∈ C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi ∈ {ai, bi} for all 1 ≤ i ≤ 4. The code C satisfies 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 we show that for any ε > 0, if the alphabet size is n > n0(ε) then the maximum possible cardinality of such a code is less than εn2 and yet it is bigger than n2-ε. This answers a question of Hollmann, van Lint, Linnartz, and Tolhuizen. The proofs combine graph theoretic tools with techniques in additive number theory.

AB - For a set C of words of length 4 over an alphabet of size n, and for a, b ∈ C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi ∈ {ai, bi} for all 1 ≤ i ≤ 4. The code C satisfies 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 we show that for any ε > 0, if the alphabet size is n > n0(ε) then the maximum possible cardinality of such a code is less than εn2 and yet it is bigger than n2-ε. This answers a question of Hollmann, van Lint, Linnartz, and Tolhuizen. The proofs combine graph theoretic tools with techniques in additive number theory.

UR - http://www.scopus.com/inward/record.url?scp=0038575565&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038575565&partnerID=8YFLogxK

U2 - 10.1006/jcta.2001.3177

DO - 10.1006/jcta.2001.3177

M3 - Article

AN - SCOPUS:0038575565

VL - 95

SP - 349

EP - 359

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 2

ER -