It has recently been shown that there are no multimedia fingerprinting codes that can find all malicious users when they use arbitrary linear attacks plus adversarial noise. It is shown that such codes exist if the complete recovery property is limited to the IPP property, i.e., the property to find at least one malicious user. Moreover, we extend this property to a property that allows us to detect all users whose contribution to the forgery is large enough. Efficient decoding (tracing traitors) algorithms are developed for these codes.

This paper presents an explicit construction of multimedia codes with complete traceability resistant to the averaging attack and δ-noise. The obtained code is a combination of a class of signature codes together with a generalization of superimposed codes, for which existence lower bounds, using the Lovász Local Lemma, are obtained. The constructions are a consequence of the Moser-Tardos variable framework.

A family F of w-subsets of a finite set X is called a set system with the identifiable parent property if for any w-subset contained in the union of some t sets, called traitors, of F at least one of these sets can be uniquely determined, i.e. traced. A set system with traceability property (TSS, for short) allows to trace at least one traitor by minimal distance decoding of the corresponding binary code, and hence the complexity of tracing procedure is of order O(M), where M is the number of users or the code's cardinality. We propose a new construction of TSS which is based on the old Kautz-Singleton concatenated construction with algebraic-geometry codes as the outer code and Guruswami-Sudan decoding algorithm. The resulting codes (set systems) have exponentially many users (codevectors) M and polylog(M) complexity of code construction and decoding, i.e. tracing traitors. This is the first construction of traceability set systems with such properties.

Parent-identifying schemes provide a way to identify causes from effects for some information systems, such as digital fingerprinting and group testing. In this paper, we consider the combinatorial structures for parent-identifying schemes. First, we establish an equivalent relationship between the parent-identifying schemes and forbidden configurations. Based on this relationship, we derive the probabilistic existence lower bounds for two related combinatorial structures, that is, t-parent-identifying set systems (t-IPPS) and t-multimedia parent-identifying codes (t-MIPPC), which are used in broadcast encryption and multimedia fingerprinting, respectively. The probabilistic lower bound for the maximum size of a t-IPPS has the asymptotically optimal order of magnitude in many cases, and that for t-MIPPC provides the asymptotically optimal code rate when t = 2 and the best known asymptotic code rate when t ≥ 3. Furthermore, we analyze the structure of 2-IPPS and prove some bounds for certain cases.

We consider collusion-resistant fingerprinting codes for multimedia content. We show that the corresponding IPP-codes may trace all guilty users and at the same time have exponentially many code words. We also establish an equivalence between signature codes for the A-channel and multimedia fingerprinting codes and prove that the rate of the best t-signature codes for A-channel is at least Θ(t-2). Finally, we construct a family of t-signature codes for the A-channel with polynomial decoding complexity and rate Θ(t-3).

Codes with the Identifiable Parent Property (IPP codes) form a very useful tool in traitor tracing schemes since they guarantee (with probability 1) identification of at least one of the traitors. We consider a natural generalization of IPP codes, namely codes for which this property holds with probability close to 1. A probabilistic version of the IPP problem has been studied under the name of collusion-secure digital fingerprinting codes. We point out that, somewhat surprisingly, fingerprinting codes do no automatically have the “almost IPP property.” In practice, this means that for a given forged fingerprint, a good tracing algorithm identifies some user, say u, as a traitor, claiming that the probability of incorrect accusation is close to 0. Nevertheless this user can successfully dispute this claim because with high probability there exist coalitions that do not contain u and that can generate the same forged fingerprint. The described shortcoming of the accepted definition of fingerprinting capacity is manifest even in the simplest case of two traitors. We discuss this case and then analyze some known constructions of digital fingerprinting codes based on concatenated codes.

