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
SN - 0097-3165
VL - 95
SP - 349
EP - 359
JO - Journal of Combinatorial Theory - Series A
JF - Journal of Combinatorial Theory - Series A
IS - 2
ER -