{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T23:29:14Z","timestamp":1784676554848,"version":"3.55.0"},"publisher-location":"Cham","reference-count":63,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030842581","type":"print"},{"value":"9783030842598","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"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":[[2021]]},"DOI":"10.1007\/978-3-030-84259-8_17","type":"book-chapter","created":{"date-parts":[[2021,8,10]],"date-time":"2021-08-10T23:21:47Z","timestamp":1628637707000},"page":"487-516","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Low-Complexity Weak Pseudorandom Functions in $$\\mathtt {AC}0[\\mathtt {MOD}2]$$"],"prefix":"10.1007","author":[{"given":"Elette","family":"Boyle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Geoffroy","family":"Couteau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Niv","family":"Gilboa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lisa","family":"Kohl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Scholl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,8,11]]},"reference":[{"key":"17_CR1","unstructured":"Akavia, A., Bogdanov, A., Guo, S., Kamath, A., Rosen, A.: Candidate weak pseudorandom functions in $${\\sf AC}^0$$$$o$$ MOD$$_2$$. In: ITCS 2014. ACM, January 2014"},{"key":"17_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, Part I. LNCS, vol. 9056, pp. 430\u2013454. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_17"},{"key":"17_CR3","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th FOCS. IEEE Computer Society Press, October 2003"},{"issue":"5","key":"17_CR4","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/120884857","volume":"42","author":"B Applebaum","year":"2013","unstructured":"Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. SIAM J. Comput. 42(5), 2008\u20132037 (2013)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"17_CR5","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/16M1085942","volume":"47","author":"B Applebaum","year":"2018","unstructured":"Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. SIAM J. Comput. 47(1), 52\u201379 (2018)","journal-title":"SIAM J. Comput."},{"key":"17_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, Part I. LNCS, vol. 9985, pp. 27\u201356. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53641-4_2"},{"key":"17_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 403\u2013415. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_34"},{"key":"17_CR8","unstructured":"Ball, M., Holmgren, J., Ishai, Y., Liu, T., Malkin, T.: On the complexity of decomposable randomized encodings, or: how friendly can a garbling-friendly PRF be? In: ITCS 2020. LIPIcs, January 2020"},{"key":"17_CR9","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":"17_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/11535218_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"O Barkol","year":"2005","unstructured":"Barkol, O., Ishai, Y.: Secure computation of constant-depth circuits with applications to database search problems. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 395\u2013411. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11535218_24"},{"issue":"3","key":"17_CR11","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E Berlekamp","year":"1978","unstructured":"Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (Corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"17_CR12","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\u2019 93","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":"17_CR13","unstructured":"Bogdanov, A., Rosen, A.: Pseudorandom functions: three decades later. Cryptology ePrint Archive, Report 2017\/652 (2017). http:\/\/eprint.iacr.org\/2017\/652"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1007\/978-3-030-03810-6_25","volume-title":"Theory of Cryptography","author":"D Boneh","year":"2018","unstructured":"Boneh, D., Ishai, Y., Passel\u00e8gue, A., Sahai, A., Wu, D.J.: Exploring crypto dark matter: new simple PRF candidates and their applications. In: Beimel, A., Dziembowski, S. (eds.) TCC 2018, Part II. LNCS, vol. 11240, pp. 699\u2013729. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-03810-6_25"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Correlated pseudorandom functions via variable-density LPN. In: FOCS (2020)","DOI":"10.1109\/FOCS46700.2020.00103"},{"issue":"5","key":"17_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M Braverman","year":"2008","unstructured":"Braverman, M.: Polylogarithmic independence fools AC0 circuits. J. ACM (JACM) 57(5), 1\u201310 (2008)","journal-title":"J. ACM (JACM)"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-662-52993-5_16","volume-title":"Fast Software Encryption","author":"A Canteaut","year":"2016","unstructured":"Canteaut, A., et al.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 313\u2013333. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-52993-5_16"},{"key":"17_CR18","unstructured":"Carmosino, M.L., Impagliazzo, R., Kabanets, V., Kolokolova, A.: Learning algorithms from natural proofs. In: CCC 2016, pp. 10:1\u201310:24 (2016)"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jcss.2018.04.006","volume":"97","author":"M Cheraghchi","year":"2018","unstructured":"Cheraghchi, M., Grigorescu, E., Juba, B., Wimmer, K., Xie, N.: Ac$${}^{\\text{0 }}$$$$\\circ $$mod$${}_{\\text{2 }}$$ lower bounds for the Boolean inner product. J. Comput. Syst. Sci. 97, 45\u201359 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/3-540-45353-9_20","volume-title":"Topics in Cryptology \u2014 CT-RSA 2001","author":"NT Courtois","year":"2001","unstructured":"Courtois, N.T.: The security of hidden field equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 266\u2013281. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45353-9_20"},{"key":"17_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-540-45146-4_11","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"NT Courtois","year":"2003","unstructured":"Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176\u2013194. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_11"},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/3-540-39200-9_21","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2003","author":"NT Courtois","year":"2003","unstructured":"Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345\u2013359. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_21"},{"key":"17_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1007\/978-3-030-77886-6_29","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"G Couteau","year":"2021","unstructured":"Couteau, G., Meyer, P.: Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 842\u2013870. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77886-6_29"},{"key":"17_CR24","unstructured":"Daniely, A., Vardi, G.: From local pseudorandom generators to hardness of learning. arXiv preprint arXiv:2101.08303 (2021)"},{"issue":"1","key":"17_CR25","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"I Dumer","year":"2003","unstructured":"Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49(1), 22\u201337 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"17_CR26","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/070684914","volume":"39","author":"V Feldman","year":"2009","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: On agnostic learning of parities, monomials, and halfspaces. SIAM J. Comput. 39(2), 606\u2013645 (2009)","journal-title":"SIAM J. Comput."},{"key":"17_CR27","unstructured":"Filmus, Y., Ishai, Y., Kaplan, A., Kindler, G.: Limits of preprocessing. In: CCC 2020 (2020)"},{"issue":"1","key":"17_CR28","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Gandikota, V., Ghazi, B., Grigorescu, E.: On the np-hardness of bounded distance decoding of Reed-Solomon codes. In: 2015 IEEE International Symposium on Information Theory (ISIT), pp. 2904\u20132908. IEEE (2015)","DOI":"10.1109\/ISIT.2015.7282988"},{"key":"17_CR30","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":"17_CR31","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions (extended abstract). In: 25th FOCS. IEEE Computer Society Press, October 1984"},{"key":"17_CR32","volume-title":"Computational Limitations for Small-depth Circuits","author":"JT H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, J.T.: Computational Limitations for Small-depth Circuits. MIT Press, Cambridge (1987)"},{"key":"17_CR33","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"issue":"1","key":"17_CR34","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2007.05.018","volume":"384","author":"L Hellerstein","year":"2007","unstructured":"Hellerstein, L., Servedio, R.A.: On PAC learning algorithms for rich Boolean function classes. Theor. Comput. Sci. 384(1), 66\u201376 (2007). https:\/\/doi.org\/10.1016\/j.tcs.2007.05.018","journal-title":"Theor. Comput. Sci."},{"key":"17_CR35","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC 2008, pp. 433\u2013442 (2008)","DOI":"10.1145\/1374376.1374438"},{"issue":"3","key":"17_CR36","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1006\/jcss.1997.1533","volume":"55","author":"JC Jackson","year":"1997","unstructured":"Jackson, J.C.: An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. J. Comput. Syst. Sci. 55(3), 414\u2013440 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/3-540-48910-X_24","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201999","author":"T Johansson","year":"1999","unstructured":"Johansson, T., J\u00f6nsson, F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 347\u2013362. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_24"},{"issue":"1","key":"17_CR38","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning Boolean formulae and finite automata. J. ACM 41(1), 67\u201395 (1994)","journal-title":"J. ACM"},{"key":"17_CR39","doi-asserted-by":"crossref","unstructured":"Kharitonov, M.: Cryptographic hardness of distribution-specific learning. In: 25th ACM STOC. ACM Press, May 1993","DOI":"10.1145\/167088.167197"},{"key":"17_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-44693-1_37","volume-title":"STACS 2001","author":"M Krause","year":"2001","unstructured":"Krause, M., Lucks, S.: On the minimal hardware complexity of pseudorandom function generators. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 419\u2013430. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44693-1_37"},{"key":"17_CR41","doi-asserted-by":"crossref","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. In: 30th FOCS. IEEE Computer Society Press, October\/November 1989","DOI":"10.1109\/SFCS.1989.63537"},{"key":"17_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-662-49890-3_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"P M\u00e9aux","year":"2016","unstructured":"M\u00e9aux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 311\u2013343. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49890-3_13"},{"key":"17_CR43","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":"17_CR44","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On e-biased generators in NC0. In: 44th FOCS. IEEE Computer Society Press, October 2003"},{"issue":"4","key":"17_CR45","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"17_CR46","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. In: 36th FOCS. IEEE Computer Society Press, October 1995"},{"key":"17_CR47","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS. IEEE Computer Society Press, October 1997"},{"key":"17_CR48","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O., Rosen, A.: Pseudo-random functions and factoring (extended abstract). In: 32nd ACM STOC. ACM Press, May 2000","DOI":"10.1145\/335305.335307"},{"key":"17_CR49","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness (extended abstract). In: 29th FOCS. IEEE Computer Society Press, October 1988","DOI":"10.1109\/SFCS.1988.21916"},{"key":"17_CR50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"key":"17_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-030-77870-5_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"C Orlandi","year":"2021","unstructured":"Orlandi, C., Scholl, P., Yakoubov, S.: The rise of Paillier: homomorphic secret sharing and public-key silent OT. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 678\u2013708. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77870-5_24"},{"key":"17_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/3-540-44750-4_20","volume-title":"Advances in Cryptology \u2014 CRYPT0\u2019 95","author":"J Patarin","year":"1995","unstructured":"Patarin, J.: Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt\u201988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 248\u2013261. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-44750-4_20"},{"issue":"4","key":"17_CR53","first-page":"333","volume":"41","author":"AA Razborov","year":"1987","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333\u2013338 (1987)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"17_CR54","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: 26th ACM STOC. ACM Press, May 1994","DOI":"10.1145\/195058.195134"},{"key":"17_CR55","doi-asserted-by":"crossref","unstructured":"Rossman, B., Servedio, R.A., Tan, L.Y.: An average-case depth hierarchy theorem for Boolean circuits. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1030\u20131048. IEEE (2015)","DOI":"10.1109\/FOCS.2015.67"},{"key":"17_CR56","unstructured":"Servedio, R.A., Viola, E.: On a special case of rigidity. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 19, p. 144. Citeseer (2012)"},{"key":"17_CR57","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: 19th ACM STOC. ACM Press, May 1987","DOI":"10.1145\/28395.28404"},{"issue":"11","key":"17_CR58","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"issue":"6","key":"17_CR59","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"17_CR60","doi-asserted-by":"crossref","unstructured":"Viola, E.: The communication complexity of addition. In: 24th SODA. ACM-SIAM, January 2013","DOI":"10.1137\/1.9781611973105.46"},{"key":"17_CR61","doi-asserted-by":"crossref","unstructured":"Williams, R.: Natural proofs versus derandomization. In: 45th ACM STOC. ACM Press, June 2013","DOI":"10.1145\/2488608.2488612"},{"key":"17_CR62","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":"Yu Yu","year":"2016","unstructured":"Yu, Yu., Steinberger, J.: Pseudorandom functions in almost constant depth from low-noise LPN. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part II. LNCS, vol. 9666, pp. 154\u2013183. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_6"},{"key":"17_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-662-53018-4_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"Yu Yu","year":"2016","unstructured":"Yu, Yu., Zhang, J.: Cryptography with auxiliary input and trapdoor from constant-noise LPN. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 214\u2013243. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53018-4_9"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2021"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-84259-8_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,11]],"date-time":"2024-08-11T00:04:58Z","timestamp":1723334698000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-84259-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030842581","9783030842598"],"references-count":63,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-84259-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"11 August 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"41","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"426","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"103","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20.9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1 invited paper is also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}