Ann-wordy=(y1,...,yn) over a finite alphabet of cardinalityqis called a descendant of a set oftwordsx1,...,xtif every coordinateyi,i=1,...,n, is contained in the set {x1i,...,xti}. A codeC={x1,...,xM} is said to have thet-IPP property if for anyn-wordythat is a descendant of at mosttparents belonging to the code, it is possible to identify at least one of them. From earlier works, it is known thatt-IPP codes of positive rate exist if and only ift≤q-1. We introduce a robust version of IPP codes which allows error-free identification of parents in the presence of a certain number of mutations, i.e., coordinates inythat can break away from the descent rule, taking arbitrary values from the alphabet or becoming completely unreadable. We show existence of robustt-IPP codes for allt≤q-1 and some positive proportion of such coordinates. We uncover a relation between the hash distance of codes and the IPP property and use it to find the exact proportion of mutant coordinates that permits identification of pirates with zero probability of error in the case of size-2 coalitions.

Let a binary Reed-Muller code RM(s;m) of length n be used on a memoryless channel with an input alphabet ±1 and a real-valued output ℝ. Given a received vector y in ℝn; we define its generalized distance T to any codeword c as the sum Σ|yj|taken over all positions j, in which vectors y, c have opposite signs. We then consider the list ℒTof codewords located within distance T from the received vector y and estimate the size LTof this list using the generalized Johnson bound. For any RM code RM(s,m) of fixed order s, the algorithm is proposed that performs list decoding beyond the error-correcting radius with linear complexity in length n and retrieves the code list ℒTwith complexity of order nsLTfor any decoding radius T within the generalized Johnson bound.

The theory of separating codes has been applied in several areas of science ranging from automata synthesis to the protection of distribution rights. In this paper, we introduce a relaxed version of separating and secure frameproof codes and show that for the relaxed definitions these two notions are different, as opposed to the original definitions when these notions coincide. Moreover, we also discuss how this new relaxed versions of the codes can be used to construct a family of fingerprinting codes.

Codes with the identifiable parent property (IPP codes) are used in traitor tracing schemes that protect data broadcast by the publisher from unauthorized access or distribution. An n-word y over a finite alphabet is called a descendant of a set of t words x1, ..., xtif yiϵ {x1i, ..., xti} for all i = 1, ... n. A code C = {x1, ..., xM} is said to have the i-IPP property if for any n-word y that is a descendant of at most t parents belonging to the code it is possible to identify at least one of them. The existence of good i-IPP codes is known from earlier works. We introduce a robust version of IPP codes which allows unconditional identification of parents even if some of the coordinates in y can break away from the descent rule, i.e., can take arbitrary values from the alphabet, or become completely unreadable. By linking this problem to perfect hash functions and, more generally, to hash distances of a code, we prove initial results on the proportion of such coordinates that can be tolerated under the unconditional recovery requirement.

Let a biorthogonal Reed-Muller code RM (1,m) of length n = 2mbe used on a memoryless channel with an input alphabet plusmn1 and a real-valued output R. Given any nonzero received vector y in the Euclidean space Rnand some parameter epsiisin(0,1), our goal is to perform list decoding of the code RM (1, m) and retrieve all codewords located within the angle arccos e from y. For an arbitrarily small epsi, we design an algorithm that outputs this list of codewords with the linear complexity order of n [ln2isin] bit operations. Without loss of generality, let vector y be also scaled to the Euclidean length radic(n) of the transmitted vectors. Then an equivalent task is to retrieve all coefficients of the Hadamard transform of vector y whose absolute values exceed nisin. Thus, this decoding algorithm retrieves all ne-significant coefficients of the Hadamard transform with the linear complexity n [ln2isin] instead of the complexity n In2n of the full Hadamard transform.

Soft-decision decoding on a memoryless channel is considered for the first-order Reed-Muller codes RM (1, m) of length 2m. We assume that different positions j of the received binary vector y can be corrupted by the errors of varying weight wj. The generalized Hamming distance between vector y and any binary vector c is then defined as the sum of weighted differences wj|yj- cj| taken over all n positions. We obtain a tight upper bound LTon the number of codewords located within generalized Hamming distance T from vector y, and design a decoding algorithm that outputs this list of codewords with complexity O (n ln2LT). In particular, all possible error weights wjequal 1 if this combinatorial model is applied to a binary symmetric channel. In this case, the well known Green algorithm performs full maximum likelihood decoding of RM (1, m) and requires O (n ln2n) bit operations, whereas the Litsyn-Shekhovtsov algorithm operates within the bounded-distance decoding radius n/4-1 with linear complexity O(n). We close the performance-complexity gap between the two algorithms. Namely, for any fixed (0, ½), our algorithm outputs the complete list of codewords within the decoding radius n(½-) with linear complexity of order n ln2.

