{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T20:33:11Z","timestamp":1764621191815,"version":"3.46.0"},"publisher-location":"Cham","reference-count":66,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032122926","type":"print"},{"value":"9783032122933","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T00:00:00Z","timestamp":1764633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-12293-3_12","type":"book-chapter","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T20:28:15Z","timestamp":1764620895000},"page":"365-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Simplified PIR and\u00a0CDS Protocols and\u00a0Improved Linear Secret-Sharing Schemes"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8392-0245","authenticated-orcid":false,"given":"Bar","family":"Alon","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6572-4195","authenticated-orcid":false,"given":"Amos","family":"Beimel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7419-1454","authenticated-orcid":false,"given":"Or","family":"Lasri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44987-6_8","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2001","author":"B Aiello","year":"2001","unstructured":"Aiello, B., Ishai, Y., Reingold, O.: Priced oblivious transfer: how to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119\u2013135. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44987-6_8"},{"key":"12_CR2","unstructured":"Alon, B., Beimel, A., Lasri, O.: Simplified PIR and CDS protocols and improved linear secret-sharing schemes. Cryptology ePrint Archive, Paper 2024\/1599 (2024)"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Upper bound on the communication complexity of private information retrieval. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) Proceedings of the 24th International Colloquium on Automata, Languages and Programming. LNCS, vol. 1256, pp. 401\u2013407 (1997)","DOI":"10.1007\/3-540-63165-8_196"},{"key":"12_CR4","unstructured":"Amran, H.: Constructing multi-servers private information retrieval protocols. Master\u2019s thesis, Ben-Gurion University (2016)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Arkis, B.: On the power of amortization in secret sharing: d-uniform secret sharing and CDS with constant information rate. ACM Trans. Comput. Theory 12(4), 24:1\u201324:21 (2020)","DOI":"10.1145\/3417756"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/978-3-319-63688-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"B Applebaum","year":"2017","unstructured":"Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 727\u2013757. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_24"},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/18M1217097","volume":"50","author":"B Applebaum","year":"2021","unstructured":"Applebaum, B., Arkis, B., Raykov, P., Vasudevan, P.N.: Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. SIAM J. Comput. 50(1), 32\u201367 (2021)","journal-title":"SIAM J. Comput."},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-030-17659-4_15","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"B Applebaum","year":"2019","unstructured":"Applebaum, B., Beimel, A., Farr\u00e0s, O., Nir, O., Peter, N.: Secret-sharing schemes for general and uniform access structures. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 441\u2013471. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_15"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Beimel, A., Nir, O., Peter, N.: Better secret sharing via robust conditional disclosure of secrets. In: 52nd STOC, pp. 280\u2013293 (2020)","DOI":"10.1145\/3357713.3384293"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-319-78375-8_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"B Applebaum","year":"2018","unstructured":"Applebaum, B., Holenstein, T., Mishra, M., Shayevitz, O.: The communication complexity of private simultaneous messages, revisited. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 261\u2013286. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_9"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/978-3-030-84252-9_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"B Applebaum","year":"2021","unstructured":"Applebaum, B., Nir, O.: Upslices, downslices, and secret-sharing with complexity of $$1.5^n$$. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 627\u2013655. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_21"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/978-3-642-55220-5_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"N Attrapadung","year":"2014","unstructured":"Attrapadung, N.: Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 557\u2013577. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_31"},{"issue":"3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930050058","volume":"19","author":"L Babai","year":"1999","unstructured":"Babai, L., G\u00e1l, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19(3), 301\u2013319 (1999)","journal-title":"Combinatorica"},{"key":"12_CR14","unstructured":"Beimel, A.: Secret-sharing schemes for general access structures: an introduction. Cryptology ePrint Archive, Paper 2025\/518 (2025)"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-030-64381-2_18","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2020","unstructured":"Beimel, A., Farr\u00e0s, O.: The share size of secret-sharing schemes for almost all access structures and graphs. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 499\u2013529. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64381-2_18"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Beimel, A., Farr\u00e0s, O., Lasri, O.: Improved polynomial secret-sharing schemes. Cryptology ePrint Archive, Paper 2023\/1158 (2023)","DOI":"10.1007\/978-3-031-48618-0_13"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Beimel, A., G\u00e1l, A., Paterson, M.: Lower bounds for monotone span programs. Research Series BRICS-RS-94-46, BRICS, Department of Computer Science, University of Aarhus (1994)","DOI":"10.7146\/brics.v1i46.21596"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1007\/3-540-48224-5_74","volume-title":"Automata, Languages and Programming","author":"A Beimel","year":"2001","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: a unified construction. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 912\u2013926. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_74"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-54242-8_14","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2014","unstructured":"Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317\u2013342. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share conversion and private information retrieval. In: Proceedings of the 27th Conference on Computational Complexity, CCC 2012, pp. 258\u2013268 (2012)","DOI":"10.1109\/CCC.2012.23"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/978-3-030-84252-9_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"A Beimel","year":"2021","unstructured":"Beimel, A., Othman, H., Peter, N.: Quadratic secret sharing and conditional disclosure of secrets. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 748\u2013778. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_25"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-030-03332-3_13","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2018","author":"A Beimel","year":"2018","unstructured":"Beimel, A., Peter, N.: Optimal linear multiparty conditional disclosure of secrets protocols. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 332\u2013362. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03332-3_13"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/0-387-34799-2_3","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 88","author":"J Benaloh","year":"1990","unstructured":"Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27\u201335. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34799-2_3"},{"key":"12_CR24","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Managing Requirements Knowledge, International Workshop on, p. 313. IEEE Computer Society (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the 1979 AFIPS National Computer Conference, vol. 48, pp. 313\u2013317 (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"issue":"1","key":"12_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00037-011-0017-1","volume":"22","author":"YM Chee","year":"2013","unstructured":"Chee, Y.M., Feng, T., Ling, S., Wang, H., Zhang, L.F.: Query-efficient locally decodable codes of subexponential length. Comput. Complex. 22(1), 159\u2013189 (2013)","journal-title":"Comput. Complex."},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pp. 41\u201351 (1995). Journal version: J. ACM 45, 965\u2013981 (1998)","DOI":"10.1145\/293347.293350"},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Pitassi, T., Robere, T., Rossman, B.: Exponential lower bounds for monotone span programs. In: 57th FOCS, pp. 406\u2013415 (2016)","DOI":"10.1109\/FOCS.2016.51"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-45539-6_22","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2000","author":"R Cramer","year":"2000","unstructured":"Cramer, R., Damg\u00e5rd, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316\u2013334. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45539-6_22"},{"issue":"3\u20134","key":"12_CR30","first-page":"429","volume":"32","author":"L Csirmaz","year":"1996","unstructured":"Csirmaz, L.: The dealer\u2019s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32(3\u20134), 429\u2013437 (1996)","journal-title":"Studia Sci. Math. Hungar."},{"issue":"4","key":"12_CR31","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s001459900029","volume":"10","author":"L Csirmaz","year":"1997","unstructured":"Csirmaz, L.: The size of a share must be large. J. Cryptol. 10(4), 223\u2013231 (1997)","journal-title":"J. Cryptol."},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, 23\u201326 October 2010, Las Vegas, Nevada, USA, pp. 705\u2013714. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.73"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Gopi, S.: 2-server PIR with sub-polynomial communication. In: 47th STOC, pp. 577\u2013584 (2015)","DOI":"10.1145\/2746539.2746546"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Gopi, S.: 2-server PIR with subpolynomial communication. J. ACM 63(4), 39:1\u201339:15 (2016)","DOI":"10.1145\/2968443"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. Technical report TR08-069, Electronic Colloquium on Computational Complexity (2008). www.eccc.uni-trier.de\/eccc\/","DOI":"10.1145\/1536414.1536422"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39\u201344 (2009)","DOI":"10.1145\/1536414.1536422"},{"issue":"6","key":"12_CR37","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1137\/090772721","volume":"41","author":"K Efremenko","year":"2012","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41(6), 1694\u20131703 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"12_CR38","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0012-365X(96)00124-0","volume":"170","author":"P Erd\u00f6s","year":"1997","unstructured":"Erd\u00f6s, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discret. Math. 170(1\u20133), 249\u2013251 (1997)","journal-title":"Discret. Math."},{"issue":"4","key":"12_CR39","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s000370100001","volume":"10","author":"A G\u00e1l","year":"2002","unstructured":"G\u00e1l, A.: A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complex. 10(4), 277\u2013296 (2002)","journal-title":"Comput. Complex."},{"key":"12_CR40","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/S0020-0190(03)00334-X","volume":"87","author":"A G\u00e1l","year":"2003","unstructured":"G\u00e1l, A., Pudl\u00e1k, P.: Monotone complexity and the rank of matrices. Inform. Process. Lett. 87, 321\u2013326 (2003)","journal-title":"Inform. Process. Lett."},{"key":"12_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-662-48000-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"R Gay","year":"2015","unstructured":"Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 485\u2013502. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_24"},{"key":"12_CR42","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. In: Proceedings of the 30th ACM Symposium on the Theory of Computing, pp. 151\u2013160 (1998). Journal version: J. Comput. Syst. Sci. 60(3), 592\u2013629 (2000)","DOI":"10.1006\/jcss.1999.1689"},{"key":"12_CR43","unstructured":"Ghasemi, F., Kopparty, S., Sudan, M.: Improved PIR schemes using matching vectors and derivatives. Technical report 2411.11611, Cryptology ePrint Archive (2024). To appear at STOC \u201925"},{"key":"12_CR44","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V Grolmusz","year":"2000","unstructured":"Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica 20, 71\u201386 (2000)","journal-title":"Combinatorica"},{"key":"12_CR45","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Improved upper bounds on information theoretic private information retrieval. In: Proceedings of the 31st ACM Symposium on the Theory of Computing, pp. 79\u201388 (1999).","DOI":"10.1145\/301250.301275"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Globecom 1987, pp. 99\u2013102 (1987). Journal version: Multiple assignment scheme for sharing secret. J. Cryptol. 6(1), 15\u201320 (1993)","DOI":"10.1007\/BF02620229"},{"key":"12_CR47","unstructured":"Itoh, T.: Efficient private information retrieval. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E82-A(1), 11\u201320 (1999)"},{"key":"12_CR48","unstructured":"Itoh, T., Suzuki, Y.: New constructions for query-efficient locally decodable codes of subexponential length. CoRR, abs\/0810.4576 (2008)"},{"key":"12_CR49","doi-asserted-by":"crossref","unstructured":"Itoh, T., Suzuki, Y.: Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Trans. Inf. Syst. E93-D(2), 263\u2013270 (2010)","DOI":"10.1587\/transinf.E93.D.263"},{"key":"12_CR50","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: 8th Structure in Complexity Theory, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"12_CR51","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: Proceedings of the 32nd ACM Symposium on the Theory of Computing, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"12_CR52","unstructured":"Kedlaya, K.S., Yekhanin, S.: Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. Technical report TR07-040, Electronic Colloquium on Computational Complexity (2007). www.eccc.uni-trier.de\/eccc\/"},{"issue":"3","key":"12_CR53","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I Kerenidis","year":"2004","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69(3), 395\u2013420 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR54","doi-asserted-by":"crossref","unstructured":"Kutin, S.: Constructing large set systems with given intersection sizes modulo composite numbers. Comb. Probab. Comput. (2002)","DOI":"10.1017\/S0963548302005242"},{"key":"12_CR55","doi-asserted-by":"crossref","unstructured":"Liu, T., Vaikuntanathan, V.: Breaking the circuit-size barrier in secret sharing. In: 50th STOC, pp. 699\u2013708 (2018)","DOI":"10.1145\/3188745.3188936"},{"key":"12_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/978-3-319-63688-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"T Liu","year":"2017","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 758\u2013790. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_25"},{"key":"12_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-3-319-78381-9_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"T Liu","year":"2018","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Towards breaking the exponential barrier for general secret sharing. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 567\u2013596. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_21"},{"key":"12_CR58","unstructured":"Mann, E.: Private access to distributed information. Master\u2019s thesis, Technion \u2013 Israel Institute of Technology, Haifa (1998)"},{"key":"12_CR59","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Robere, R.: Strongly exponential lower bounds for monotone computation. In: 49th STOC, pp. 1246\u20131255 (2017)","DOI":"10.1145\/3055399.3055478"},{"key":"12_CR60","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Robere, R.: Lifting Nullstellensatz to monotone span programs over any field. In: 50th STOC, pp. 1207\u20131219 (2018)","DOI":"10.1145\/3188745.3188914"},{"issue":"3","key":"12_CR61","first-page":"717","volume":"14","author":"L R\u00f3nyai","year":"2001","unstructured":"R\u00f3nyai, L., Babai, L., Ganapathy, M.K.: On the number of zero-patterns of a sequence of polynomials. J. AMS 14(3), 717\u2013735 (2001)","journal-title":"J. AMS"},{"issue":"11","key":"12_CR62","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"12_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/978-3-642-54242-8_26","volume-title":"Theory of Cryptography","author":"H Wee","year":"2014","unstructured":"Wee, H.: Dual system encryption via predicate encodings. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 616\u2013637. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_26"},{"key":"12_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1007\/11523468_115","volume-title":"Automata, Languages and Programming","author":"S Wehner","year":"2005","unstructured":"Wehner, S., de Wolf, R.: Improved lower bounds for locally decodable codes and private information retrieval. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1424\u20131436. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11523468_115"},{"key":"12_CR65","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: Proceedings of the 20th IEEE Conference on Computational Complexity, pp. 275\u2013284 (2005)","DOI":"10.1109\/CCC.2005.2"},{"key":"12_CR66","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: Proceedings of the 39th ACM Symposium on the Theory of Computing, pp. 266\u2013274 (2007)","DOI":"10.1145\/1250790.1250830"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-12293-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T20:28:19Z","timestamp":1764620899000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-12293-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,2]]},"ISBN":["9783032122926","9783032122933"],"references-count":66,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-12293-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,2]]},"assertion":[{"value":"2 December 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Aarhus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}