We use pairings over elliptic curves to give a collusion-resistant traitor tracing scheme where the sizes of public keys, secret keys, and ciphertexts are independent of the number of users. Prior constructions from pairings had size $\Omega(N^{1/3})$. Our construction is non-black box.

Traitor-tracing systems allow identifying the users who contributed to building a rogue decoder in a broadcast environment. In a traditional traitor-tracing system, a key authority is responsible for generating the global public parameters and issuing secret keys to users. All security is lost if the \emph{key authority itself} is corrupt. This raises the question: Can we construct a traitor-tracing scheme, without a trusted authority? In this work, we propose a new model for...

A $t$-out-of-$n$ threshold decryption system assigns key shares to $n$ parties so that any $t$ of them can decrypt a well-formed ciphertext. Existing threshold decryption systems are not secure when these parties are rational actors: an adversary can offer to pay the parties for their key shares. The problem is that a quorum of $t$ parties, working together, can sell the adversary a decryption key that reveals nothing about the identity of the traitor parties. This provides a risk-free...

In Crypto 94, Chor, Fiat, and Naor first introduced the traitor tracing (TT) systems, which aim at helping content distributors identify pirates. Since its introduction, many traitor tracing schemes have been proposed. However, we observe until now almost all the traitor tracing systems using probabilistic public key (and secret key) encryption as the the content distribution algorithm, they do not consider this basic fact: the malicious encrypter can plant some trapdoor in the randomness...

We show the following results: - The post-quantum equivalence of indistinguishability obfuscation and differing inputs obfuscation in the restricted setting where the outputs differ on at most a polynomial number of points. Our result handles the case where the auxiliary input may contain a quantum state; previous results could only handle classical auxiliary input. - Bounded collusion traitor tracing from general public key encryption, where the decoder is allowed to contain a...

We present a pairing-based traitor tracing scheme for $N$ users with$$ |\mathsf{pk}| = |\mathsf{ct}| = O(N^{1/3}), \quad |\mathsf{sk}| = O(1). $$This is the first pairing-based scheme to achieve ${|\mathsf{pk}|\cdot|\mathsf{sk}|\cdot|\mathsf{ct}|=o(N)}$. Our construction relies on the (bilateral) $k$-Lin assumption, and achieves private tracing and full collusion resistance. Our result simultaneously improves upon the sizes of $\mathsf{pk},\mathsf{ct}$ in Boneh–Sahai–Waters...

