Abstract This paper addresses the generation of binary 2-separating codes and the study of the code rates that can be achieved in practice. In the case of binary 2-separating codes, there exist lower and upper theoretical bounds in the rates that can be achieved. The generation of 2-separating codes has been studied from a theoretical point of view, but, as far as we know, it has not been tackled from a practical point of view. In this paper, we consider and analyze two different generation algorithms. Both algorithms were implemented in CUDA and executed in GPUs, for the sake of efficiency. The first algorithm is inspired by the Moser–Tardos algorithm, which is based on the Local Lovász Lemma. This algorithm has a strong theoretical appeal; codes obtained through this first algorithm can be shown to match the best known lower bound. To generate codes with rates as large as possible, a second algorithm has been implemented. The rates achieved are larger than those achieved with the first algorithm, but they still are very far from the theoretical upper bound. The results obtained suggest that the theoretical upper bound can probably be improved.

This paper studies the decoding of traceability codes though the lens of the Koetter- Vardy algebraic soft-decision decoding algorithm. Our focus is on the multiplicity assignment step. Previous works assumed that the cost of the multiplicity matrix had to approach infinity. We show that the cost of the multiplicity matrix can be polynomial in the code length in order to find identifiable traitors.

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.

The usefulness of Identifiable Parent Property (IPP) schemes in diverse scenarios has led to several distinct but related concepts. This work focuses on three of these concepts: “classical” IPP codes, Multimedia IPP codes, and IPP set systems. Although several existence bounds for all of the above schemes are known, constructions are scarce. In this paper, we present explicit constructions of all mentioned IPP notions, in the form of combinatorial objects. Our discussion follows a systematic procedure. First, we use the Lovász Local Lemma (LLL) to obtain existence bounds for the object to be constructed. The bounds derived essentially match the previously best-known ones. Additionally, our proof strategy enables for further development. It allows us to use the Moser-Tardos algorithmic version of the LLL in order to construct, with polynomial complexity, the actual objects. Moreover, we extend the results of Giotis et al. to precisely establish the computational complexity of the proposed algorithms.

Abstract According to their strength, the tracing properties of a code can be categorized as frameproof, separating, IPP and TA. It is known that, if the minimum distance of the code is larger than a certain threshold then the TA property implies the rest. Silverberg et al. ask if there is some kind of tracing capability left when the minimum distance falls below the threshold. Under different assumptions, several papers have given a negative answer to the question. In this paper, further progress is made. We establish values of the minimum distance for which Reed-Solomon codes do not posses the separating property.

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.

Codes with the Identifying Parent Property constitute a powerful type of codes with many uses in fingerprinting. Thus, it is of great interest to find sharp existence bounds for that class of codes. By applying a specific variation of the Lovász Local Lemma, we get existence bounds on q-ary IPP codes that improve previously stated ones.

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.

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.

This paper deals with the use of the Koetter-Vardy soft-decision decoding algorithm to perform identification of guilty users in traitor tracing and fingerprinting schemes. In these schemes, each user is assigned a copy of an object with an embedded codeword. Placing different codewords in different copies makes each copy unique and at the same time allows unique identification of each user. The weakness of these schemes comes in the form of a collusion attack, where a group of dishonest users get together and, by comparing their copies, they create a pirate copy that tries to hide their identities. The concern of the paper is restricted to traitor tracing and fingerprinting schemes based on Reed-Solomon codes. By using the Koetter-Vardy soft-decision decoding algorithm as the core part of the tracing process, three different settings are approached: tracing in traceability codes, tracing in identifiable parent property codes and tracing in binary concatenated fingerprinting codes. It is also discussed how by a careful setting of a reliability matrix all possibly identifiable users can be found.

A fingerprinting code is a set of codewords 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 with$\epsilon $error, 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 with probability$1-\epsilon $. The Boneh–Shaw fingerprinting codes are$n$-secure codes with$\epsilon _{B}$error, where$n$also denotes the number of authorized users. Unfortunately, the length the Boneh–Shaw codes should be of order$O(n^{3}\log (n/\epsilon _{B}))$, which is prohibitive for practical applications. In this paper, we prove that the Boneh–Shaw codes are ($c< n$)-secure for lengths of order$O(nc^{2}\log (n/\epsilon _{B}))$. Moreover, in this paper it is also shown how to use these codes to construct binary fingerprinting codes of length$L=O(c^{6}\log (c/\epsilon ) \log n)$, with probability of error$\epsilon < \epsilon _{B}$and an identification algorithm of complexity$poly(\log n)=poly(L)$. These results improve in some aspects the best known schemes and with a much more simple construction.

In a fingerprinting scheme, a distributor places marks in each copy of a digital object. Placing different marks in different copies uniquely identifies the recipient of each copy, and therefore allows tracing of the source of an unauthorised redistribution. A widely used approach to the fingerprinting problem is the use of error correcting codes with a suitable large minimum distance. With this approach, the set of embedded marks in a given copy is precisely a code word of the error correcting code. We present two different approaches that use side information for the tracing process. The first approach deals uses the Guruswami–Sudan errors-and-erasures list decoding algorithm whereas the second approach shows the use of a full side information matrix.

In this paper we present constructions of traceability codes based on the Chinese Remainder Theorem. Taking into account the non-uniformity of the alphabet of the code, we derive a new expression for the minimum distance that allows us to provide a criterion to obtain traceability codes with the maximum number of code words. In order to make the traceability conditions as independent as possible of the code parameters, we also present a new family of non-uniform alphabet codes whose tracing capabilities only depend on the code length.

Traceability codes are used in copyright protection schemes to prevent illegal redistribution of digital content. A traceability code, C, is a set of codewords with the following identification property: let z be a word that is "generated" by a coalition of codewords U/spl sub/C; then there is at least one codeword in U that is "closer" to z than any other codeword not in U is. If the identification process is to be performed efficiently, then error-correcting codes can be used. We make use of a powerful conceptual tool, called ideal-based code (that includes Reed-Solomon, algebraic-geometric and Chinese reminder theorem codes), introduced by V. Guruswami et al., (see Proc. 41st IEEE Symp. on Foundations of Comp. Science, p.159-68, 2000), to present a general framework for the construction and decoding of traceability codes.

In the multimedia content market, there is the need to protect both intellectual property and distribution rights against dishonest buyers. Traitor tracing schemes provide means to find the guilty party in the case of an illegal redistribution. We consider traitor tracing schemes that use error correcting codes, where each user is assigned a unique set of ordered symbols. Since redistributing the set without modification trivially identifies the guilty user, a group of users, aiming to distort their identities, combine their sets and create a new pirate set. In this case, traitor tracing consists in identifying the users whose set agrees the most with the pirate. We present a traitor tracing algorithm that, taking advantage of soft-decision decoding techniques, finds all possibly identifiable traitors, thus extending the capabilities of previously known tracing algorithms.

In order to provide copyright protection for digital contents, a distributor can place marks in each copy of a digital object. Placing different marks in different copies, makes each copy unique, and at the same time allows one to trace the source of an unauthorized distribution. This embedding mark technique, known as fingerprinting, was introduced by Wagner (1983). A problem arises when a group of dishonest users collude, compare their copies, and by changing the marks where their copies differ they create a new copy that conceals their identities. Codes with the "identifiable parent property" or IPP codes, provide means of traceability in the presence of a collusion attack. We present a new decoding algorithm for IPP codes, that can also be used to improve the performance of the Silverberg-Staddon-Walker (see Advances in Cryptology - ASIACRYPT2001, 2001) IPP algorithms.