New constructions for IPP codes (Q1781000): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Sosina S. Martirosyan / rank | |||
Property / reviewed by | |||
Property / reviewed by: Juan G. Tena Ayuso / rank | |||
Revision as of 11:57, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New constructions for IPP codes |
scientific article |
Statements
New constructions for IPP codes (English)
0 references
15 June 2005
0 references
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.
0 references
identifiable parent property (IPP) code
0 references
traceability (TA) code
0 references
error correcting code
0 references
perfect hash family
0 references
recursive construction
0 references