Collusion resistant traitor tracing from learning with errors

ABSTRACT

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, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions.

We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts.

We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class logspace) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.

References

1. Michel Abdalla, Alexander W. Dent, John Malone-Lee, Gregory Neven, Duong Hieu Phan, and Nigel P. Smart. 2007. Identity-Based Traitor Tracing. In Public Key Cryptography - PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, April 16-20, 2007, Proceedings. 361–376.
2. Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehlé, and Shota Yamada. 2017. Efficient Public Trace and Revoke from Standard Assumptions: Extended Abstract. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017. 2277–2293.
3. Shweta Agrawal, Dan Boneh, and Xavier Boyen. 2010. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In Proceedings of the 30th annual conference on Advances in cryptology (CRYPTO’10). Springer-Verlag, Berlin, Heidelberg, 98–115. http://dl.acm.org/citation.cfm?id=1881412.1881420
4. Shweta Agrawal, Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. Functional Encryption: New Perspectives and Lower Bounds. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II. 500–518.
5. Miklós Ajtai. 1999. Generating Hard Instances of the Short Basis Problem. In Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings. 1–9.
6. Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee. 2016. Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH13. Cryptology ePrint Archive, Report 2016/1003. (2016).
7. STOC’18, June 25–29, 2018, Los Angeles, CA, USA Rishab Goyal, Venkata Koppula, Brent Waters
8. Olivier Billet and Duong Hieu Phan. 2008. Efficient Traitor Tracing from Collusion Secure Codes. In Information Theoretic Security, Third International Conference, ICITS 2008, Calgary, Canada, August 10-13, 2008, Proceedings. 171–182.
9. Nir Bitansky and Vinod Vaikuntanathan. 2015. Indistinguishability Obfuscation from Functional Encryption. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 171–190.
10. Dan Boneh and Matthew K. Franklin. 1999. An Efficient Public Key Traitor Tracing Scheme. In Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings. 338–353.
11. Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. 2014. Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits. In Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings. 533–556.
12. Dan Boneh and Moni Naor. 2008. Traitor tracing with constant size ciphertext. In Proceedings of the 2008 ACM Conference on Computer and Communications Security, CCS 2008, Alexandria, Virginia, USA, October 27-31, 2008. 501–510.
13. Dan Boneh, Amit Sahai, and Brent Waters. 2006. Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys. In EUROCRYPT. 573–592.
14. Dan Boneh and Brent Waters. 2006. A fully collusion resistant broadcast, trace, and revoke system. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS 2006, Alexandria, VA, USA, Ioctober 30 - November 3, 2006. 211–220.
15. Dan Boneh, David J. Wu, and Joe Zimmerman. 2014. Immunizing Multilinear Maps Against Zeroizing Attacks. Cryptology ePrint Archive, Report 2014/930. (2014).
16. Dan Boneh and Mark Zhandry. 2014. Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation. In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I. 480–499. 978-3-662-44371-2_27
17. Zvika Brakerski, Craig Gentry, Shai Halevi, Tancrède Lepoint, Amit Sahai, and Mehdi Tibouchi. 2015. Cryptanalysis of the Quadratic Zero-Testing of GGH. IACR Cryptology ePrint Archive (2015).
18. Zvika Brakerski, Alex Lombardi, Gil Segev, and Vinod Vaikuntanathan. 2017. Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions. Cryptology ePrint Archive, Report 2017/967. (2017). http://eprint.iacr.org/ 2017/967.
19. Zvika Brakerski and Gil Segev. 2015. Function-Private Functional Encryption in the Private-Key Setting. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II. 306–324.
20. Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. 2016. Obfuscating conjunctions under entropic ring LWE. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science.
21. Ran Canetti and Yilei Chen. 2017. Constraint-hiding Constrained PRFs for NC1 from LWE. In EUROCRYPT.
22. David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. 2010. Bonsai Trees, or How to Delegate a Lattice Basis. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30 - June 3, 2010. Proceedings. 523–552.
23. Hervé Chabanne, Duong Hieu Phan, and David Pointcheval. 2005. Public Traceability in Traitor Tracing Schemes. In Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings. 542–558.
24. Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, and Hansol Ryu. 2016. Cryptanalysis of the new CLT multilinear map over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques.
25. Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. 2015. Cryptanalysis of the Multilinear Map over the Integers. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. 3–12.
26. Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. 2016. An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a lowlevel encoding of zero. LMS Journal of Computation and Mathematics (2016).
27. Benny Chor, Amos Fiat, and Moni Naor. 1994. Tracing Traitors. In CRYPTO. 257–270.
28. Benny Chor, Amos Fiat, Moni Naor, and Benny Pinkas. 2000. Tracing traitors. IEEE Trans. Information Theory 46, 3 (2000), 893–910.
29. Jean-Sébastien Coron, Craig Gentry, Shai Halevi, Tancrède Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi. 2015. Zeroizing Without Low-Level Zeroes: New MMAP Attacks and their Limitations. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I.
30. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. 2016. Cryptanalysis of GGH15 Multilinear Maps. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II.
31. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. 2017. Zeroizing Attacks on Indistinguishability Obfuscation over CLT13. In Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I.
32. Jean-Sebastien Coron, Tancrede Lepoint, and Mehdi Tibouchi. 2014. Cryptanalysis of Two Candidate Fixes of Multilinear Maps over the Integers. Cryptology ePrint Archive, Report 2014/975. (2014).
33. Nico Döttling and Sanjam Garg. 2017. Identity-Based Encryption from the Diffie-Hellman Assumption. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I. 537–569.
34. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings. 265–284.
35. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. 2009. On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (STOC ’09). ACM, New York, NY, USA, 381–390.
36. Nico DÃűttling and Sanjam Garg. 2017. From Selective IBE to Full IBE and Selective HIBE. TCC. (2017).
37. Nelly Fazio, Antonio Nicolosi, and Duong Hieu Phan. 2007. Traitor Tracing with Optimal Transmission Rate. In Information Security, 10th International Conference, ISC 2007, Valparaíso, Chile, October 9-12, 2007, Proceedings. 71–88. org/10.1007/978-3-540-75496-1_5
38. David Mandell Freeman. 2010. Converting Pairing-based Cryptosystems from Composite-order Groups to Prime-order Groups. In Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT’10). Springer-Verlag, Berlin, Heidelberg, 44–61. 1007/978-3-642-13190-5_3
39. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. 2013. Candidate Indstinguishability Obfuscation and Functional Encryption for all circuits. In FOCS.
40. Sanjam Garg, Abishek Kumarasubramanian, Amit Sahai, and Brent Waters. 2010. Building Efficient Fully Collusion-resilient Traitor Tracing and Revocation Schemes. In Proceedings of the 17th ACM Conference on Computer and Communications Security (CCS ’10). ACM, New York, NY, USA, 121–130.
41. Craig Gentry, Sergey Gorbunov, and Shai Halevi. 2015. Graph-Induced Multilinear Maps from Lattices. In TCC.
42. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In STOC. 197–206.
43. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2012. Functional Encryption with Bounded Collusions via Multi-party Computation. In CRYPTO.
44. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. 2013. Attributebased Encryption for Circuits. In STOC.
45. Rishab Goyal, Venkata Koppula, Andrew Russell, and Brent Waters. 2017. Risky Traitor Tracing and New Differential Privacy Negative Results. Cryptology ePrint Archive, Report 2017/1117. (2017).
46. Rishab Goyal, Venkata Koppula, and Brent Waters. 2017. Lockable Obfuscation. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017.
47. 612–621.
48. Rishab Goyal, Venkata Koppula, and Brent Waters. 2017. Separating Semantic and Circular Security for Symmetric-Key Bit Encryption from the Learning with Errors Assumption. In EUROCRYPT.
49. Shai Halevi. 2015. Graded Encoding, Variations on a Scheme. Cryptology ePrint Archive, Report 2015/866. (2015).
50. Yupu Hu and Huiwen Jia. 2016. Cryptanalysis of GGH map. In Annual International Conference on the Theory and Applications of Cryptographic Techniques.
51. Aggelos Kiayias and Moti Yung. 2002. Traitor Tracing with Constant Transmission Rate. In Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings. 450–465.
52. Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Daniel Wichs. 2017. Hardness of Non-Interactive Differential Privacy from One-Way Functions. Cryptology ePrint Archive, Report 2017/1107. (2017).
53. Collusion Resistant Traitor Tracing from Learning with Errors STOC’18, June 25–29, 2018, Los Angeles, CA, USA
54. Kaoru Kurosawa and Yvo Desmedt. 1998. Optimum Traitor Tracing and Asymmetric Schemes. In Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding. 145–157.
55. Kaoru Kurosawa and Takuya Yoshida. 2002. Linear Code Implies Public-Key Traitor Tracing. In Public Key Cryptography, 5th International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2002, Paris, France, February 12-14, 2002, Proceedings. 172–187.
56. San Ling, Duong Hieu Phan, Damien Stehlé, and Ron Steinfeld. 2014. Hardness of k-LWE and Applications in Traitor Tracing. In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I. 315–334.
57. Daniele Micciancio and Chris Peikert. 2012. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings. 700–718.
58. Eric Miles, Amit Sahai, and Mark Zhandry. 2016. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. In Annual Cryptology Conference.
59. Moni Naor and Benny Pinkas. 1998. Threshold traitor tracing. In Advances in CryptologyâĂŤCRYPTO’98. Springer, 502–517.
60. Duong Hieu Phan, Reihaneh Safavi-Naini, and Dongvu Tonien. 2006. Generic Construction of Hybrid Public Key Traitor Tracing with Full-Public-Traceability. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II. 264–275.
61. Amit Sahai and Hakan Seyalioglu. 2010. Worry-free encryption: functional encryption with public keys. In Proceedings of the 17th ACM conference on Computer and communications security (CCS ’10). ACM, New York, NY, USA, 463–472.
62. Jessica Staddon, Douglas R. Stinson, and Ruizhong Wei. 2001. Combinatorial properties of frameproof and traceability codes. IEEE Trans. Information Theory 47, 3 (2001), 1042–1049.
63. Douglas R. Stinson and Ruizhong Wei. 1998. Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes. SIAM J. Discrete Math. 11, 1 (1998), 41–53.
64. Daniel Wichs and Giorgos Zirdelis. 2017. Obfuscating Compute-and-Compare Programs under LWE. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. 600–611.
65. Andrew Yao. 1986. How to Generate and Exchange Secrets. In FOCS. 162–167. Abstract 1 Introduction 1.1 Technical Overview 1.2 Some Future Directions 1.3 Additional Related Work References

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption

  • Security services

    • Pseudonymity, anonymity and untraceability