New constructions for IPP codes
type: Item
instance of: scholarly article
title: New constructions for IPP codes
zbMATH Open document ID: 1077.94028
author: Tran van Trung
author: Sosina S. Martirosyan
published in: Designs, Codes and Cryptography
publication date: 2005-06-15T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 94B60
zbMATH DE Number: 2176203
zbMATH Keywords: identifiable parent property (IPP) code
zbMATH Keywords: traceability (TA) code
zbMATH Keywords: error correcting code
zbMATH Keywords: perfect hash family
zbMATH Keywords: recursive construction
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
full work available at URL: s10623-005-6402-5
OpenAlex ID: W2098275865
cites work: Explicit construction of exponential sized families of k-independent sets
cites work: A hypergraph approach to the identifying parent property: The case of multiple parents
cites work: Collusion-secure fingerprinting for digital data
cites work: A Generalization of a Theorem due to MacNeish
cites work: Perfect hashing
cites work: Q4940701
cites work: Tracing traitors
cites work: Q4941865
cites work: Q4941866
cites work: Improved decoding of Reed-Solomon and algebraic-geometry codes
cites work: List decoding algorithms for certain concatenated codes
cites work: Q4474218
cites work: On codes with the identifiable parent property
cites work: New results on frame-proof codes and traceability schemes
cites work: Combinatorial properties of frameproof and traceability codes
cites work: Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
cites work: Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
cites work: Q4487082
cites work: Decoding of Reed Solomon codes beyond the error-correction bound
cites work: On a class of traceability codes
DOI: 10.1007/S10623-005-6402-5
Recommended article: A class of traceability codes
Recommended article: Analysis of two tracing traitor schemes via coding theory
Recommended article: A class of I.P.P. codes with efficient identification
Recommended article: Recursive constructions of secure codes and hash families using difference function families.
Recommended article: On the relationship between the traceability properties of Reed-Solomon codes
Recommended article: Combinatorial properties of frameproof and traceability codes
Recommended article: Upper bounds for parent-identifying set systems
Recommended article: Q4432207
Recommended article: Codes with the Identifiable Parent Property and the Multiple-Access Channel
Recommended article: Q4788569
description: scientific article; zbMATH DE number 2176203