An Improved Encryption Scheme for Traitor Tracing from Lattice

An Improved Encryption Scheme for Traitor Tracing from Lattice

Qing Ye, Mingxing Hu, Guangxuan Chen, Panke Qin
Copyright: © 2018 |Pages: 15
DOI: 10.4018/IJDCF.2018100102
(Individual Articles)
No Current Special Offers


This article first describes a paper by Ling, Phan, and Stehle at the CRYPTO 2014 which presented the first encryption scheme for traitor tracing from lattice, and the scheme is almost as efficient as the learning with errors (LWE) encryption. However, their scheme is not constructed on an efficient trapdoor, that is, the trapdoor generation and preimage sampling algorithms are rather complex and not suitable for practice. This article is considered to use the MP12 trapdoor to construct an improved traitor tracing scheme. First, by using batch execution method, this article proposes an improved extracting algorithm for the user's key. Then, this article combines that with multi-bit encryption system to construct an efficient one-to-many encryption scheme. Furthermore, it is presented that a novel projective sampling family has very small hidden constants. Finally, a comparative analysis shows that the parameters of the scheme such as lattice dimension, trapdoor size, and ciphertext expansion rate, etc., all decrease in some degree, and the computational cost is reduced.
Article Preview

1. 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 IJDCF.2018100102.m01, 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.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2023)
Volume 14: 3 Issues (2022)
Volume 13: 6 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing