New constructions for IPP codes (Q1781000)

This paper deals with codes with a traceability property, namely the so-called Identifiable Parent Property (IPP) codes, introduced to protect copyrighted digital data. Let \(C\) be and \((n,M,q)\)-code, \(w\geq 2\)\, an integer, and let \(desc_w(C)\)\, be the \(w\)-descendant code, defined as the set of \(n\)-tuples \(x\)\, that can be produced by a coalition of codewords \(C_0 \subset C\)\, of size at most \(w\) (i.e. \(x_i\in \{a_i; a\in C_0 \}, 1\leq i\leq n\)). Then \(C\)\, is called an IPP code if for all \(x\in desc_w(C)\)\, it holds that \(\cap_i\, C_i\) is not empty, where \(C_i\subset C\),\, of size at most \(w\)\, and \(x\in desc(C_i)\). IPP codes were introduced by \textit{H. Hollmann} et al. [J. Comb. Theory, Ser. A 82, 121--133 (1998; Zbl 0910.05070)] and its properties have been later studied by other authors. In particular \textit{J. Staddon} et al. [IEEE Trans. Inf. Theory 47, 1042--1049 (2001; Zbl 1001.94032)] show that error-correcting codes with ``sufficiently large'' distance are IPP codes. The present paper provides two explicit constructions methods for IPP codes using recursion techniques. The first construction, described in section 3, provides an infinite class of IPP codes with the best asymptotic behavior. Moreover the authors show that this codes have an efficient traitor tracing algorithm (TTA) with running time \(O(M)\) (traitor tracing schemes have been extensively studied for use against piracy. List decoding techniques of error correcting codes enable to construct traceability schemes with fast TTA). Previously the existence of TTA with running time \(O(M)\) was only known for the subclass of the so-called TA-codes, \textit{A. Silverberg} et al. [ASIACRYPT 2001, Lect. Notes Comput. Sci. 2248, 175--192 (2001; Zbl 1062.94552)]. Section 4 presents a new construction of perfect hash families and later uses this class to derive an infinite class of IPP codes.