A class of non‐linear asymptotic fingerprinting codes with ε‐error

DOIhttps://doi.org/10.1108/14684520710731010
Published date27 February 2007
Pages22-37
Date27 February 2007
AuthorMarcel Fernandez,Josep Cotrina‐Navau,Miguel Soriano
Subject MatterInformation & knowledge management,Library & information science
A class of non-linear asymptotic
fingerprinting codes with
1
-error
Marcel Fernandez, Josep Cotrina-Navau and Miguel Soriano
Department of Telematics Engineering, Universitat Polite
`cnica de Catalunya,
Barcelona, Spain
Abstract
Pupose – The purpose of this paper is to show that a fingerprinting code is a set of code words that
are embedded in each copy of a digital object, with the purpose of making each copy unique. If the
fingerprinting code is c-secure, then the decoding of a pirate word created by a coalition of at most c
dishonest users, will expose at least one of the guilty parties.
Design/methodology/approach – The paper presents a systematic strategy for collusionsattacking
a fingerprinting scheme. As a particular case, this strategy shows that linear codes are not good
fingerprinting codes. Based on binary linear equidistant codes, the paper constructs a family of
fingerprinting codes in which the identification of guiltyusers can be efficiently done using minimum
distance decoding.Moreover, in order to obtain codes with a better ratea 2-secure fingerprinting code is
also constructed by concatenating a code from the previous family with an outer IPP code.
Findings – The particular choice of the codes is such that it allows the use of efficient decoding
algorithms that correct errors beyond the error correction bound of the code, namely a simplified
version of the Chase algorithms for the inner code and the Koetter-Vardy soft-decision list decoding
algorithm for the outer code.
Originality/value – The paper presents a fingerprinting code together with an efficient chasing
algorithm.
Keywords Codes, Algorithmiclanguages
Paper type Technical paper
Introduction
The fingerprinting technique consists in making the copies of a digital object unique
by embedding a different set of marks in each copy. Having unique copies of an object
clearly rules out plain redistribution, but still a coalition of dishonest users can collude,
compare their copies and by changing the marks where their copies differ, they are able
to create a pirate copy that tries to disguise their identities. Thus, the fingerprinting
problem consists in finding, for each copy of the object, the right set of marks that help
to prevent collusion attacks.
The construction of collusion secure codes was first addressed in Boneh and Shaw,
1998. In that paper, Boneh and Shaw obtain (c.1)-secure codes with a probability
1
of
failing to identify a guilty user. Barg et al. (2003) present a construction based on the
composition of two codes, an inner binary (c, c) separable code and an outer non-binary
code.
The security of fingerprinting codes is normally based on the fact that the coalition
cannot use any pre-established strategy, and therefore, the only possibility is to
The current issue and full text archive of this journal is available at
www.emeraldinsight.com/1468-4527.htm
This work has been supported in part by the Spanish Research Council (CICYT) Project
TSI2005-07293-C02-01 (SECONNET) and TIC2003-01748 (RUBI).
OIR
31,1
22
Article received
25 September 2006
Reviewed by EuDiRights
Workshop Committee
Approved for publication
10 October 2006
Online Information Review
Vol. 31 No. 1, 2007
pp. 22-37
qEmerald Group Publishing Limited
1468-4527
DOI 10.1108/14684520710731010
construct the new false fingerprint in a random way. In this case, the probability of
framing an innocent user is lowered. The only possible strategy that is assumed in all
fingerprinting schemes is the majority strategy, so all existing fingerprinting codes are
robust against this strategy. Here we show a new possible strategy. Moreover , we
show how to construct families of 2-secure codes from binary linear equidistant codes.
The proposed construction has the particularity that an innocent user is never framed
and the probability of identifying at least one coalition member is 1 2
1
for any
1
.0.
Unfortunately, the families we construct have a poor code rate. In order to obtain
codes with a better rate, we also present a binary 2-secure code with error
1
, that is a
concatenated code, where the inner code is a code from the previous family and the
outer code is a Reed-Solomon code having the identifiable parent property (IPP).
The use of error correcting codes allows us to view the pirate fingerprint as a
codeword of the fingerprinting code containing many errors. As it is shown below, the
number of errors that a dishonest coalition is able to introduce into the fingerprint, will
force us to be able to decode beyond the error correction bound of the code. Since we
will be using concatenated codes, the basic idea is to pass the information obtained
from the inner decodings, provided by a simplified version of the Chase algorithms, to
a Koetter-Vardy algebraic soft decision decoding algorithm that is used to decode the
outer code.
Previous results and definitions
Let Qbe a finite alphabet of size jQj. We define Qn:¼x¼ðxi;...,x
n
):x
n
[Q. The
elements of Q
n
are called words. For any set X,jXjdenotes the cardinality of X.
Codes
Let Qbe the finite field with qelements, that is, Q¼Fq. A subset Cof a vector space Fn
q
is called a code. The words in Care called code words.
The number of nonzero coordinates in a word xis called the weight of xand is
commonly denoted by w(x). The Hamming distance d(a,b) between two words a,b
[Fn
qis the number of positions where aand bdiffer. The distance between a word a
and a subset of words U#Fn
qis defined as d(a,U):¼min
u[U
d(a,u). The minimum
distance of C, denoted by d, is defined as the smallest distance between two different
code words.
A code Cis a linear code if it forms a subspace of Fn
q. A code with length n,
dimension kand minimum distance dis denoted as a [n, k, d ]-code.
If the code is not linear then it is usually denoted as (n, M, d ) where as before n
denotes the length of the code and dthe minimum distance. In this case Mdenotes the
number of code words is the code. Sometimes the distance parameter is omitted from
the expression and the code is simply denoted as a (n, M) code.
Descendants. Envelope set
Following (Barg et al., 2003; Boneh and Shaw, 1998) (we refer readers to these papers
for a more detailed exposition), given a subset X?Q
n
, we define the envelope E(X)? Q
n
of Xas a set of words than can be derived from Xusing the rules that we detail below.
If y[((X) then yis a descendant of Xand any x[((X) is a parent of y. A position i
is undetectable for Xif xr
i¼xs
i,;x
r
,x
s
[X. The undetectable positions form a set
denoted ((X).
Fingerprinting
codes with
1-error
23

To continue reading

Request your trial

VLEX uses login cookies to provide you with a better browsing experience. If you click on 'Accept' or continue browsing this site we consider that you accept our cookie policy. ACCEPT