Article Preview
Top1. Introduction
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, i.e., using the pirate decryption device, the tracing algorithm can recover at least one member of the malicious coalition. Traitor tracing schemes are particularly well suited for fighting copyright infringement in the context of commercial content distribution (e.g., Pay-TV, subscription news websites, etc.).
Chor et al. (1994) first proposed the concept of “traitor tracing” at CRYPTO 1994. Since then, much work has been devoted to devising efficient and secure traitor tracing schemes. These schemes can be divided into two categories: Fully collusion resistant schemes and bounded collusion resistant schemes. Boneh et al. (2006) proposed the first non-trivial fully collusion resistant scheme, but its ciphertext size is still large 
, where N is the total number of users). Recently, Boneh & Zhandry (2013) proposed a fully collusion resistant scheme with polylog size parameters. However, it relies on indistinguishability obfuscation (Garg et al, 2013), whose security foundation remains to be studied. Fully collusion resistant schemes are more desirable because they can deal with arbitrarily large malicious coalitions. But, unsurprisingly, the most efficient schemes are in the bounded collusion model where the number of malicious users is limited. Boneh & Franklin (1999) first transformed the standard ElGamal public key encryption into a traitor tracing scheme in the bounded collusion model. This transformation induces a linear loss in efficiency, with respect to the maximum number of traitors. The known transformations from encryption to traitor tracing in the bounded collusion model present at least a linear loss in efficiency, either in the ciphertext size or in the private key size (Boneh & Franklin, 1999; Naor & Pinkas, 2000; Kiayias & Yung, 2002; Sirvent, 2007; Billet & Phan, 2008; Boneh & Naor, 2008). There is a common defect in all of the above schemes, i.e., they are all based on the hardness of number theoretic problem (such as large integer factorization problem and discrete logarithm problem), and cannot resist the attack from a quantum computer.
Since the pioneering work of Ajtai (1996), there have been a number of cryptographic schemes with security provably relying on the worst-case hardness of standard lattice problems, such as the decision Gap Shortest Vector Problem. Lattice-based cryptographic schemes enjoy unmatched security guarantees: Even with a quantum computer, security relies on worst-case hardness assumptions for problems expected to be exponentially hard to solve. Meanwhile, as the basic operations are matrix-vector multiplications, they often enjoy great asymptotic efficiency. At CRYPTO 2014, Ling et al. (2014) first proposed a new problem called k-LWE problem and based on this hardness result, they presented the first algebraic construction of a traitor tracing scheme in the bounded collusion model, whose security relies on the worst-case hardness of standard lattice problems. Their scheme not only can resist the attack from a quantum computer but also achieves public traceability without linear loss in efficiency. However, their scheme exposes a defect on the efficiency of trapdoor function, that is, the trapdoor generation and preimage sampling algorithm are rather complex and not very suitable for practice, in either runtime or the “quality” (The quality of a trapdoor roughly corresponds to the Euclidean lengths of its vectors — shorter is better.) of their outputs. Moreover, when the total number of users N is large, the extracting algorithm for all user’s keys should be executed N times, which severely influences the cryptosystem’s efficiency.