A new deterministic list decoding algorithm is proposed for general Reed-Muller codes RM(s,m) of length n = 2mand distance d = 2m-epsi. Given n and d, the algorithm performs beyond the bounded distance threshold of d/2 and has a low complexity order of nmepsi-1for any decoding radius T that is less than the Johnson bound

This paper considers the fingerprinting problem for the particular case when coalitions of pirates consist of no more than two users. It proves that random binary fingerprinting codes are secure against size-2 coalitions with probability of error tending to zero and code rate R=1-1/21og/sub 2/3=0.2075. This is an improvement by a factor of eight over the best known schemes that provide the error probability tending to zero.

This paper proves that random ternary codes are 2-traceability codes for code rate R/spl ges/c>0. This gives an affirmative answer to a particular case of the open problem of the minimum size q/sub t/ of the alphabet over which there exist t-traceability codes with nonvanishing code rate.

We propose a formal model for embedding information in black and white images and prove the equivalence between the existence of embedding schemes and covering codes. An asymptotically tight bound on the performance of embedding schemes is given. We construct efficient embedding schemes via known coverings. In particular, one of those schemes allows the embedding of up to /spl lfloor/log/sub 2/(n+1)/spl rfloor/ bits in coverwords of n bits, changing at most one bit, which is twice as good as the scheme of Y.-Y. Chen et al. (see Proc. IEEE Symp. on Computers and Communication - ISCC 2000, p.750-5, 2000). We rewrite some previous schemes with a look towards their covering structures. Finally, we address the problem of active warden in a similar way, giving a model, establishing the relationship with centered codes and concluding by a construction of schemes resistant to active warden.

We consider a general fingerprinting problem of digital data under which coalitions of users can alter or erase some bits in their copies in order to create an illegal copy. Each user is assigned a fingerprint which is a word in a fingerprinting code of size M (the total number of users) and length n. We present binary fingerprinting codes secure against size-t coalitions which enable the distributor (decoder) to recover at least one of the users from the coalition with probability of error exp(-/spl Omega/(n)) for M=exp(/spl Omega/(n)). This is an improvement over the best known schemes that provide the error probability no better than exp(-/spl Omega/(n/sup 1/2/)) and for this probability support at most exp(O(n/sup 1/2/)) users. The construction complexity of codes is polynomial in n. We also present versions of these constructions that afford identification algorithms of complexity poly(n)=polylog(M), improving over the best previously known complexity of /spl Omega/(M). For the case t=2, we construct codes of exponential size with even stronger performance, namely, for which the distributor can either recover both users from the coalition with probability 1-exp(/spl Omega/(n)), or identify one traitor with probability 1.

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x 1 , . . . ,x t if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all i=1, . . . ,n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes with asymptotically nonvanishing rate.

In both open and private communication the participants face potential threats from a malicious enemy who has access to the communication channel and can insert messages (impersonation attack) or alter already transmitted messages (substitution attack). Authentication codes (A-codes) have been developed to provide protection against these threats. In this paper we introduce a new distance, called the authentication distance (A-distance), and show that an A-code can be described as a code for the A-distance. The A-distance is directly related to the probability P/sub S/ of success in a substitution attack. We show how to transform an error-correcting code into an A-code and vice versa. We further use these transformations to provide both upper and lower bounds on the size of the information to be authenticated, and study their asymptotic behavior. As examples of obtained results, we prove that the cardinality of the source state space grows exponentially with the number of keys provided P/sub S/>P/sub I/, we generalize the square-root bound given by Gilbert, MacWilliams, and Sloane in 1979, and we provide very efficient constructions using concatenated Reed-Solomon codes.