{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:00:12Z","timestamp":1777964412271,"version":"3.51.4"},"publisher-location":"Cham","reference-count":57,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030038090","type":"print"},{"value":"9783030038106","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-03810-6_25","type":"book-chapter","created":{"date-parts":[[2018,11,7]],"date-time":"2018-11-07T16:30:29Z","timestamp":1541608229000},"page":"699-729","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":48,"title":["Exploring Crypto Dark Matter:"],"prefix":"10.1007","author":[{"given":"Dan","family":"Boneh","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Alain","family":"Passel\u00e8gue","sequence":"additional","affiliation":[]},{"given":"Amit","family":"Sahai","sequence":"additional","affiliation":[]},{"given":"David J.","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,8]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/2554797.2554821","volume":"2014","author":"A Akavia","year":"2014","unstructured":"Akavia, A., Bogdanov, A., Guo, S., Kamath, A., Rosen, A.: Candidate weak pseudorandom functions in AC$$^0$$ o MOD$$_2$$. ITCS 2014, 251\u2013260 (2014)","journal-title":"ITCS"},{"key":"25_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-662-46800-5_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 430\u2013454. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_17"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-45198-3_17","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N Alon","year":"2003","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX\/RANDOM -2003. LNCS, vol. 2764, pp. 188\u2013199. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45198-3_17"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Applebaum, B.: Cryptographic hardness of random local functions-survey. In: TCC, p. 599 (2013)","DOI":"10.1007\/978-3-642-36594-2_33"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: How to garble arithmetic circuits. In: FOCS, pp. 120\u2013129 (2011)","DOI":"10.1109\/FOCS.2011.40"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-662-53641-4_2","volume-title":"Theory of Cryptography","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Raykov, P.: Fast pseudorandom functions based on expander graphs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 27\u201356. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53641-4_2"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: ACM CCS, pp. 805\u2013817 (2016)","DOI":"10.1145\/2976749.2978331"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Arnold, A., Giesbrecht, M., Roche, D.S.: Sparse interpolation over finite fields via low-order roots of unity. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 27\u201334. ACM (2014)","DOI":"10.1145\/2608628.2608671"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-662-44371-2_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"A Banerjee","year":"2014","unstructured":"Banerjee, A., Peikert, C.: New and improved key-homomorphic pseudorandom functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 353\u2013370. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44371-2_20"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/978-3-642-29011-4_42","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"A Banerjee","year":"2012","unstructured":"Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719\u2013737. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_42"},{"key":"25_CR11","unstructured":"Barrington, D.A.: Width-3 permutation branching programs. Technical Memorandum TM-293 (1985)"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/3-540-44448-3_41","volume-title":"Advances in Cryptology \u2014 ASIACRYPT 2000","author":"M Bellare","year":"2000","unstructured":"Bellare, M., Namprempre, C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 531\u2013545. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44448-3_41"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynominal interpolation (extended abstract). In: ACM STOC, pp. 301\u2013309 (1988)","DOI":"10.1145\/62212.62241"},{"issue":"6","key":"25_CR14","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1137\/S009753979326091X","volume":"25","author":"F Bergadano","year":"1996","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput. 25(6), 1268\u20131280 (1996)","journal-title":"SIAM J. Comput."},{"key":"25_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-48329-2_24","volume-title":"Advances in Cryptology \u2014 CRYPTO 1993","author":"A Blum","year":"1994","unstructured":"Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278\u2013291. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48329-2_24"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: ACM STOC, pp. 435\u2013440 (2000)","DOI":"10.1145\/335305.335355"},{"key":"25_CR17","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-319-57048-8_3","volume-title":"Tutorials on the Foundations of Cryptography","author":"A Bogdanov","year":"2017","unstructured":"Bogdanov, A., Rosen, A.: Pseudorandom functions: three decades later. Tutorials on the Foundations of Cryptography. ISC, pp. 79\u2013158. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8_3"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-642-40041-4_23","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Boneh","year":"2013","unstructured":"Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic PRFs and their applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 410\u2013428. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_23"},{"key":"25_CR19","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: CCC, pp. 10:1\u201310:24 (2016)"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., H\u00e5stad, J., Friedman, J., Rudich, S., Smolensky, R.: The bit extraction problem of t-resilient functions (preliminary version). In: FOCS, pp. 396\u2013407 (1985)","DOI":"10.1109\/SFCS.1985.55"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-30576-7_19","volume-title":"Theory of Cryptography","author":"R Cramer","year":"2005","unstructured":"Cramer, R., Damg\u00e5rd, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342\u2013362. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-30576-7_19"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., et al.: Testing for concise representations. In: FOCS, pp. 549\u2013558 (2007)","DOI":"10.1109\/FOCS.2007.32"},{"key":"25_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/978-3-319-96884-1_22","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"C Dobraunig","year":"2018","unstructured":"Dobraunig, C., et al.: Rasta: a cipher with low ANDdepth and Few ANDs per bit. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 662\u2013692. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_22"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Druk, E., Ishai, Y.: Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. In: ITCS 2014, pp. 169\u2013182 (2014)","DOI":"10.1145\/2554797.2554815"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: On learning bounded-width branching programs. In: COLT, pp. 361\u2013368 (1995)","DOI":"10.1145\/225298.225342"},{"key":"25_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-319-63715-0_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"A Esser","year":"2017","unstructured":"Esser, A., K\u00fcbler, R., May, A.: LPN decoded. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 486\u2013514. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_17"},{"issue":"27\u201329","key":"25_CR27","doi-asserted-by":"publisher","first-page":"2659","DOI":"10.1016\/j.tcs.2009.03.030","volume":"410","author":"S Garg","year":"2009","unstructured":"Garg, S., Schost, \u00c9.: Interpolation of polynomials given by straight-line programs. Theor. Comput. Sci. 410(27\u201329), 2659\u20132662 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"25_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-78967-3_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"H Gilbert","year":"2008","unstructured":"Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB$$^\\sharp $$: increasing the security and efficiency of HB$$^+$$. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361\u2013378. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78967-3_21"},{"key":"25_CR29","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. Cryptology ePrint Archive, Report 2000\/063 (2000). http:\/\/eprint.iacr.org\/2000\/063"},{"key":"25_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/3-540-39568-7_22","volume-title":"Advances in Cryptology","author":"O Goldreich","year":"1985","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: On the cryptographic applications of random functions (extended abstract). In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 276\u2013288. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/3-540-39568-7_22"},{"issue":"4","key":"25_CR31","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986)","journal-title":"J. ACM"},{"issue":"4","key":"25_CR32","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: ACM STOC, pp. 433\u2013442 (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"25_CR34","doi-asserted-by":"crossref","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: FOCS, pp. 423\u2013432 (2004)","DOI":"10.1109\/FOCS.2004.64"},{"key":"25_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-51084-2_44","volume-title":"Symbolic and Algebraic Computation","author":"E Kaltofen","year":"1989","unstructured":"Kaltofen, E., Yagati, L.: Improved sparse multivariate polynomial interpolation algorithms. In: Gianni, P. (ed.) ISSAC 1988. LNCS, vol. 358, pp. 467\u2013474. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51084-2_44"},{"key":"25_CR36","doi-asserted-by":"crossref","unstructured":"Kharitonov, M.: Cryptographic hardness of distribution-specific learning. In: ACM STOC, pp. 372\u2013381 (1993)","DOI":"10.1145\/167088.167197"},{"key":"25_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/978-3-540-70583-3_40","volume-title":"Automata, Languages and Programming","author":"V Kolesnikov","year":"2008","unstructured":"Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 486\u2013498. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_40"},{"key":"25_CR38","doi-asserted-by":"crossref","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform, and learnability. In: FOCS, pp. 574\u2013579 (1989)","DOI":"10.1109\/SFCS.1989.63537"},{"key":"25_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-642-32009-5_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"E Miles","year":"2012","unstructured":"Miles, E., Viola, E.: Substitution-permutation networks, pseudorandom functions, and natural proofs. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 68\u201385. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_5"},{"key":"25_CR40","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. In: FOCS, pp. 170\u2013181 (1995)","DOI":"10.1109\/SFCS.1995.492474"},{"issue":"2","key":"25_CR41","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci. 58(2), 336\u2013375 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"25_CR42","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231\u2013262 (2004)","journal-title":"J. ACM"},{"key":"25_CR43","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O., Rosen, A.: Pseudo-random functions and factoring (extended abstract). In: ACM STOC, pp. 11\u201320 (2000)","DOI":"10.1145\/335305.335307"},{"issue":"1","key":"25_CR44","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic Boolean formulae. SIAM J. Discret. Math. 16(1), 20\u201346 (2002)","journal-title":"SIAM J. Discret. Math."},{"key":"25_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-642-27660-6_9","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K Pietrzak","year":"2012","unstructured":"Pietrzak, K.: Cryptography from learning parity with noise. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol. 7147, pp. 99\u2013114. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27660-6_9"},{"key":"25_CR46","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded-depth networks over a complete basis with logical addition (russian). Matematicheskie Zametki 41(4), 598\u2013607 (1987). english translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333\u2013338, 1987","DOI":"10.1007\/BF01137685"},{"key":"25_CR47","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: ACM STOC, pp. 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"25_CR48","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: ACM STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"25_CR49","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: A theory of the learnable. In: ACM STOC, pp. 436\u2013445 (1984)","DOI":"10.1145\/800057.808710"},{"key":"25_CR50","first-page":"314","volume-title":"Colt Proceedings 1990","author":"Karsten Verbeurgt","year":"1990","unstructured":"Verbeurgt, K.A.: Learning DNF under the uniform distribution in quasi-polynomial time. In: COLT, pp. 314\u2013326 (1990)"},{"key":"25_CR51","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1137\/1.9781611973105.46","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Emanuele Viola","year":"2013","unstructured":"Viola, E.: The communication complexity of addition. In: SODA, pp. 632\u2013651 (2013)"},{"issue":"2","key":"25_CR52","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01438278","volume":"5","author":"K Werther","year":"1994","unstructured":"Werther, K.: The complexity of sparse polynomial interpolation over finite fields. Appl. Algebr. Eng. Commun. Comput. 5(2), 91\u2013103 (1994)","journal-title":"Appl. Algebr. Eng. Commun. Comput."},{"key":"25_CR53","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162\u2013167 (1986)","DOI":"10.1109\/SFCS.1986.25"},{"key":"25_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-662-49896-5_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"Y Yu","year":"2016","unstructured":"Yu, Y., Steinberger, J.: Pseudorandom functions in almost constant depth from low-noise LPN. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 154\u2013183. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_6"},{"key":"25_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-662-46803-6_8","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"S Zahur","year":"2015","unstructured":"Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 220\u2013250. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_8"},{"key":"25_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09519-5_73"},{"issue":"3","key":"25_CR57","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R Zippel","year":"1990","unstructured":"Zippel, R.: Interpolating polynomials from their values. J. Symb. Comput. 9(3), 375\u2013403 (1990)","journal-title":"J. Symb. Comput."}],"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-030-03810-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T00:21:00Z","timestamp":1775262060000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-03810-6_25"}},"subtitle":["New Simple PRF Candidates and Their Applications"],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030038090","9783030038106"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-03810-6_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"8 November 2018","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":"Panaji","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 November 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 November 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}