{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:37:08Z","timestamp":1787341028698,"version":"build-2736575974"},"reference-count":81,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["Contract N00014-11-1-0382"],"award-info":[{"award-number":["Contract N00014-11-1-0382"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1414082"],"award-info":[{"award-number":["CNS-1414082"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>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 a 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 superpolynomial modulus-to-noise ratio.<\/jats:p>","DOI":"10.1137\/18m1197825","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T12:23:57Z","timestamp":1572956637000},"page":"STOC18-94-STOC18-241","source":"Crossref","is-referenced-by-count":4,"title":["Collusion Resistant Traitor Tracing from Learning with Errors"],"prefix":"10.1137","volume":"49","author":[{"given":"Rishab","family":"Goyal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkata","family":"Koppula","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brent","family":"Waters","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"key":"atypb1","first-page":"98","author":"Agrawal S.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb2","first-page":"2277","author":"Agrawal S.","year":"2017","journal-title":"TX"},{"key":"atypb3","first-page":"595","author":"Applebaum B.","year":"2009","journal-title":"CRYPTO"},{"key":"atypb4","unstructured":"D. Apon, N. D\u00f6ttling, S. Garg, and P. Mukherjee,\n                      Cryptanalysis of Indistinguishability Obfuscations of Circuits over GGH\\textup13\n                      , Cryptology ePrint Archive, Report 2016\/1003, 2016."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"M. Abdalla, A. W. Dent, J. Malone-Lee, G. Neven, D. H. Phan, and N. P. Smart,\n                      Identity-based traitor tracing\n                      , in Proceedings of the Public Key Cryptography, PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, China, 2007, pp. 361-376.","DOI":"10.1007\/978-3-540-71677-8_24"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"S. Agrawal, S. Gorbunov, V. Vaikuntanathan, and H. Wee,\n                      Functional encryption: New perspectives and lower bounds\n                      , in Proceedings of the 33rd Annual Cryptology Conference Advances in Cryptology - CRYPTO 2013, Part II, Santa Barbara, CA, 2013, pp. 500-518.","DOI":"10.1007\/978-3-642-40084-1_28"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"M. Ajtai,\n                      Generating hard instances of the short basis problem\n                      , in Proceedings of the 26th International Colloquium on Automata, Languages and Programming, Prague, Czech Republic, ICALP'99, 1999, pp. 1-9.","DOI":"10.1007\/3-540-48523-6_1"},{"key":"atypb8","unstructured":"G. Asharov, A. Jain, and D. Wichs,\n                      Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE\n                      , Cryptology ePrint Archive, Report 2011\/613, 2011,http:\/\/eprint.iacr.org\/2011\/613."},{"key":"atypb9","first-page":"333","author":"Agrawal S.","year":"2016","journal-title":"Berlin"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"D. A. Barrington,\n                      Bounded-width polynomial-size branching programs recognize exactly those languages in NC$^1$\n                      , in Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, 1986, pp. 1-5.","DOI":"10.1145\/12130.12131"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/0215040"},{"key":"atypb12","first-page":"1","author":"Barak B.","year":"2011","journal-title":"Springer"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"D. Boneh and M. K. Franklin,\n                      An efficient public key traitor tracing scheme\n                      , in Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology - CRYPTO'99, Santa Barbara, CA, 1999, pp. 338-353.","DOI":"10.1007\/3-540-48405-1_22"},{"key":"atypb14","first-page":"1","author":"Boneh D.","year":"2011","journal-title":"Heidelberg"},{"key":"atypb15","first-page":"141","author":"Brakerski Z.","year":"2011","journal-title":"Springer"},{"key":"atypb16","first-page":"533","author":"Boneh D.","year":"2014","journal-title":"Denmark"},{"key":"atypb17","unstructured":"Z. Brakerski, C. Gentry, S. Halevi, T. Lepoint, A. Sahai, and M. Tibouchi,\n                      Cryptanalysis of the Quadratic Zero-Testing of GGH\n                      , IACR Cryptology ePrint Archive, 2015."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"D. Boneh, K. Lewi, H. W. Montgomery, and A. Raghunathan,\n                      Key homomorphic PRFs and their applications\n                      , in Advances in Cryptology - CRYPTO 2013, 33rd Annual Cryptology Conference, Part I, Santa Barbara, CA, 2013, pp. 410-428.","DOI":"10.1007\/978-3-642-40041-4_23"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehl\u00e9,\n                      Classical hardness of learning with errors\n                      , in Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, 2013, pp. 575-584.","DOI":"10.1145\/2488608.2488680"},{"key":"atypb20","first-page":"535","author":"Brakerski Z.","year":"2018","journal-title":"Springer"},{"key":"atypb21","first-page":"501","author":"Boneh D.","year":"2008","journal-title":"VA"},{"key":"atypb22","first-page":"171","author":"Billet O.","year":"2008","journal-title":"Canada"},{"key":"atypb23","first-page":"306","author":"Brakerski Z.","year":"2015","journal-title":"Poland"},{"key":"atypb24","first-page":"573","author":"Boneh D.","year":"2006","journal-title":"EUROCRYPT"},{"key":"atypb25","first-page":"171","volume":"2015","author":"Bitansky N.","year":"2015","journal-title":"Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840764"},{"key":"atypb27","first-page":"211","author":"Boneh D.","year":"2006","journal-title":"VA"},{"key":"atypb28","unstructured":"D. Boneh, D. J. Wu, and J. Zimmerman,\n                      Immunizing Multilinear Maps against Zeroizing Attacks\n                      , Cryptology ePrint Archive, Report 2014\/930, 2014."},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"D. Boneh and M. Zhandry,\n                      Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation\n                      , in Proceedings of the 34th Annual Cryptology Conference Advances in Cryptology - CRYPTO 2014, Part I, Santa Barbara, CA, 2014, pp. 480-499.","DOI":"10.1007\/978-3-662-44371-2_27"},{"key":"atypb30","first-page":"446","author":"Canetti R.","year":"2017","journal-title":"EUROCRYPT"},{"key":"atypb31","first-page":"509","author":"Cheon J. H.","year":"2016","journal-title":"Berlin"},{"key":"atypb32","first-page":"257","author":"Chor B.","year":"1994","journal-title":"Heidelberg"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/18.841169"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"J.S. Coron, C. Gentry, S. Halevi, T. Lepoint, H. K. Maji, E. Miles, M. Raykova, A. Sahai, and M. Tibouchi,\n                      Zeroizing without low-level zeroes: New MMAP attacks and their limitations\n                      , in Proceedings of the 35th Annual Cryptology Conference, Advances in Cryptology - CRYPTO 2015, Part I, Santa Barbara, CA, 2015, pp. 247-266.","DOI":"10.1007\/978-3-662-47989-6_12"},{"key":"atypb35","first-page":"523","author":"Cash D.","year":"2010","journal-title":"French Riviera"},{"key":"atypb36","first-page":"3","author":"Cheon J. H.","year":"2015","journal-title":"Bulgaria"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157016000371"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"J.S. Coron, M. S. Lee, T. Lepoint, and M. Tibouchi,\n                      \n                        Cryptanalysis of GGH\n                        15\n                        multilinear maps\n                      \n                      , in Proceedings of the 36th Annual International Cryptology Conference, Advances in Cryptology - CRYPTO 2016, Part II, Santa Barbara, CA, 2016, pp. 607-628.","DOI":"10.1007\/978-3-662-53008-5_21"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"J.S. Coron, M. S. Lee, T. Lepoint, and M. Tibouchi,\n                      Zeroizing attacks on indistinguishability obfuscation over CLT$_{13}$\n                      , in Proceedings of the 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Public-Key Cryptography, PKC 2017, Part I, Amsterdam, The Netherlands, 2017, pp. 41-58.","DOI":"10.1007\/978-3-662-54365-8_3"},{"key":"atypb40","unstructured":"J.S. Coron, T. Lepoint, and M. Tibouchi,\n                      Cryptanalysis of Two Candidate Fixes of Multilinear Maps over the Integers\n                      , Cryptology ePrint Archive, Report 2014\/975, 2014."},{"key":"atypb41","first-page":"542","author":"Chabanne H.","year":"2005","journal-title":"Denmark"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"Y. Chen, V. Vaikuntanathan, B. Waters, H. Wee, and D. Wichs,\n                      Traitor-tracing from LWE made simple and attribute-based\n                      , in Proceedings of the 16th International Conference, Theory of Cryptography, TCC 2018, Part II, Panaji, India, 2018, pp. 341-369.","DOI":"10.1007\/978-3-030-03810-6_13"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"Y. Chen, V. Vaikuntanathan, and H. Wee,\n                      GGH$15$ beyond permutation branching programs: Proofs, attacks, and candidates\n                      , in Proceedings of the 38th Annual International Cryptology Conference, Advances in Cryptology - CRYPTO 2018, Part II, Santa Barbara, CA, 2018, pp. 577-607.","DOI":"10.1007\/978-3-319-96881-0_20"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"N. D\u00f6ttling and S. Garg,\n                      Identity-based encryption from the Diffie-Hellman assumption\n                      , in Proceedings of the 37th Annual International Cryptology Conference, Advances in Cryptology - CRYPTO 2017, Part I, Santa Barbara, CA, 2017, pp. 537-569.","DOI":"10.1007\/978-3-319-63688-7_18"},{"key":"atypb45","first-page":"372","author":"D\u00f6ttling N.","year":"2017","journal-title":"Cham"},{"key":"atypb46","first-page":"265","volume":"2006","author":"Dwork C.","year":"2006","journal-title":"TCC"},{"key":"atypb47","first-page":"381","author":"Dwork C.","year":"2009","journal-title":"New York"},{"key":"atypb48","first-page":"1","author":"Dodis Y.","year":"2013","journal-title":"Springer"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"N. Fazio, A. Nicolosi, and D. H. Phan,\n                      Traitor tracing with optimal transmission rate\n                      , in Proceedings of the 10th International Conference on Information Security, ISC 2007, Valpara\u00edso, Chile, 2007, pp. 71-88.","DOI":"10.1007\/978-3-540-75496-1_5"},{"key":"atypb50","first-page":"44","author":"Freeman D. M.","year":"2010","journal-title":"Heidelberg"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/14095772X"},{"key":"atypb52","first-page":"498","author":"Gentry C.","year":"2015","journal-title":"Heidelberg"},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y. Kalai, R. A. Popa, V. Vaikuntanathan, and N. Zeldovich,\n                      Reusable garbled circuits and succinct functional encryption\n                      , in Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC'13, 2013, pp. 555-564.","DOI":"10.1145\/2488608.2488678"},{"key":"atypb54","first-page":"467","author":"Goyal R.","year":"2018","journal-title":"Springer"},{"key":"atypb55","first-page":"121","author":"Garg S.","year":"2010","journal-title":"New York"},{"key":"atypb56","first-page":"612","volume":"2017","author":"Goyal R.","year":"2017","journal-title":"FOCS"},{"key":"atypb57","first-page":"528","author":"Goyal R.","year":"2017","journal-title":"Cham"},{"key":"atypb58","first-page":"197","author":"Gentry C.","year":"2008","journal-title":"New York"},{"key":"atypb59","first-page":"162","author":"Gorbunov S.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb60","first-page":"545","author":"Gorbunov S.","year":"2013","journal-title":"New York"},{"key":"atypb61","first-page":"503","author":"Gorbunov S.","year":"2015","journal-title":"Heidelberg"},{"key":"atypb62","unstructured":"S. Halevi,\n                      Graded Encoding, Variations on a Scheme\n                      , Cryptology ePrint Archive, Report 2015\/866, 2015."},{"key":"atypb63","first-page":"537","author":"Hu Y.","year":"2016","journal-title":"Berlin"},{"key":"atypb64","first-page":"145","author":"Kurosawa K.","year":"1998","journal-title":"Finland"},{"key":"atypb65","first-page":"437","author":"Kowalczyk L.","year":"2018","journal-title":"Springer"},{"key":"atypb66","first-page":"450","author":"Kiayias A.","year":"2002","journal-title":"The Netherlands"},{"key":"atypb67","first-page":"172","volume":"2002","author":"Kurosawa K.","year":"2002","journal-title":"PKC"},{"key":"atypb68","doi-asserted-by":"crossref","unstructured":"S. Ling, D. H. Phan, D. Stehl\u00e9, and R. Steinfeld,\n                      Hardness of k-LWE and applications in traitor tracing\n                      , in Proceedings of the 34th Annual Cryptology Conference, Advances in Cryptology - CRYPTO 2014, Part I, Santa Barbara, CA, 2014, pp. 315-334.","DOI":"10.1007\/978-3-662-44371-2_18"},{"key":"atypb69","first-page":"700","author":"Micciancio D.","year":"2012","journal-title":"UK"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"atypb71","first-page":"629","author":"Miles E.","year":"2016","journal-title":"Heidelberg"},{"key":"atypb72","first-page":"502","author":"Naor M.","year":"1998","journal-title":"Springer"},{"key":"atypb73","first-page":"388","author":"Nishimaki R.","year":"2016","journal-title":"Part"},{"key":"atypb74","first-page":"333","volume":"2009","author":"Peikert C.","year":"2009","journal-title":"STOC"},{"key":"atypb75","first-page":"264","author":"Phan D. H.","year":"2006","journal-title":"Italy"},{"key":"atypb76","first-page":"84","author":"Regev O.","year":"2005","journal-title":"MD"},{"key":"atypb77","first-page":"463","author":"Sahai A.","year":"2010","journal-title":"New York"},{"key":"atypb78","doi-asserted-by":"publisher","DOI":"10.1109\/18.915661"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196304246"},{"key":"atypb80","first-page":"600","volume":"2017","author":"Wichs D.","year":"2017","journal-title":"FOCS"},{"key":"atypb81","first-page":"162","author":"Yao A.","year":"1986","journal-title":"Canada"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1197825","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:02:19Z","timestamp":1787338939000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1197825"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":81,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1197825"],"URL":"https:\/\/doi.org\/10.1137\/18m1197825","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,5]]}}}