Search

A (public key) Trace and Revoke Scheme combines the functionality of broadcast encryption witht he capability of traitor tracing. Specifically, (1) a trusted center publishes a single public key and distributes individual secret keys to the users of the system; (2) anybody can encrypt a message so that all but a specified subset of "revoked" users can decrypt the resulting ciphertext; and (3) if a (small) group of users combine their secret keys to produce a "pirate decoder", the center can trace at least one of the "traitors" given access to this decoder.We construct the first chosen ciphertext (CCA2) secure Trace and Revoke Scheme based on the DDH assumption. Our scheme is also the first adaptively secure scheme, allowing the adversary to corrupt players at any point during execution, while prior works (e.g., [14, 16]) only achieves a very weak form of non-adaptive security even against chosen plaintext attacks.Of independent interest, we present a slightly simpler construction that shows a "natural separation" between the classical notion of CCA2- security and the recently proposed [15, 1] relaxed notion of gCCA2- security.

The authors present a software copyright protection model based on information hiding concepts with a public key scheme. A number of schemes for information hiding have been proposed such as digital watermarking, fingerprinting and traitor tracing scheme. Among these schemes, the authors focus on traitor tracing schemes. They first introduce digital copyright protection schemes. The proposed model provides secure software installation and an illegal copying protection scheme based on an information hiding scheme. It also provides a software live-update scheme based on a traitor tracing scheme. They propose a new model which uses the traitor tracing scheme and an electronic legal license tracing scheme for copyright protection. The live-update scheme of the proposed model is based on the traitor tracing scheme and reliable multicast guarantees security and efficiency.

An efficient traitor tracing scheme for broadcast encryption is proposed. Its security depends on the difficulty of discrete logarithm problem and is equivalent to ElGamal public-key cryptosystem even when subscribers collude. The proposed scheme is the first one which satisfies all the following features: the tracing algorithm is black box tracing; all the traitors are identified from a captured pirate decoder; the data supplier can encrypt the contents such that only a specific subset of subscribers' decoders can decrypt it; the encryption algorithm is public-key.

Broadcast Encryption schemes enable a center to broadcast encrypted programs so that only designated subsets of users can decrypt each program. The stateless variant of this problem provides each user with a fixed set of keys which is never updated. The best scheme published so far for this problem is the "subset difference" (SD) technique of Naor Naor and Lotspiech, in which each one of the n users is initially given O(log2(n)) symmetric encryption keys. This allows the broadcaster to define at a later stage any subset of up to r users as "revoked", and to make the program accessible only to their complement by sending O(r) short messages before the encrypted program, and asking each user to perform an O(log(n)) computation. In this paper we describe the "Layered Subset Difference" (LSD) technique, which achieves the same goal with O(log1+?(n)) keys, O(r) messages, and O(log(n)) computation. This reduces the number of keys given to each user by almost a square root factor without affecting the other parameters. In addition, we show how to use the same LSD keys in order to address any subset defined by a nested combination of inclusion and exclusion conditions with a number of messages which is proportional to the complexity of the description rather than to the size of the subset. The LSD scheme is truly practical, and makes it possible to broadcast an unlimited number of programs to 256,000,000 possible customers by giving each new customer a smart card with one kilobyte of tamper-resistant memory. It is then possible to address any subset defined by t nested inclusion and exclusion conditions by sending less than 4t short messages, and the scheme remains secure even if all the other users form an adversarial coalition.