A broadcast, trace and revoke system generalizes broadcast encryption as well as traitor tracing. In such a scheme, an encryptor can specify a list $L \subseteq N$ of revoked users so that (i) users in $L$ can no longer decrypt ciphertexts, (ii) ciphertext size is independent of $L$, (iii) a pirate decryption box supports tracing of compromised users. The ``holy grail'' of this line of work is a construction which resists unbounded collusions, achieves all parameters (including public and...

We present the first fully collusion resistant traitor tracing (TT) scheme for identity-based inner product functional encryption (IBIPFE) that directly traces user identities through an efficient tracing procedure. We name such a scheme as embedded identity traceable IBIPFE (EI-TIBIPFE), where secret keys and ciphertexts are computed for vectors u and v respectively. Additionally, each secret key is associated with a user identification information tuple (i , id, gid) that specifies user...

Several broadcast encryption (BE) constructions have been proposed since Fiat and Naor introduced the concept, some achieving short parameters size while others achieve better security. Since 1994, a lot of alternatives to BE have moreover been additionally proposed, such as the broadcast and trace (BT) primitive which is a combination of broadcast encryption and traitor tracing. Among the other variants of BE, the notion of augmented BE (AugBE), introduced by Boneh and Waters in 2006,...

Functional Encryption (FE) has been extensively studied in the recent years, mainly focusing on the feasibility of constructing FE for general functionalities, as well as some realizations for restricted functionalities of practical interest, such as inner-product. However, little consideration has been given to the issue of key leakage on FE. The property of FE that allows multiple users to obtain the same functional keys from the holder of the master secret key raises an important...

Traitor tracing schemes [Chor–Fiat–Naor, Crypto ’94] help content distributors fight against piracy and are defined with the content distributor as a trusted authority having access to the secret keys of all users. While the traditional model caters well to its original motivation, its centralized nature makes it unsuitable for many scenarios. For usage among mutually untrusted parties, a notion of *ad hoc* traitor tracing (naturally with the capability of broadcast and revocation) is...

The main goal of traceable cryptography is to protect against unauthorized redistribution of cryptographic functionalities. Such schemes provide a way to embed identities (i.e., a "mark") within cryptographic objects (e.g., decryption keys in an encryption scheme, signing keys in a signature scheme). In turn, the tracing guarantee ensures that any "pirate device" that successfully replicates the underlying functionality can be successfully traced to the set of identities used to build the...

In a broadcast encryption system, a sender can encrypt a message for any subset of users who are listening on a broadcast channel. The goal of broadcast encryption is to leverage the broadcasting structure to achieve better efficiency than individually encrypting to each user; in particular, reducing the bandwidth (i.e., ciphertext size) required to transmit securely, although other factors such as public and private key size and the time to execute setup, encryption and decryption are also...

Traitor tracing aims to identify the source of leaked decryption keys. Since the "traitor" can try to hide their key within obfuscated code in order to evade tracing, the tracing algorithm should work for general, potentially obfuscated, decoder programs. In the setting of such general decoder programs, prior work uses black box tracing: the tracing algorithm ignores the implementation of the decoder, and instead traces just by making queries to the decoder and observing the outputs. We...

Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted...

Attribute-based encryption received widespread attention as soon as it was proposed. However, due to its specific characteristics, some restrictions on attribute set in attribute-based encryption are not flexible enough in actual operation. In addition, since access authorities are determined according to users' attributes, users sharing the same attributes are difficult to be distinguished. Once a malicious user makes illicit gains by their decryption authorities, it is difficult to track...

We explore the problem of traitor tracing where the pirate decoder can contain a quantum state. Our main results include: - We show how to overcome numerous definitional challenges to give a meaningful notion of tracing for quantum decoders - We give negative results, demonstrating barriers to adapting classical tracing algorithms to the quantum decoder setting. - On the other hand, we show how to trace quantum decoders in the setting of (public key) private linear broadcast encryption,...

The best existing pairing-based traitor tracing schemes have $O(\sqrt{N})$-sized parameters, which has stood since 2006. This intuitively seems to be consistent with the fact that pairings allow for degree-2 computations, yielding a quadratic compression. In this work, we show that this intuition is false by building a tracing scheme from pairings with $O(\sqrt[3]{N})$-sized parameters. We additionally give schemes with a variety of parameter size trade-offs, including a scheme with...

Broadcast Encryption is a fundamental primitive supporting sending a secure message to any chosen target set of $N$ users. While many efficient constructions are known, understanding the efficiency possible for an ``Anonymous Broadcast Encryption'' (ANOBE), i.e., one which can hide the target set itself, is quite open. The best solutions by Barth, Boneh, and Waters ('06) and Libert, Paterson, and Quaglia ('12) are built on public key encryption (PKE) and their ciphertext sizes are, in...

Software watermarking schemes allow a user to embed an identifier into a piece of code such that the resulting program is nearly functionally-equivalent to the original program, and yet, it is difficult to remove the identifier without destroying the functionality of the program. Such schemes are often considered for proving software ownership or for digital rights management. Existing constructions of watermarking have focused primarily on watermarking pseudorandom functions (PRFs). In...

Encryption is an indispensable tool for securing digital infra- structures as it reduces the problem of protecting the data to just protecting decryption keys. Unfortunately, this also makes it easier for users to share protected data by simply sharing decryption keys. Kiayias and Tang (ACM CCS 2013) were the first to address this important issue pre-emptively rather than a posteriori like traitor tracing schemes do. They proposed leakage-deterring encryption schemes that work as follows....

Functional Encryption (FE) has been widely studied in the last decade, as it provides a very useful tool for restricted access to sensitive data: from a ciphertext, it allows specific users to learn a function of the underlying plaintext. In practice, many users may be interested in the same function on the data, say the mean value of the inputs, for example. The conventional definition of FE associates each function to a secret decryption functional key and therefore all the users get the...

This work shows all necessary calculations to extend the ``Practical Attribute Based Encryption: Traitor Tracing, Revocation, and Large Universe'' scheme of Liu and Wong with non-monotonic access structures. We ensure that the blackbox traceability property is preserved.

A traitor tracing scheme is a multi-user public-key encryption scheme where each user in the system holds a decryption key that is associated with the user's identity. Using the public key, a content distributor can encrypt a message to all of the users in the system. At the same time, if a malicious group of users combine their respective decryption keys to build a "pirate decoder," there is an efficient tracing algorithm that the content distributor can use to identify at least one of the...

In a traitor tracing (TT) system for $n$ users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the $n$ users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called $Trace$, which can identify at least one of the secret keys used to construct the pirate decoding box. Traditionally, the trace algorithm output only...

We construct a broadcast and trace scheme (also known as trace and revoke or broadcast, trace and revoke) with $N$ users, where the ciphertext size can be made as low as $O(N^\epsilon)$, for any arbitrarily small constant $\epsilon>0$. This improves on the prior best construction of broadcast and trace under standard assumptions by Boneh and Waters (CCS `06), which had ciphertext size $O(N^{1/2})$. While that construction relied on bilinear maps, ours uses a combination of the learning with...

A software watermarking scheme enables users to embed a message or mark within a program while preserving its functionality. Moreover, it is difficult for an adversary to remove a watermark from a marked program without corrupting its behavior. Existing constructions of software watermarking from standard assumptions have focused exclusively on watermarking pseudorandom functions (PRFs). In this work, we study watermarking public-key primitives such as the signing key of a digital signature...

Functional encryption (FE) is advanced encryption that enables us to issue functional decryption keys where functions are hardwired. When we decrypt a ciphertext of a message $m$ by a functional decryption key where a function $f$ is hardwired, we can obtain $f(m)$ and nothing else. We say FE is selectively or adaptively secure when target messages are chosen at the beginning or after function queries are sent, respectively. In the weakly-selective setting, function queries are also chosen...

Attribute-Based Encryption (ABE) is a versatile one-to-many encryption primitive, which enables fine-grained access control over encrypted data. Due to its promising applications in practice, ABE schemes with high efficiency, security and expressivity have been continuously emerging. On the other hand, due to the nature of ABE, a malicious user may abuse its decryption privilege. Therefore, being able to identify such a malicious user is crucial towards the practicality of ABE. Although some...

A traitor tracing scheme is a public key encryption scheme for which there are many secret decryption keys. Any of these keys can decrypt a ciphertext; moreover, even if a coalition of users collude, put together their decryption keys and attempt to create a new decryption key, there is an efficient algorithm to trace the new key to at least one the colluders. Recently, Goyal, Koppula and Waters (GKW, STOC 18) provided the first traitor tracing scheme from LWE with ciphertext and secret key...

Private linear key agreement (PLKA) enables a group of users to agree upon a common session key in a broadcast encryption (BE) scenario, while traitor tracing (TT) system allows a tracer to identify conspiracy of a troop of colluding pirate users. This paper introduces a key encapsulation mechanism in BE that provides the functionalities of both PLKA and TT in a unified cost-effective primitive. Our PLKA based traitor tracing offers a solution to the problem of achieving full collusion...

In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$ where $n$ is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably,...

In this work we seek to construct collusion-resistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a $f$-risky traitor tracing system as one where the probability of identifying a traitor is $f(\lambda,n)$ times the probability a successful box is...

A central challenge in differential privacy is to design computationally efficient non-interactive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset $D \in X^n$ consisting of some small number of elements $n$ from some large data universe $X$, and efficiently outputs a summary that allows a user to efficiently obtain an answer to any query in some large family...

A Ciphertext-Policy Attribute-Based Encryption (CP-ABE) allows users to specify the access policies without having to know the identities of users. In this paper, we contribute by proposing an ABE scheme which enables revoking corrupted users. Given a key-like blackbox, our system can identify at least one of the users whose key must have been used to construct the blackbox and can revoke the key from the system. This paper extends the work of Liu and Wong to achieve traitor revocability. We...

A central problem in differential privacy is to accurately answer a large family $Q$ of statistical queries over a data universe $X$. A statistical query on a dataset $D \in X^n$ asks ``what fraction of the elements of $D$ satisfy a given predicate $p$ on $X$?'' Ignoring computational constraints, it is possible to accurately answer exponentially many queries on an exponential size universe while satisfying differential privacy (Blum et al., STOC'08). Dwork et al. (STOC'09) and Boneh...

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing systems via black-box constructions from symmetric cryptographic primitives, e.g. one-way functions. More specifically, we...

In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), access policies associated with the ciphertexts are generally role-based and the attributes satisfying the policies are generally \emph{shared} by multiple users. If a malicious user, with his attributes shared with multiple other users, created a decryption blackbox for sale, this malicious user could be difficult to identify from the blackbox. Hence in practice, a useful CP-ABE scheme should have some tracing mechanism to identify...

In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some ``pirate decoder'' that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition...

We propose a new type of score function for Tardos traitor tracing codes. It is related to the recently introduced tally-based score function, but it utilizes more of the information available to the decoder. It does this by keeping track of sequences of symbols in the distributed codewords instead of looking at columns of the code matrix individually. We derive our new class of score functions from a Neyman-Pearson hypothesis test and illustrate its performance with simulation...

The topic of this paper is collusion resistant watermarking, a.k.a. traitor tracing, in particular bias-based traitor tracing codes as introduced by G.Tardos in 2003. The past years have seen an ongoing effort to construct efficient high-performance decoders for these codes. In this paper we construct a score system from the Neyman-Pearson hypothesis test (which is known to be the most powerful test possible) into which we feed all the evidence available to the tracer, in particular the...

In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), a user's decryption key is associated with attributes which in general are not related to the user's identity, and the same set of attributes could be shared between multiple users. From the decryption key, if the user created a decryption blackbox for sale, this malicious user could be difficult to identify from the blackbox. Hence in practice, a useful CP-ABE scheme should have some tracing mechanism to identify this `traitor' from...

We introduce the k-LWE problem, a Learning With Errors variant of the k-SIS problem. The Boneh-Freeman reduction from SIS to k-SIS suffers from an exponential loss in k. We improve and extend it to an LWE to k-LWE reduction with a polynomial loss in k, by relying on a new technique involving trapdoors for random integer kernel lattices. Based on this hardness result, we present the first algebraic construction of a traitor tracing scheme whose security relies on the worst-case hardness of...

We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. (1) A mark-embedded function must be functionally equivalent to the original...

A Ciphertext-Policy Attribute-Based Encryption (CP-ABE) system extracts the decryption keys over attributes shared by multiple users. It brings plenty of advantages in ABE applications. CP-ABE enables fine-grained access control to the encrypted data for commercial applications. There has been significant progress in CP-ABE over the recent years because of two properties called traceability and large universe, greatly enriching the commercial applications of CP-ABE. Traceability is the...

In the field of collusion-resistant traitor tracing, Oosterwijk et al. recently determined the optimal suspicion function for simple decoders. Earlier, Moulin also considered another type of decoder: the generic joint decoder that compares all possible coalitions, and showed that usually the generic joint decoder outperforms the simple decoder. Both Amiri and Tardos, and Meerwald and Furon described constructions that assign suspicion levels to $c$-tuples, where $c$ is the number of...

At Eurocrypt 2011, Wee presented a generalization of threshold public key encryption, threshold signatures, and revocation schemes arising from threshold extractable hash proof systems. In particular, he gave instances of his generic revocation scheme from the DDH assumption (which led to the Naor-Pinkas revocation scheme), and from the factoring assumption (which led to a new revocation scheme). We expand on Wee's work in two directions: (a) We propose threshold extractable hash proof...

We study the asymptotic-capacity-achieving score function that was recently proposed by Oosterwijk et al. for bias-based traitor tracing codes. For the bias function we choose the Dirichlet distribution with a cutoff. Using Bernstein's inequality and Bennett's inequality, we upper bound the false positive and false negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size $c_0$ and...

In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange, efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting properties that have not been achievable before: - Our multiparty non-interactive key exchange protocol does not require a trusted setup. Moreover, the size of the published value from each user is independent of the total number of users. - Our broadcast encryption schemes support...

White-box cryptography has attracted a growing interest from researchers in the last decade. Several white-box implementations of standard block-ciphers (DES, AES) have been proposed but they have all been broken. On the other hand, neither evidence of existence nor proofs of impossibility have been provided for this particular setting. This might be in part because it is still quite unclear what {white-box} cryptography really aims to achieve and which security properties are expected from...

We study collusion-resistant traitor tracing in the simple decoder approach, i.e. assignment of scores for each user separately. We introduce a new score function for non-binary bias-based traitor tracing. It has three special properties that have long been sought after: (i) The expected score of an innocent user is zero in each content position. (ii) The variance of an innocent user's score is~1 in each content position. (iii) The expectation of the coalition's score does not depend on...

We investigate alternative suspicion functions for bias-based traitor tracing schemes, and present a practical construction of a simple decoder that attains capacity in the limit of large coalition size $c$. We derive optimal suspicion functions in both the Restricted-Digit Model and the Combined-Digit Model. These functions depend on information that is usually not available to the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such...

Trace and revoke is broadcast encryption with the traitor tracing functionality. It is a very powerful primitive since it can revoke users whose private keys are compromised by finding them using a tracing algorithm if a pirate decoder is given. Public-key trace and revoke (PKTR) is a special type of trace and revoke such that anyone can run the tracing algorithm and anyone can create an encrypted message by using a public key. Although public-key trace and revoke schemes are attractive...

We investigate alternative suspicion functions for Tardos traitor tracing schemes. In the simple decoder approach (computation of a score for every user independently) we derive suspicion functions that optimize a performance indicator related to the sufficient code length $\ell$ in the limit of large coalition size $c$. Our results hold for the Restricted-Digit Model as well as the Combined-Digit Model. The scores depend on information that is usually not available to the tracer -- the...

Forensic watermarking is the application of digital watermarks for the purpose of tracing unauthorized redistribution of content. The most powerful type of attack on watermarks is the collusion attack, in which multiple users compare their differently watermarked versions of the same content. Collusion-resistant codes have been developed against these attacks. One of the most famous such codes is the Tardos code. It has the asymptotically optimal property that it can resist c attackers with...

Broadcast encryption (BE) is a cryptographic primitive that allows a broadcaster to encrypt digital content to a privileged set of users and in this way prevent revoked users from accessing the content. In BE schemes, a group of users, called traitor s may leak their keys and enable an adversary to receive the content. Such malicious users can be detected through traitor tracing (TT) schemes. The ultimate goal in a content distribution system would be combining traitor tracing and broadcast...

Let $\G$ be a group of prime order $q$, and let $g_1,\ldots,g_n$ be random elements of $\G$. We say that a vector $\vecx = (x_1,\ldots,x_n)\in \Z_q^n$ is a {\em discrete log representation} of some some element $y\in\G$ (with respect to $g_1,\ldots,g_n$) if $g_1^{x_1}\cdots g_n^{x_n} = y$. Any element $y$ has many discrete log representations, forming an affine subspace of $\Z_q^n$. We show that these representations have a nice {\em continuous leakage-resilience} property as follows....

In the classical model of traitor tracing, one assumes that a traitor contributes its entire secret key to build a pirate decoder. However, new practical scenarios of pirate has been considered, namely Pirate Evolution Attacks at Crypto 2007 and Pirates 2.0 at Eurocrypt 2009, in which pirate decoders could be built from sub-keys of users. The key notion in Pirates 2.0 is the anonymity level of traitors: they can rest assured to remain anonymous when each of them only contributes a very...

The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring...

A traitor tracing scheme is a multi-receiver encryption scheme where malicious receiver coalitions aiming at building pirate decryption devices are deterred by the existence of a tracing algorithm: Using the pirate decryption device, the tracing algorithm can recover at least one member of the malicious coalition. All existing traitor tracing schemes rely either on rather inefficient generic constructions from arbitrary encryption schemes and collusion-secure fingerprinting codes, or on...

An $n$-word $y$ over a finite alphabet of cardinality $q$ is called a descendant of a set of $t$ words $x^1,\dots,x^t$ if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n.$ A code $\cC=\{x^1,\dots,x^M\}$ is said to have the $t$-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. From earlier works it is known that $t$-IPP codes of positive rate exist if and only if $t\le q-1$. We introduce...

Broadcast encryption provides a convenient method to distribute digital content to subscribers over an insecure broadcast channel. Traitor tracing is needed because some users may give out their decryption keys to construct pirate decoders. There are many traitor tracing schemes based on collusion secure codes and identifiable parent property codes. However, these schemes are subject to public collaboration of traitors, which is presented by Billet and Phan in EUROCRYPT 2009 as an attack...

We study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a...

We propose a new encryption scheme that supports joint fingerprinting and decryption. The scheme is remarkably resistant to known-plaintext attack and collusion attack (e.g. average attack or other linear combination attack) on keys. Interestingly, the security of our scheme is relied on a lattice problem: Given a collection of random lattice points generated from a short basis of a lattice, find the short basis. The scheme can be used as a traitor-tracing scheme or a buyer-seller...

Codes with the \emph{Identifiable Parent Property} (IPP) have been studied in the context of traitor tracing; such codes can be used to enable a data supplier to determine the origin of pirated data. We consider an analogous property for a set of binary strings $S$: if a new string $\tau$ is formed by concatenating substrings of members of $S$, we should be able to identify at least one original string which must have been used to generate $\tau$. We prove upper and lower bounds for the size...

A collusion-secure code is called robust if it is secure against erasure of a limited number of undetectable bits, in addition to collusion attacks under Marking Assumption. In this article, we propose the first general conversion method of (non-robust) $c$-secure codes to robust $c$-secure codes. Also, the same method amplifies robustness of given robust $c$-secure codes. By applying our conversion to $c$-secure codes given by Nuida et al. (AAECC 2007), we present robust $c$-secure codes...

We develop an abstract framework that encompasses the key properties of bilinear groups of composite order that are required to construct secure pairing-based cryptosystems, and we show how to use prime-order elliptic curve groups to construct bilinear groups with the same properties. In particular, we define a generalized version of the subgroup decision problem and give explicit constructions of bilinear groups in which the generalized subgroup decision assumption follows from the...

In [BSW06,BW06] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption. In this paper we present new, efficient trace & revoke schemes which are based on prime order bilinear groups, and whose security depend on the hardness of the Decisional Linear Assumption or the External Diffie-Hellman (XDH) assumption....

Key-Policy Attribute-Based Encryption (KP-ABE) is a promising cryptographic primitive which enables fine-grained access control over sensitive data. However, key abuse attacks in KP-ABE may impede its wide application especially in copyright-sensitive systems. To defend against this kind of attacks, this paper proposes a novel KP-ABE scheme which is able to disclose any illegal key distributor’s ID when key abuse is detected. In our scheme, each bit of user ID is defined as an attribute and...

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...

This paper investigates the security of FTT (fully collusion resistant traitor tracing) schemes in terms of DOT (Denial Of Tracing) and framing. With DOT attack, a decoder is able to detect tracing activity, and then prolongs the tracing process such that the tracer is unable to complete tracing job in a realistic time duration and hence has to abort his effort. On the other hand, by merely embedding several bytes of non-volatile memory in the decoder, we demonstrate, for the FTT schemes,...

Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by $k$ traitors out of a static set of $\ell$ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such...

This paper proposes fully resilient traitor tracing schemes which have no restriction about the number of traitors. By using the concept of key update, the schemes can make the pirate decoders useless within some time-period, which will be called life-time of the decoder. There is a trade-off between the size of ciphertext and life-time of pirate decoders.

Copyrighting a function is the process of embedding hard-to-remove marks in the function's implementation while retaining its original functionality. Here we consider the above problem in the context of public-key encryption and we parallel the process of copyrighting a function to the process of designing traitor tracing schemes. We derive two copyrighted public-key encryption functions for the $2$-key setting, solving an open question left by earlier work with respect to copyrighting...

Pairing based cryptography is a new public key cryptographic scheme. An elliptic curve suitable for pairing based cryptography is called a ``pairing-friendly'' elliptic curve. After Mitsunari, Sakai and Kasahara's traitor tracing scheme and Boneh and Boyen's short signature scheme, many protocols based on pairing-related problems such as the $q$-weak Diffie-Hellman problem have been proposed. In Eurocrypt 2006, Cheon proposed a new efficient algorithm to solve pairing-related problems and...

Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers: if some receivers collude and share their decryption keys to build some pirate decoder, a tracing procedure should be able to find at least one of these ``traitors'' from the pirate decoder. In this paper, we consider powerful pirate decoders, which may sometimes refuse to decrypt, or may try to detect when the tracing procedure is running. Most known traitor tracing...

We introduce a simple primitive called Augmented Broadcast Encryption (ABE) that is sufficient for constructing broadcast encryption, traitor-tracing, and trace-and-revoke systems. These ABE-based constructions are resistant to an arbitrary number of colluders and are secure against adaptive adversaries. Furthermore, traitor tracing requires no secrets and can be done by anyone. These broadcast systems are designed for broadcasting to arbitrary sets of users. We then construct a secure ABE...

Recently, Boneh, Gentry, and Waters '05 presented an efficient broadcast encryption, and Boneh, Sahai, and Waters '06 presented an efficient traitor tracing scheme. The former broadcast encryption result contains both a simpler chosen plaintext secure version and a more complicated but chosen ciphertext secure version. The latter traitor tracing scheme is only chosen plaintext secure. In this paper, we use the twin encryption technique of Naor and Yung '90 to add chosen ciphertext...

A cover-free family is a well-studied combinatorial structure that has many applications in computer science and cryptography. In this paper, we propose a new public key traitor tracing scheme based on cover-free families. The new traitor tracing scheme is similar to the Boneh-Franklin scheme except that in the Boneh-Franklin scheme, decryption keys are derived from Reed-Solomon codes while in our case they are derived from a cover-free family. This results in much simpler and faster tracing...

At the Asiacrypt 2003 conference Billet and Gilbert introduce a block cipher, which, to quote them, has the following paradoxical traceability properties: it is computationally easy to derive many equivalent distinct descriptions of the same instance of the block cipher; but it is computationally difficult, given one or even up to $k$ of them, to recover the so-called meta-key from which they were derived, or to find any additional equivalent description, or more generally to forge any new...

We construct the first fully collusion resistant tracing traitors system with sublinear size ciphertexts and constant size private keys. More precisely, let $N$ be the total number of users. Our system generates ciphertexts of size $O(\sqrt{N})$ and private keys of size $O(1)$. We build our system by first building a simpler primitive called private linear broadcast encryption (PLBE). We then show that any PLBE gives a tracing traitors system with the same parameters. Our system uses...

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.

$\Gamma$ is a $q$-ary code of length $L$. A word $w$ is called a descendant of a coalition of codewords $w^{(1)}, w^{(2)}, \dots, w^{(t)}$ of $\Gamma$ if at each position $i$, $1 \leq i \leq L$, $w$ inherits a symbol from one of its parents, that is $w_i \in \{ w^{(1)}_i, w^{(2)}_i, \dots, w^{(t)}_i \}$. A $k$-secure frameproof code ($k$-SFPC) ensures that any two disjoint coalitions of size at most $k$ have no common descendant. Several probabilistic methods prove the existance of codes but...

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give...

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non-trusted content providers using the same set of keys, which makes the scheme...

A broadcast encryption scheme for stateless receivers is a data distribution method which never updates users' secret information while in order to maintain the security the system efficiency decreases with the number of revoked users. Another method, a rekeying scheme is a data distribution approach where it revokes illegal users in an {\em explicit} and {\em immediate} way whereas it may cause inconvenience for users. A hybrid approach that appropriately combines these two types...

A (public key) Trace and Revoke Scheme combines the functionality of broadcast encryption with the 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...

The paper gives an upper bound on the size of a $q$-ary code of length $n$ that has the $k$-identifiable parent property. One consequence of this bound is that the optimal rate of such a code is determined in many cases when $q\rightarrow\infty$ with $k$ and $n$ fixed.

In this paper, we first show that three public-key $(k,n)$-traceability schemes can be derived from an $[n,u,d]$-linear code ${\cal C}$ such that $d \geq 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...

In Crypto'99, Boneh and Franklin proposed a public key traitor tracing scheme~\cite{Boneh}, which was believed to be able to catch all traitors while not accusing any innocent users (i.e., full-tracing and error-free). Assuming that Decision Diffie-Hellman problem is unsolvable in $G_{q}$, Boneh and Franklin proved that a decoder cannot distinguish valid ciphertexts from invalid ones that are used for tracing. However, our novel pirate decoder $P_{3}$ manages to make some invalid ciphertexts...

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...

We apply powerful, recently discovered techniques for the list decoding of error-correcting codes to the problem of efficiently tracing traitors. Traitor tracing schemes have been extensively studied for use as a piracy deterrent. In a widely studied model for protecting digital content, each user in the system is associated with a unique set of symbols. For example, the sets may be used to install a software CD or decrypt pay-TV content. The assignment of sets is done in such a way that if...

In order to protect copyrighted material, codes may be embedded in the content or codes may be associated with the keys used to recover the content. Codes can offer protection by providing some form of traceability for pirated data. Several researchers have studied different notions of traceability and related concepts in recent years. "Strong" versions of traceability allow at least one member of a coalition that constructs a "pirate decoder" to be traced. Weaker versions of this concept...