Abstract
Traitor tracing schemes are a very useful tool for preventing piracy in digital content distribution systems. A traitor tracing procedure allows the system-manager to reveal the identities of the subscribers that were implicated in the construction of a pirate-device that illegally receives the digital content (called traitors). In an important variant called “asymmetric” traitor tracing, the system-manager is not necessarily trusted, thus the tracing procedure must produce undeniable proof of the implication of the traitor subscribers. This non-repudiation property of asymmetric schemes has the potential to significantly increase the effectiveness of the tracing procedure against piracy.
In this work, we break the two previous proposals for efficient asymmetric public-key traitor tracing, by showing how traitors can evade the proposed traitor tracing procedures. Then, we present a new efficient Asymmetric Public-Key Traitor Tracing scheme for which we prove its traceability in detail (in the non-black-box model); to the best of our knowledge this is the first such scheme. Our system is capable of proving the implication of all traitors that participate in the construction of a pirate-key. We note that even though we break the earlier schemes we employ some of their fundamental techniques and thus consider them important developments towards the solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Canal Plus files $ 1 billion lawsuit on News Corp arm, Reuters, 03.12.02, 7:46 PM ET, Also http://www.wired.com/news/politics/0,1283,51005,00.html
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (Im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 1. Springer, Heidelberg (2001)
Berlekamp, E.R., Welch, L.: Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 (1986)
Boneh, D., Franklin, M.: An Efficient Public Key Traitor Tracing Scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 338. Springer, Heidelberg (1999)
Boneh, D., Franklin, M.: An Efficient Public Key Traitor Tracing Scheme (2001) (manuscript, full-version of [4])
Brands, S.: Rethinking Public Key Infrastructures and Digital Certificates – Building in Privacy, Ph.D. thesis, Technical University of Eindhoven (1999)
Chang, Y.-C., Lu, C.-J.: Oblivious Polynomial Evaluation and Oblivious Neural Learning. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, p. 369. Springer, Heidelberg (2001)
Chor, B., Fiat, A., Naor, M.: Tracing Traitors. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 257–270. Springer, Heidelberg (1994)
Chor, B., Fiat, A., Naor, M., Pinkas, B.: Tracing Traitors. IEEE Transactions on Information Theory 46(3), 893–910 (2000)
Cramer, R., Shoup, V.: A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, p. 13. Springer, Heidelberg (1998)
Daemen, J., Rijmen, V.: The design of Rijndael-AES the advanced encryption standard. Springer, Heidelberg (2002)
Fiat, A., Naor, M.: Broadcast Encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Gafni, E., Staddon, J., Yin, Y.L.: Efficient methods for integrating traceability and broadcast encryption. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, p. 372. Springer, Heidelberg (1999)
Guruswami, V., Sudan, M.: Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. In: The Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 28–39. IEEE Computer Society, Los Alamitos (1998)
Kiayias, A., Yung, M.: Self Protecting Pirates and Black-Box Traitor Tracing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 63. Springer, Heidelberg (2001)
Kiayias, A., Yung, M.: Traitor Tracing with Constant Transmission Rate. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, p. 450. Springer, Heidelberg (2002)
Kiayias, A., Yung, M.: Robust Malleable Oblivious Polynomial Evaluation (manuscript)
Kiayias, A., Yung, M.: Cryptographic Hardness Based on the Decoding of Reed-Solomon Codes. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, p. 232. Springer, Heidelberg (2002)
Komaki, H., Watanabe, Y., Hanaoka, G., Imai, H.: Efficient Asymmetric Self-Enforcement Scheme with Public Traceability. In: Public Key Cryptography (2001)
Kurosawa, K., Desmedt, Y.: Optimum Traitor Tracing and Asymmetric Schemes. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 145–157. Springer, Heidelberg (1998)
MacWilliams, F.J., Sloane, N.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1977)
Naor, D., Naor, M., Lotspiech, J.B.: Revocation and tracing schemes for stateless receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 41. Springer, Heidelberg (2001)
Naor, M., Pinkas, B.: Oblivious Transfer and Polynomial Evaluation. In: The Proceedings of the 31th ACM Symposium on the Theory of Computing (1999) (Full version available from authors)
Naor, M., Pinkas, B.: Efficient Trace and Revoke Schemes. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, p. 1. Springer, Heidelberg (2001)
Pfitzmann, B.: Trials of Traced Traitors. In: Anderson, R. (ed.) IH 1996. LNCS, vol. 1174, pp. 49–63. Springer, Heidelberg (1996)
Pfitzmann, B., Schunter, M.: Asymmetric fingerprinting. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 84–95. Springer, Heidelberg (1996)
Pfitzmann, B., Waidner, M.: Asymmetric fingerprinting for larger collusions. In: Proc. ACM Conference on Computer and Communication Security, pp. 151–160 (1997)
Sander, T., Tschudin, C.F.: On Software Protection via Function Hiding. Information Hiding (1998)
Stinson, D., Wei, R.: Key preassigned traceability schemes for broadcast encryption. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 144–156. Springer, Heidelberg (1999)
Stinson, D.R., Wei, R.: Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes. SIAM J. on Discrete Math. 11(1) (1998)
Watanabe, Y., Hanaoka, G., Imai, H.: Efficient Asymmetric Public-Key Traitor Tracing without Trusted Agents. In: CT-RSA 2001 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kiayias, A., Yung, M. (2003). Breaking and Repairing Asymmetric Public-Key Traitor Tracing. In: Feigenbaum, J. (eds) Digital Rights Management. DRM 2002. Lecture Notes in Computer Science, vol 2696. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-44993-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-44993-5_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40410-1
Online ISBN: 978-3-540-44993-5
eBook Packages: Springer Book Archive