In known traitor tracing schemes, an enabling block is used for both secure broadcast of a session key and tracing traitors in pirate boxes. This paper suggests a new traitor tracing scheme that has two-levels for efficiency. In the more frequent level an enabling block is used only for a very efficient session key distribution, and a new block, less frequently used, called a renewal block is used for the renewal of the group key and for the detection and revocation of traitors. This organization increases efficiency: the computational complexity of encryption/ decryption of the often employed enabling block is constant, while only that of the sporadically employed renewal block depends on the allowed revocations (as in earlier schemes). However, our saving has a price: in a two-level broadcasting scheme, the new danger is that rather than performing piracy by leaking the keys of the renewal block, the individual traitors may leak to pirates the means to decode the enabling blocks at the sessions. For example, if the enabling block is naively implemented as a single key-encrypting-key that is known to all- and this key is used to encrypt session keys, then any participant can leak this key without being detected. (Note that leaking the session keys themselves, constantly all the time, is typically considered in the literature not to be an economically viable option). In order to prevent this new potential leakage, a novel idea of personal enabling keys (used throughout) is suggested. In order to get a session key, a user will need access to the enabling block with his own personal key. To discourage leakage of the personal key (which would violate the service), a novel self-enforcement method is employed that ties "privacy" to "leakage". The self-enforcement of personal keys uses the fact that if the key is leaked then the party which leaks may lose its private data to the party it leaks to (i.e. it is a privacy-based protection mechanism). In our self-enforcement, a subscriber's private information is not embedded into his personal key directly (as was done earlier). Thus, if a subscriber's important data is altered, his personal key needs not to be regenerated. The separation into two-level broadcast (for efficiency) together with the novel flexible self-enforcement (privacy-based protection of the enabling-block keys) is the central contribution of this work.

Piracy in digital content distribution systems is usually identified as the illegal reception of the material by an unauthorized (pirate). device. A well known method for discouraging piracy in this setting is the usage of a traitor tracing scheme that enables the recovery of the identities of the subscribers who collaborated in the construction of the pirate decoder (the traitors). An important type of tracing which we deal with here is "black-box traitor tracing" which reveals the traitors' identity using only black-box access to the pirate decoder. The only existing general scheme which is successful in general black-box traitor tracing was introduced by Chor Fiat and Naor. Still, this scheme employs a pirate decoder model that despite its generality it is not intended to apply to all settings. In particular it is assumed that (1) the pirate decoder is "resettable", i.e. the tracer is allowed to reset the pirate decoder to its initial state after each trial (but in many settings this is not possible: the pirate decoder is "history-recording"), and that (2) the pirate decoder is "available", i.e. it does not employ an internal reactive mechanism that, say, disables the tracing process (such as shutting down) -- we will call such reactive decoders "abrupt."In this work we discuss pirate-decoders of various types which we categorize according to their capabilities: resettable vs. history recording, and available vs. abrupt. These (crafty) pirate decoders of "enhanced capabilities" (compared to the model of Chor et al.) appear in many plausible piracy scenarios. We then present new (foxy) black-box traitor tracing schemes which cope with such pirate decoders. We present a generic black box traitor tracing technique against any abrupt/resettable decoder. This generic tracing method can be implemented readily in a linear ciphertext size traitor tracing scheme. By employing a new relaxation technique, which we call list-tracing, we describe a traitor tracing scheme with sublinear ciphertext size that is successful against abrupt/resettable pirate decoders. Finally, we present the first black-box traitor-tracing scheme and techniques that are successful against abrupt/history-recording pirate decoders (in the multimedia transmission setting).

In order for the Internet-based digital products to be widely accepted, secure copyright distribution mechanism must be provided with advanced traitor tracing mechanism. We present new software copyright protection and electronic license distribution model based on public key scheme. In this model, digital contents can be distributed over a broadcast channel in a encrypted form and the authorized user can decrypt it, which can be traced back with proposed public key tracing mechanism. Proposed model provides efficiency since merchant server can issue electronic licenses in advance by preprocessing. It also provides secure and efficient software live-update mechanism based on traitor tracing scheme.

We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible in the sense that any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold, while the maximum number of revoked ones cannot be changed in previous schemes. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present an efficient public-key revocable and black-box-traceable scheme by combining flexible revocation with two known black-box-tracing algorithms.

An important open problem in the area of Traitor Tracing is designing a scheme with constant expansion of the size of keys (users' keys and the encryption key) and of the size of ciphertexts with respect to the size of the plaintext. This problem is known from the introduction of Traitor Tracing byChor, Fiat and Naor. We refer to such schemes as traitor tracing with constant transmission rate. Here we present a general methodologyand two protocol constructions that result in the first two public-keytraitor tracing schemes with constant transmission rate in settings where plaintexts can be calibrated to be sufficientlylarge. Our starting point is the notion of "copyrighted function" which was presented byNaccac he, Shamir and Stern. We first solve the open problem of discrete-log-based and public-key-based "copyrighted function." Then, we observe the simple yet crucial relation between (public-key) copyrighted encryption and (public-key) traitor tracing, which we exploit byin troducing a generic design paradigm for designing constant transmission rate traitor tracing schemes based on copyrighted encryption functions. Our first scheme achieves the same expansion efficiency as regular ElGamal encryption. The second scheme introduces only a slightlylarger (constant) overhead, however, it additionallyac hieves efficient black-box traitor tracing (against any pirate construction).

In this paper, we first show that three public-key (k, n)- traceability schemes can be derived from an [n, u, d]-linear code C such that d ? 2k+1. The previous schemes are obtained as special cases. This observation gives a more freedom and a new insight to this field. For example, we show that Boneh-Franklin scheme is equivalent to a slight modification of the corrected Kurosawa-Desmedt scheme. This means that BF scheme is redundant or overdesigned because the modified KD scheme is much simpler. It is also shown that the corrected KD scheme is the best among them.

We use powerful new techniques for list decoding errorcorrecting codes to efficiently trace traitors. Although much work has focusedon constructing traceability schemes, the complexity of the tracing algorithm has receivedlittle attention. Because the TA tracing algorithm has a runtime of O(N) in general, where N is the number of users, it is inefficient for large populations.We produce schemes for which the TA algorithm is very fast. The IPP tracing algorithm, though less efficient, can list all coalitions capable of constructing a given pirate. We give evidence that when using an algebraic structure, the ability to trace with the IPP algorithm implies the ability to trace with the TA algorithm. We also construct schemes with an algorithm that finds all possible traitor coalitions faster than the IPP algorithm. Finally, we suggest uses for other decoding techniques in the presence of additional information about traitor behavior.

A new scheme of asymmetric public-key traitor tracing without involvement of trusted third parties will be discussed in our dissertation. Previously, an efficient construction of asymmetric public-key tracing scheme was also presented by Kurosawa and Desmedt, however, their scheme required the involvement of the third trusted party(s) known as agent(s). As far as we know, our scheme is the first concrete construction of a practical asymmetric public-key traitor tracing that does not rely on trusted agents. Moreover, our protocol contains other desirable features: (direct non-repudiation, full frameproof, and black-box traceability for asymmetric scheme) that the previous public-key traitor tracing schemes did not offer. In order to eliminate the dependencies of the trusted agents, we use a novel primitive, recently invented by Naor and Pinkas called, "oblivious polynomial evaluation".

We deal with the problem of a center sending a message to a group of users such that some subset of the users is considered revoked and should not be able to obtain the content of the message. We concentrate on the stateless receiver case, where the users do not (necessarily) update their state from session to session. We present a framework called the Subset-Cover framework, which abstracts a variety of revocation schemes including some previously known ones. We provide sufficient conditions that guarantees the security of a revocation algorithm in this class. We describe two explicit Subset-Cover revocation algorithms; these algorithms are very flexible and work for any number of revoked users. The schemes require storage at the receiver of log N and 1/2 log2 N keys respectively (N is the total number of users), and in order to revoke r users the required message lengths are of r log N and 2r keys respectively. We also provide a general traitor tracing mechanism that can be integrated with any Subset-Cover revocation scheme that satisfies a "bifurcation property". This mechanism does not need an a priori bound on the number of traitors and does not expand the message length by much compared to the revocation of the same set of traitors. The main improvements of these methods over previously suggested methods, when adopted to the stateless scenario, are: (1) reducing the message length to O(r) regardless of the coalition size while maintaining a single decryption at the user's end (2) provide a seamless integration between the revocation and tracing so that the tracing mechanisms does not require any change to the revocation algorithm.

We proposed a new public-key traitor tracing scheme with revocation capability using the dynamic share and entity revocation techniques. The enabling block of our scheme is independent of the number of subscribers, but dependent on the collusion and revocation thresholds. Each receiver holds one decryption key only. Our traitor tracing algorithm works in a black-box way and is conceptually simple. The distinct feature of our scheme is that when the traitors are found, we can revoke their private keys (up to some threshold z) without updating any private key of the remaining subscribers. Furthermore, we can restore the decryption privilege of a revoked private key later. We can actually increase the revocation capability beyond z with dynamic assignment of shares into the enabling block. This property makes our scheme highly practical. Previously proposed public-key traitor tracing schemes have to update all existing private keys even when revoking one private key only. Our scheme is as efficient as Boneh and Franklin's scheme in many aspects. Our traitor tracing scheme is fully k-resilient such that our traitor tracing algorithm can find all traitors if the number of them is k or less. The encryption algorithm of our scheme is semantically secure assuming that the decisional Diffie-Hellman problem is hard. We also proposed a variant traitor tracing scheme whose encryption algorithm is semantically secure against the adaptive chosen ciphertext attack assuming hardness of the decisional Diffie-Hellman problem.

Traitor tracing schemes deter traitors from giving away their keys to decrypt the contents by enabling the data supplier to identify the source of a redistributed copy. In asymmetric schemes, the supplier can also convince an arbiter of this fact. Another approach to the same goal was suggested by Dwork, Lotspiech and Naor, so called self-enforcement schemes. In these schemes, traitors have to either divulge their private sensitive information or distribute fairly large amount of data. However, the same private information must be revealed to the data supplier, which invokes the necessity of more discussion about the model underlying this scheme. In this paper, we present an efficient asymmetric self-enforcement scheme, which also supports the asymmetric traceability without any trusted third parties, assuming the situation where the authenticity of the exponent of each subscriber's sensitive information bound to the subject entity is publicly certified, such as PKI derived from discrete logarithm based cryptosystems. In our scheme, the sensitive information needs not to be revealed to any entities. As far as we know, there has never been any proposal of asymmetric self-enforcement schemes. Furthermore, our scheme is as efficient as the previous most efficient symmetric or asymmetric traitor tracing schemes proposed so far.

Traceability schemes allow detection of at least one traitor when a group of colluders attempt to construct a pirate decoder and gain illegal access to digital content.Fiat and Tassa proposed dynamic traitor tracing schemes that can detect all traitors if they attempt to rebroadcast the content after it is decrypted.In their scheme the content is broken into segments and marked so that a re-broadcasted segment can be linked to a particular subgroup of users.Mark allocation for a segment is determined when the re-broadcast from the previous segment is observed.They showed that by careful design of the mark allocation scheme it is possible to detect all traitors. We consider the same scenario as Fiat and Tassa and propose a new type of traceability scheme, called sequential traitor tracing, that can efficiently detect all traitors and does not require any real-time computation. That is, the marking allocation is pre-determined and is independent of the re-broadcasted segment.This is very attractive as it allows segments to be shortened and hence the overall convergence time reduced. We analyse the scheme and give two general constructions one based on a special type of function family, and the other on error correcting codes. We obtain the convergence time of these schemes and show that the scheme based on error correcting codes has a convergence time which is the same as the best known result for dynamic schemes.

To protect against illegal copying and distribution of digital objects, such as images, videos and software products, merchants can 'fingerprint' objects by embedding a distinct codeword in each copy of the object, hence allowing unique identification of the buyer. The buyer does not know where the codeword is embedded and so cannot tamper with it. However a group of dishonest buyers can compare their copies of the object, find some of the embedded bits and change them to create a pirate copy. A c-traceability scheme can identify at least one of the colluders if up to c colluders have generated a pirate copy. In this paper we assume the merchant is not trusted and may attempt to 'frame' a buyer by embedding the buyer's codeword in a second copy of the object. We introduce a third party called the 'arbiter' who is trusted and can arbitrate between the buyer and the merchant if a dispute occurs. We describe the system as a set system and give two constructions, one based on polynomials over finite fields and the other based on orthogonal arrays, that provide protection in the above scenario.

Traitor tracing schemes were introduced so as to combat the typical piracy scenario whereby pirate decoders (or access control smart-cards) are manufactured and sold by pirates to illegal subscribers. Those traitor tracing schemes, however, are ineffective for the currently less common scenario where a pirate publishes the periodical access control keys on the Internet or, alternatively, simply rebroadcasts the content via an independent pirate network. This new piracy scenario may become especially attractive (to pirates) in the context of broadband multicast over the Internet. In this paper we consider the consequences of this type of piracy and offer countermeasures. We introduce the concept of dynamic traitor tracing which is a practical and efficient tool to combat this type of piracy. We also consider the static watermarking problem, presented by Boneh and Shaw, and derive bounds on the performance parameters of the "natural majority algorithm".

Traceability schemes for broadcast encryption are defined by Chor, Fiat and Naor in [6] to protect against a possible coalition of users producing an illegal decryption key. Their scheme was then generalized by Stinson and Wei in [17]. These schemes assume that every user can decrypt the secret value. In this paper we discuss key preassigned traceability schemes, in which only the users in a specified privileged subset can decrypt. A new scheme is presented in this paper, which has better traceability than previous schemes. We also present a new threshold traceability scheme by using ramp scheme. All the constructions are explicit and could be implemented easily.

We construct a public key encryption scheme in which there is one public encryption key, but many private decryption keys. If some digital content (e.g., a music clip) is encrypted using the public key and distributed through a broadcast channel, then each legitimate user can decrypt using its own private key. Furthermore, if a coalition of users collude to create a new decryption key then there is an effcient algorithm to trace the new key to its creators. Hence, our system provides a simple and effcient solution to the "traitor tracing problem". Our tracing algorithm is deterministic, and catches all active traitors while never accusing innocent users, although it is only partially "black box". A minor modification to the scheme enables it to resist an adaptive chosen ciphertext attack. Our techniques apply error correcting codes to the discrete log representation problem.

This work presents threshold tracing schemes. Tracing schemes trace the source of keys which are used in pirate decoders for sensitive or proprietary data (such as pay-TV programs). Previous tracing schemes were designed to operate against any decoder which decrypts with a non-negligible success probability. We introduce threshold tracing schemes which are only designed to trace the source of keys of decoders which decrypt with probability greater than some threshold q (which is a parameter). These schemes present a dramatic reduction in the overhead compared to the previous constructions of tracing schemes.

A traceability scheme is a broadcast encryption scheme such that a data supplier T can trace malicious authorized users (traitors) who gave a decryption key to an unauthorized user (pirate). This paper first derives lower bounds on the sizes of keys and ciphertexts. These bounds are all tight because an optimum one-time use scheme is also presented. We then propose a multiple-use scheme which approximately meets our bounds. This scheme is proven to be secure as well as much more efficient than the schemes by Chor, Fiat and Naor. Finally, practical types of asymmetric schemes with arbiter are discussed in which T cannot frame any authorized user as a traitor.

At ACISP 2003 conference, Narayanan, Rangan and Kim proposed a secret-key traitor tracing scheme used for pay TV system. In this note, we point out a flaw in their scheme.

Stream cipher systems are used to protect intellectual property in pay-TV and a number of other applications. In some of these, it would be convenient if a single ciphertext could be broadcast, and subscribers given slightly different deciphering keys that had the effect of producing slightly different plaintexts. In this way, a subscriber who illegally resold material licensed to him could be traced. Previously, such tracing could be done using a one-time pad, or with complicated key management schemes. In this paper we show how to endow any stream cipher with this potentially useful property. We also present a simple traitor tracing scheme based on random coding with which it can be used.

Traitor tracing schemes as introduced by Chor, Fiat, and Naor at Crypto '94 are intended for tracing people who abuse a broadcast encryption scheme by allowing additional, illegitimate users to decrypt the data. The schemes should also provide legal evidence for such treachery.

A trace and revoke scheme is an encryption scheme to make sure that only authorised users can access the content. When a clone device is recovered, the 'trace' component detects the pirate users that have compromised the secret keys in their devices and contributed to the clone device. In a pirate evolution attack, attackers release the compromised secret keys very slowly through a number of generations of pirate decoders that will take long time to disable them all. In this paper we will show an easy and efficient approach for the state-of-art subset difference based trace-revoke scheme to defend well against this attack. Our solution is deployed in AACS, the industry new content protection standard for high definition DVDs. We believe the pirate evolution tolerance bound should be considered carefully while designing a scheme. We formally analyse the trade off between the immunity to evolution attack and revocation efficiency.

Fingerprinting is an emerging technology to protect multimedia data from piracy, where each distributed copy is labelled with unique identification information. To protect the rights of both the merchant and the customer, the fingerprinting is designed to be asymmetric, where the merchant can trace the traitor by means of the embedded fingerprint and the customer is immune to being framed due to the asymmetric property. This paper proposes an asymmetric fingerprinting scheme that is efficient from the bandwidth usage point of view, where a one-out-of-two oblivious transfer protocol is used to achieve the asymmetric property. In our scheme, symmetric encryption instead of public-key encryption, is performed on the multimedia data, which can reduce the complexity and communication cost. In addition, multicast that is an efficient transport technology for one-to-many communication is exploited, which can reduce the bandwidth usage significantly.

We develop a framework of construction strategies for trace- ability codes on the subject of multimedia fingerprinting, which constructs traceability codes in a concatenated way. In fingerprinting systems, there are tradeoffs among the size of the customer base, the collusion resil- ience, and the codeword length. Our goal is to find a strategy to con- struct, traceability codes that reach an equilibrium among these tradeoffs. Instead of investigating a "high-performance" code, which has proven challenging in existing researches, we introduce a concatenated construction methodology to provide a flexible approach for producing more applicable traceability codes by composing several existing "low- performance" collusion-secure codes. Instead of just giving an example constructed by specific codes, we describe a general code construction strategy and give a detailed analysis on it. Moreover, we propose two concatenated construction schemes based on group fingerprinting to show the feasibility of the concatenated construction strategy. Experi- mental results show good performances on the code length, detection time, and tracing ability. © 2007 Society of Photo-Optical Instrumentation

This paper presents a feasible system for image fingerprinting. Two important problems of fingerprinting are the design collusion-secure codes and the watermarking strategies for the fingerprints. We address these problems by proposing hierarchical fingerprint codes and a content adaptive watermarking scheme. It is challenging to find a practical collusion-secure code for fingerprinting because of the trade-offs between the fingerprint code's length, its collusion resiliency, and the size of the customer base. Therefore, instead of pursuing a high-performance code, we construct a new fingerprint code by concatenating existing codes using a hierarchical structure. The resulting code is efficient in decoding, much shorter than existing codes for similar parameters, and thus practical for real systems. In the fingerprinting, the codes are often very long if the applicable colluder-resisting ability and large customer bases are needed. The resulting acute degradation of fingerprinted content may be unacceptable. Hence the long-length watermark must be appropriately embedded into images to preserve the image quality. We design a strength-decision algorithm, on the basis of neural networks, to adaptively embed the long-length fingerprints with suitable magnitudes into different image regions. This adaptive watermarking technique maintains the combination of robustness and imperceptibility without the effort of dealing with visual models. In addition, we analyze the disturbance due to collusion attacks on images and propose an optimization algorithm that can select better embedding positions to resist collusion attacks and preserve acceptable transparency of the watermark according to different multimedia contents. Experimental results show the high detection correctness of the traitor tracing. It implies that our fingerprinting system, constructed by applying a hierarchical fingerprint code to the content-adaptive watermarking scheme, is effective for multimedia application.

Traceability codes are combinatorial objects introduced by Chor, Fiat and Naor in 1994 to be used in traitor tracing schemes to protect digital content. A k-traceability code is used in a scheme to trace the origin of digital content under the assumption that no more than k users collude. It is well known that an error correcting code of high minimum distance is a traceability code. When does this ‘error correcting construction’ produce good traceability codes? The paper explores this question.Let ℓ be a fixed positive integer. When q is a sufficiently large prime power, a suitable Reed–Solomon code may be used to construct a 2-traceability code containing q⌈ℓ/4⌉ codewords. The paper shows that this construction is close to best possible: there exists a constant c, depending only on ℓ, such that a q-ary 2-traceability code of length ℓ contains at most cq⌈ℓ/4⌉ codewords. This answers a question of Kabatiansky from 2005.Barg and Kabatiansky (2004) asked whether there exist families of k-traceability codes of rate bounded away from zero when q and k are constants such that q⩽k2. These parameters are of interest since the error correcting construction cannot be used to construct k-traceability codes of constant rate for these parameters: suitable error correcting codes do not exist when q⩽k2 because of the Plotkin bound. Kabatiansky (2004) answered Barg and Kabatiansky's question (positively) in the case when k=2. This result is generalised to the following: whenever k and q are fixed integers such that k⩾2 and q⩾k2−⌈k/2⌉+1, or such that k=2 and q=3, there exist infinite families of q-ary k-traceability codes of constant rate.

The flaw of traitor tracing schemes based on traditional ElGamal is that cannot resist convex combination attack. On this point this paper raises an improved ElGamal scheme, which shorten the length of the private key. The new scheme uses the users private key and the header h(s, r) to computer session keys. It is worth mentioning that the user's private key has relation with the header h(s, r), so the improved scheme has good revocability. The results show that the security of the improved scheme is enhanced in comparison with the traditional traitor tracing scheme.

In the context of the thesis we are studying the notions of broadcast encryption and traitor tracing in an industrial framework of conditional access systems related to Pay-TV. Broadcast encryption represents a cryptographic primitive which allows confidential transmission of content on a broadcast channel in such a way that only an authorized subset of users defined by the broadcaster are able to access it. Traitor tracing is a mechanism for identifying rogue sources who shared their decryption keys. Combined together, these two methods can be used to identify compromised terminals and instantaneously revoke them. Intuitively these two techniques are of high interest for Pay-TV systems with respect to the threats of today. Today, the majority of industrial security system are based on the tamper-resistance against attacks, such as those exploiting, for instance, different side channel information such as time, power consumption, electromagnetic emanations to name a few. However during recent years these attacks became more and more sophisticated. Therefore the aim of this thesis is to propose new schemes and mechanisms to improve the state-of-the-art for the conditional access systems and more specifically Pay-TV systems so that they rely even more on a solid cryptographic basis. As a matter of fact, even though many cryptographic schemes closely related to the subject of this thesis existed since many years in academia, none of them could have been deployed directly and efficiently in the context of large scale Pay-TV system which puts a number of heavy constraints on the bandwidth as well as on the computational complexity of the receivers. Consequently we will also describe the system and its constraints in order to simplify the task of development and integration of future schemes in these two academic domains in the context of practical environment.

The final publication is available at Springer via http://dx.doi.org/10.1007/s10623-015-0060-z In this paper we discuss some variations of the notion of separating code for alphabets of arbitrary size. We show how the original definition can be relaxed in two different ways, namely almost separating and almost secure frameproof codes, yielding two different concepts. The new definitions enable us to obtain codes of higher rate, at the expense of satisfying the separating property partially. These new definitions become useful when complete separation is only required with high probability, rather than unconditionally. We also show how the codes proposed can be used to improve the rate of existing constructions of families of fingerprinting codes.

Dubrov and Ishai (STOC 2006) revealed, by generalizing the notion of pseudorandom generators (PRGs), that under a computational assumption, randomness in a protocol can be replaced with pseudorandomness in an indistinguishable way for an adversary even if his algorithm has unbounded complexity. However, their argument was applied only to some special protocols. In this article, we first show that their argument is not effective for a wide class of more general protocols. Then we propose a novel evaluation technique for such indistinguishability that is based on usual PRGs and is effective for those more general protocols. Examples of such protocols include parallel computation over honest-but-curious modules, secret sharing, broadcast encryption, traitor tracing, and collusion-secure codes.

International audience; This paper presents a new decoder for probabilistic binary traitor tracing codes under the marking assumption. It is based on a binary hypothesis testing rule which integrates a collusion channel relaxation so as to obtain numerical and simple accusation functions. This decoder is blind as no estimation of the collusion channel prior to the accusation is required. Experimentations show that using the proposed decoder gives better performance than the well-known symmetric version of the Tardos decoder for common attack channels.

Traitor tracing schemes are used in to detect piracy in broadcast encryption systems, in case that a bounded number of authorized users are dishonest. In this paper we present, by solving a variant of the guessing secrets problem defined by Chung, Graham and Leighton [3], a traitor tracing scheme based in the recently discovered van Trung-Martirosyan traceability codes.

In fingerprint-based secure multimedia distribution systems, the encryption process is performed at the sender side before transmission, and the fingerprint embedding and decryption processes are performed at the receiver side simultaneously. In this paper, a low complexity joint fingerprint and decryption (JFD) scheme based on exclusive-or operations has been proposed, which can be effectively used for traitor tracing. The scheme encrypts only sub-pixels of the entire image using a tiny lookup table generated by a stream cipher. In the decryption process, some pixels can be completely recovered and the fingerprinting process depends on four different directions of sub-image blocks. The method successfully leaves the user's fingerprint during decryption and produces slightly different media copies. The experimental results show that the proposed scheme is highly effective in terms of perceptual security and fingerprinted visual quality.

Dynamic traitor tracing schemes are used to trace the source of piracy in broadcast environments such as cable TV. Dynamic schemes divide content into a series of watermarked segments that are then broadcast. The broadcast provider can adapt the watermarks according to the pirate's response and eventually trace him/her. As dynamic algorithms are deterministic, for a given set of inputs, the tracing algorithm will execute exactly the same way each time. An adversary can use this knowledge to ensure that the tracing algorithm is forced into executing at its worst case bound. In this paper we review dynamic traitor tracing schemes and describe why determinism is a problem. We ammend several existing dynamic tracing algorithms by incorporating randomised decisions. This eliminates any advantage an adversary has in terms of the aforementioned attack, as he/she no longers knows exactly how the tracing algorithm will execute. Simulations show that the randomising modifications influence each dynamic algorithm to run at its average case complexity in terms of tracing time. We provide an efficiency analysis of the amended algorithms and give some recommendations for reducing overhead.

The notion of traitor tracing was introduced by Chor, Fiat, and Naor [Tracing Traitors, Lecture Notes in Comput. Sci. 839, 1994, pp. 257--270] in order to combat piracy scenarios. Recently, Fiat and Tassa [ Tracing Traitors, Lecture Notes in Comput. Sci. 1666, 1999, pp. 354--371] proposed a dynamic traitor tracing scenario, in which the algorithm adapts dynamically according to the responses of the pirate. Let n be the number of users and p the number of traitors. Our main result is an algorithm which locates p traitors, even if p is unknown, using a watermarking alphabet of size p+1 and an optimal number of $\Theta(p^2 + p\log n)$ rounds. This improves the exponential number of rounds achieved by Fiat and Tassa in this case. We also present two algorithms that use a larger alphabet: for an alphabet of size p+c+1, $c\geq1$, an algorithm that uses O(p2/c+ p log n) rounds; for an alphabet of size pc+1, an algorithm that uses O(p logcn) rounds. Our final result is a lower bound of $\Omega(p^2/c+p\log_{c+1}n)$ rounds for any algorithm that uses an alphabet of size p+c, assuming that p is not known in advance.