Generalized hashing and parent-identifying codes

Noga Alon, Gérard Cohen, Michael Krivelevich, Simon Litsyn

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


Let C be a code of length n over an alphabet of q letters. For a pair of integers 2≤t<u, C is (t, u)-hashing if for any two subsets T, U ⊂ C, satisfying T ⊂ U, T = t, U = u, there is a coordinate 1≤i≤n such that for any x ∈ T, y ∈ U - x, x and y differ in the ith coordinate. This definition, generalizing the standard notion of a t-hashing family, is motivated by an application in designing the so-called parent identifying codes, used in digital fingerprinting. In this paper, we provide lower and upper bounds on the best possible rate of (t, u)-hashing families for fixed t, u and growing n. We also describe an explicit construction of (t, u)-hashing families. The obtained lower bound on the rate of (t, u)-hashing families is applied to get a new lower bound on the rate of t-parent identifying codes.

Original languageEnglish (US)
Pages (from-to)207-215
Number of pages9
JournalJournal of Combinatorial Theory. Series A
Issue number1
StatePublished - Oct 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Generalized hashing and parent-identifying codes'. Together they form a unique fingerprint.

Cite this