{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:22:32Z","timestamp":1775794952808,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":55,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662498958","type":"print"},{"value":"9783662498965","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49896-5_6","type":"book-chapter","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T04:45:32Z","timestamp":1461732332000},"page":"154-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN"],"prefix":"10.1007","author":[{"given":"Yu","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Steinberger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,28]]},"reference":[{"key":"6_CR1","unstructured":"Related work on LPN-based authentication schemes. http:\/\/www.ecrypt.eu.org\/lightweight\/index.php\/HB"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Akavia, A., Bogdanov, A., Guo, S., Kamath, A., Rosen, A.: Candidate weak pseudorandom functions in AC $$^0{\\circ }$$ 0 \u2218 MOD $$_2$$ 2 . In: Innovations in Theoretical Computer Science, ITCS 2014, pp. 251\u2013260 (2014)","DOI":"10.1145\/2554797.2554821"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs. approximation complexity. In: 44th Annual Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, Massachusetts, pp. 298\u2013307. IEEE (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B Applebaum","year":"2009","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595\u2013618. Springer, Heidelberg (2009)"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-540-74143-5_6","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"B Applebaum","year":"2007","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 92\u2013110. Springer, Heidelberg (2007). http:\/\/www.eng.tau.ac.il\/bennyap\/pubs\/input-locality-full-revised-1.pdf"},{"key":"6_CR6","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)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-642-29011-4_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"A Becker","year":"2012","unstructured":"Becker, A., Joux, A., May, A., Meurer, A.: Decoding random binary linear codes in $$2^{\\text{ n\/20 }}$$ 2 n\/20 : how 1 + 1 = 0 improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520\u2013536. Springer, Heidelberg (2012)"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48405-1_17","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"M Bellare","year":"1999","unstructured":"Bellare, M., Goldreich, O., Krawczyk, H.: Stateless evaluation of pseudorandom functions: security beyond the birthday barrier. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 270\u2013287. Springer, Heidelberg (1999)"},{"issue":"3","key":"6_CR9","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.J., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theor. 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-36594-2_3","volume-title":"Theory of Cryptography","author":"I Berman","year":"2013","unstructured":"Berman, I., Haitner, I., Komargodski, I., Naor, M.: Hardness preserving reductions via cuckoo hashing. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 40\u201359. Springer, Heidelberg (2013)"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-22792-9_42","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"DJ Bernstein","year":"2011","unstructured":"Bernstein, D.J., Lange, T., Peters, C.: Smaller decoding exponents: ball-collision decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 743\u2013760. Springer, Heidelberg (2011)"},{"key":"6_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 - CRYPTO \u201993","author":"A Blum","year":"1994","unstructured":"Blum, A., Furst, M.L., 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)"},{"issue":"4","key":"6_CR13","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-540-85174-5_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"A Boldyreva","year":"2008","unstructured":"Boldyreva, A., Fehr, S., O\u2019Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335\u2013359. Springer, Heidelberg (2008)"},{"issue":"1","key":"6_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1109\/18.651067","volume":"44","author":"A Canteaut","year":"1998","unstructured":"Canteaut, A., Chabaud, F.: A new algorithm for finding minimum-weight words in a linear code: application to McEliece\u2019s cryptosystem and to narrow-sense BCH codes of length 511. IEEE Trans. Inf. Theor. 44(1), 367\u2013378 (1998)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-662-49096-9_10","volume-title":"Theory of Cryptography","author":"D Cash","year":"2016","unstructured":"Cash, D., Kiltz, E., Tessaro, S.: Two-round man-in-the-middle security from LPN. In: Kushilevitz, E., et al. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 225\u2013248. Springer, Heidelberg (2016)"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-13039-2_6","volume-title":"Progress in Cryptology \u2013 INDOCRYPT 2014","author":"N Chandran","year":"2014","unstructured":"Chandran, N., Garg, S.: Balancing output length and query bound in hardness preserving constructions of pseudorandom functions. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 89\u2013103. Springer, Cham (2014)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-642-55220-5_19","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"S Chen","year":"2014","unstructured":"Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327\u2013350. Springer, Heidelberg (2014)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/978-3-319-12280-9_10","volume-title":"Cryptology and Network Security","author":"B David","year":"2014","unstructured":"David, B., Dowsley, R., Nascimento, A.C.A.: Universally composable oblivious transfer based on a variant of LPN. In: Gritzalis, D., Kiayias, A., Askoxylakis, I. (eds.) CANS 2014. LNCS, vol. 8813, pp. 143\u2013158. Springer, Heidelberg (2014)"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-642-29011-4_22","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"Y Dodis","year":"2012","unstructured":"Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D.: Message authentication, revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 355\u2013374. Springer, Heidelberg (2012)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-540-30576-7_30","volume-title":"Theory of Cryptography","author":"Y Dodis","year":"2005","unstructured":"Dodis, Y., Smith, A.: Entropic security and the encryption of high entropy messages. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 556\u2013577. Springer, Heidelberg (2005)"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-642-34961-4_30","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"N D\u00f6ttling","year":"2012","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J., Nascimento, A.C.A.: IND-CCA secure cryptography based on a variant of the LPN problem. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 485\u2013503. Springer, Heidelberg (2012)"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/978-3-662-47989-6_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"N D\u00f6ttling","year":"2015","unstructured":"D\u00f6ttling, N., Schr\u00f6der, D.: Efficient pseudorandom functions via on-the-fly adaptation. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 329\u2013350. Springer, Heidelberg (2015)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: New results for learning noisy parities and halfspaces. In: 47th Symposium on Foundations of Computer Science, Berkeley, CA, USA, 21\u201324 October 2006, pp. 563\u2013574. IEEE (2006)","DOI":"10.1109\/FOCS.2006.51"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Gazi, P., Tessaro, S.: Secret-key cryptography from ideal primitives: a systematic overview. In: 2015 IEEE Information Theory Workshop (ITW 2015), pp. 1\u20135 (2015)","DOI":"10.1109\/ITW.2015.7133163"},{"issue":"4","key":"6_CR26","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"},{"key":"6_CR27","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"RL Graham","year":"1994","unstructured":"Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley Longman Publishing Co. Inc., Boston (1994)","edition":"2"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Haitner, I., Reingold, O., Vadhan, S.P.: Efficiency improvements in constructing pseudorandom generators from one-way functions. In: Proceedings of the 42nd ACM Symposium on the Theory of Computing, pp. 437\u2013446 (2010)","DOI":"10.1145\/1806689.1806750"},{"issue":"4","key":"6_CR29","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., Luby, M.: Construction of pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"301","key":"6_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/3-540-45682-1_4","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"NJ Hopper","year":"2001","unstructured":"Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52\u201366. Springer, Heidelberg (2001)"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, 30 October\u20131 November 1989, pp. 248\u2013253. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63486"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/978-3-642-34961-4_40","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2012","author":"A Jain","year":"2012","unstructured":"Jain, A., Krenn, S., Pietrzak, K., Tentes, A.: Commitments and efficient zero-knowledge proofs from learning parity with noise. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 663\u2013680. Springer, Heidelberg (2012)"},{"key":"6_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-28914-9_21","volume-title":"Theory of Cryptography","author":"A Jain","year":"2012","unstructured":"Jain, A., Pietrzak, K., Tentes, A.: Hardness preserving constructions of pseudorandom functions. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 369\u2013382. Springer, Heidelberg (2012)"},{"key":"6_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/11535218_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"A Juels","year":"2005","unstructured":"Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293\u2013308. Springer, Heidelberg (2005)"},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/11761679_6","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"J Katz","year":"2006","unstructured":"Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB $$^{+}$$ + protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73\u201387. Springer, Heidelberg (2006)"},{"key":"6_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-54631-0_1","volume-title":"Public-Key Cryptography \u2013 PKC 2014","author":"E Kiltz","year":"2014","unstructured":"Kiltz, E., Masny, D., Pietrzak, K.: Simple chosen-ciphertext security from low-noise LPN. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 1\u201318. Springer, Heidelberg (2014)"},{"key":"6_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-642-20465-4_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"E Kiltz","year":"2011","unstructured":"Kiltz, E., Pietrzak, K., Cash, D., Jain, A., Venturi, D.: Efficient authentication from hard learning problems. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 7\u201326. Springer, Heidelberg (2011)"},{"key":"6_CR39","unstructured":"Kirchner, P.: Improved generalized birthday attack. Cryptology ePrint Archive, Report 2011\/377 (2011). http:\/\/eprint.iacr.org\/2011\/377"},{"key":"6_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11832072_24","volume-title":"Security and Cryptography for Networks","author":"\u00c9 Levieil","year":"2006","unstructured":"Levieil, \u00c9., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348\u2013359. Springer, Heidelberg (2006)"},{"issue":"4","key":"6_CR41","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"LA Levin","year":"1987","unstructured":"Levin, L.A.: One-way functions and pseudorandom generators. Combinatorica 7(4), 357\u2013363 (1987)","journal-title":"Combinatorica"},{"key":"6_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"V Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"key":"6_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-642-40084-1_18","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Masny, D.: Man-in-the-middle secure authentication schemes from LPN and weak PRFs. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 308\u2013325. Springer, Heidelberg (2013)"},{"key":"6_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-46035-7_8","volume-title":"Advances in Cryptology - EUROCRYPT 2002","author":"UM Maurer","year":"2002","unstructured":"Maurer, U.M.: Indistinguishability of random systems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 110\u2013132. Springer, Heidelberg (2002)"},{"key":"6_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-25385-0_6","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2011","author":"A May","year":"2011","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in $$\\tilde{\\cal O\\cal }(2^{0.054n})$$ O ~ ( 2 0.054 n ) . In: Wang, X., Lee, D.H. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 107\u2013124. Springer, Heidelberg (2011)"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th Annual Symposium on Foundations of Computer Science, Miami Beach, Florida, 20\u201322 October 1997, pp. 458\u2013467. IEEE (1997)","DOI":"10.1109\/SFCS.1997.646134"},{"key":"6_CR47","doi-asserted-by":"crossref","unstructured":"Naor, M., Reingold, O., Rosen, A.: Pseudo-random functions and factoring. Electronic Colloquium on Computational Complexity (ECCC) TR01-064 (2001)","DOI":"10.1145\/335305.335307"},{"key":"6_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-04159-4_21","volume-title":"Selected Areas in Cryptography","author":"J Patarin","year":"2009","unstructured":"Patarin, J.: The \u201cCoefficients H\u201d technique. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 328\u2013345. Springer, Heidelberg (2009)"},{"key":"6_CR49","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)"},{"key":"6_CR50","first-page":"598","volume":"41","author":"AA Razborov","year":"1986","unstructured":"Razborov, A.A.: Lower bounds on the size of bounded depth networks over a complete basis with logical addition. Mathematische Zametki 41, 598\u2013607 (1986). English Translation in Mathematical Notes of the Academy of Sciences of the USSR","journal-title":"Mathematische Zametki"},{"key":"6_CR51","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, Montr\u00e9al, Qu\u00e9bec, Canada, 23\u201325 May 1994, pp. 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"6_CR52","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005)","DOI":"10.1145\/1060590.1060603"},{"key":"6_CR53","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC 1987), pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"6_CR54","series-title":"Lecture Notes in Computer Science","first-page":"106","volume-title":"Coding Theory and Applications","author":"T Dong","year":"2005","unstructured":"Dong, T., Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory and Applications. LNCS, vol. 388, pp. 106\u2013113. Springer, Heidelberg (2005)"},{"key":"6_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-662-48000-7_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"Y Yu","year":"2015","unstructured":"Yu, Y., Gu, D., Li, X., Weng, J.: (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 209\u2013229. Springer, Heidelberg (2015)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49896-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T22:03:35Z","timestamp":1748901815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49896-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662498958","9783662498965"],"references-count":55,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49896-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"28 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}