Parent-Identifying Codes

Noga Alon, Eldar Fischer, Mario Szegedy

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)349-359
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Volume95
Issue number2
DOIs
StatePublished - Aug 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Parent-Identifying Codes'. Together they form a unique fingerprint.

Cite this