{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:48:57Z","timestamp":1740098937773,"version":"3.37.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319686363"},{"type":"electronic","value":"9783319686370"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68637-0_16","type":"book-chapter","created":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T06:07:56Z","timestamp":1508134076000},"page":"261-267","source":"Crossref","is-referenced-by-count":0,"title":["On the Hardness of Sparsely Learning Parity with Noise"],"prefix":"10.1007","author":[{"given":"Hanlin","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuoyao","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,17]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1007\/s00037-011-0029-x","volume":"20","author":"M Alekhnovich","year":"2011","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. Comput. Complex. 20, 755\u2013786 (2011)","journal-title":"Comput. Complex."},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 171\u2013180 (2010)","DOI":"10.1145\/1806689.1806715"},{"issue":"4","key":"16_CR3","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s00145-009-9039-0","volume":"22","author":"B Applebaum","year":"2009","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. J. Cryptol. 22(4), 429\u2013469 (2009)","journal-title":"J. Cryptol."},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22792-9_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"B Barak","year":"2011","unstructured":"Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Y.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 1\u201320. Springer, Heidelberg (2011). doi:\n10.1007\/978-3-642-22792-9_1"},{"key":"16_CR5","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\n            n\/20: how \n            $$1+1=0$$\n           improves information set decoding. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 520\u2013536. Springer, Heidelberg (2012). doi:\n10.1007\/978-3-642-29011-4_31"},{"issue":"3","key":"16_CR6","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"ER Berlekamp","year":"1978","unstructured":"Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.A.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theor. 24(3), 384\u2013386 (1978)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"16_CR7","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). doi:\n10.1007\/978-3-642-22792-9_42"},{"key":"16_CR8","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). doi:\n10.1007\/3-540-48329-2_24"},{"issue":"4","key":"16_CR9","doi-asserted-by":"crossref","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"},{"issue":"1","key":"16_CR10","doi-asserted-by":"crossref","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":"16_CR11","doi-asserted-by":"crossref","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: New results for learning noisy parities and halfspaces. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21\u201324 October 2006, Berkeley, California, USA, Proceedings, pp. 563\u2013574 (2006)","DOI":"10.1109\/FOCS.2006.51"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Holenstein, T.: Key agreement from weak bit agreement. In: STOC, pp. 664\u2013673 (2005)","DOI":"10.1145\/1060590.1060689"},{"key":"16_CR13","unstructured":"Holenstein, T.: Strengthening Key Agreement using Hard-Core Sets. PhD thesis, ETH Zurich, Zurich, Switzerland (2006)"},{"issue":"3","key":"16_CR14","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/s00145-010-9061-2","volume":"23","author":"J Katz","year":"2010","unstructured":"Katz, J., Shin, J.S., Smith, A.D.: Parallel and concurrent security of the HB and hb\n            $${^{\\text{+ }}}$$\n           protocols. J. Cryptol. 23(3), 402\u2013421 (2010)","journal-title":"J. Cryptol."},{"key":"16_CR15","unstructured":"Kirchner, P.: Improved generalized birthday attack. IACR Cryptology ePrint Archive 2011:377 (2011)"},{"key":"16_CR16","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). doi:\n10.1007\/11832072_24"},{"key":"16_CR17","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. Algorithms and Techniques","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\/RANDOM -2005. LNCS, vol. 3624, pp. 378\u2013389. Springer, Heidelberg (2005). doi:\n10.1007\/11538462_32"},{"key":"16_CR18","unstructured":"May, A., Meurer, A., Thomae, E.: Decoding random linear codes in \n            $$\\tilde{\\cal{O}}(2^{ 0.054n})$$\n          . In: Advances in Cryptology - ASIACRYPT 2011\u201317th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4\u20138, 2011, Proceedings, pp. 107\u2013124 (2011)"},{"key":"16_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-22792-9_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"D Micciancio","year":"2011","unstructured":"Micciancio, D., Mol, P.: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 465\u2013484. Springer, Heidelberg (2011). doi:\n10.1007\/978-3-642-22792-9_26"},{"issue":"6","key":"16_CR20","doi-asserted-by":"crossref","first-page":"34:1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1\u201334:40 (2009)","journal-title":"J. ACM"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0019850","volume-title":"Coding Theory and Applications","author":"J Stern","year":"1989","unstructured":"Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106\u2013113. Springer, Heidelberg (1989). doi:\n10.1007\/BFb0019850"},{"key":"16_CR22","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":"Y Yu","year":"2016","unstructured":"Yu, Y., Zhang, J.: Cryptography with auxiliary input and trapdoor from constant-noise LPN. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 214\u2013243. Springer, Heidelberg (2016). doi:\n10.1007\/978-3-662-53018-4_9"}],"container-title":["Lecture Notes in Computer Science","Provable Security"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68637-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T06:11:56Z","timestamp":1508134316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68637-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319686363","9783319686370"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68637-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}