{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:22:36Z","timestamp":1775794956146,"version":"3.50.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030176587","type":"print"},{"value":"9783030176594","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-17659-4_21","type":"book-chapter","created":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T04:42:13Z","timestamp":1557808933000},"page":"619-635","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing"],"prefix":"10.1007","author":[{"given":"Zvika","family":"Brakerski","sequence":"first","affiliation":[]},{"given":"Vadim","family":"Lyubashevsky","sequence":"additional","affiliation":[]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Wichs","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,24]]},"reference":[{"key":"21_CR1","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optimia in lattices, codes, and systems of linear equations. In: 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, USA, 3\u20135 November 1993, pp. 724\u2013733. IEEE Computer Society (1993)"},{"key":"21_CR2","unstructured":"Alkim, E., Ducas, L., P\u00f6ppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, 10\u201312 August 2016, pp. 327\u2013343 (2016)"},{"key":"21_CR3","unstructured":"Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, 9-11 January 2017, Berkeley, CA, USA, pp. 7:1\u20137:31 (2017)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, USA, 22\u201324 May 1996, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-03685-9_26","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N Alon","year":"2009","unstructured":"Alon, N., Panigrahy, R., Yekhanin, S.: Deterministic approximation algorithms for the nearest codeword problem. In: Dinur, I., Jansen, K., Naor, J., Rolim, J.D.P. (eds.) APPROX\/RANDOM 2009. LNCS, vol. 5687, pp. 339\u2013351. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03685-9_26"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Bos, J.W., et al.: Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24\u201328 October 2016, pages 1006\u20131018 (2016)","DOI":"10.1145\/2976749.2978425"},{"key":"21_CR7","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.L., Kearns, M.J., 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":"21_CR8","unstructured":"Berman, P., Karpinski, M.: Approximating minimum unsatisfiability of linear equations. In: Eppstein, D. (ed.) Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 6\u20138 January 2002, San Francisco, CA, USA, pp. 514\u2013516. ACM\/SIAM (2002)"},{"issue":"4","key":"21_CR9","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":"21_CR10","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 575\u2013584 (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"21_CR11","unstructured":"Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. Cryptology ePrint Archive, Report 2017\/967 (2017). https:\/\/eprint.iacr.org\/2017\/967. EUROCRYPT 2018 [BLSV18]"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-319-78381-9_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"Z Brakerski","year":"2018","unstructured":"Brakerski, Z., Lombardi, A., Segev, G., Vaikuntanathan, V.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 535\u2013564. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_20"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 97\u2013106 (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"21_CR14","unstructured":"Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17\u201318 October 1999, New York, NY, USA, pp. 475\u2013485. IEEE Computer Society (1999)"},{"issue":"2","key":"21_CR15","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":"21_CR16","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May\u20132 June 2009, pp. 169\u2013178 (2009)"},{"key":"21_CR17","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 3, no. 42 (1996)"},{"issue":"1","key":"21_CR18","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"21_CR19","unstructured":"Goldreich, O.: Three XOR-lemmas - an exposition. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 2, no. 56 (1995)"},{"key":"21_CR20","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). https:\/\/doi.org\/10.1007\/978-3-642-20465-4_3"},{"key":"21_CR21","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\n$${}^{\\text{+ }}$$\n protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73\u201387. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11761679_6"},{"key":"21_CR22","unstructured":"Kopparty, S., Saraf, S.: Local list-decoding and testing of random linear codes from high error. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, MA, USA, 5\u20138 June 2010, pp. 417\u2013426. ACM (2010)"},{"key":"21_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/3-540-48285-7_33","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 1993","author":"M Matsui","year":"1994","unstructured":"Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386\u2013397. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48285-7_33"},{"key":"21_CR24","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: Proceedings of 45th Symposium on Foundations of Computer Science (FOCS 2004), 17\u201319 October 2004, Rome, Italy, pp. 372\u2013381 (2004)"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-45146-4_17","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"D Micciancio","year":"2003","unstructured":"Micciancio, D., Vadhan, S.P.: Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282\u2013298. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_17"},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"Mahmoody, M., Xiao, D.: On the power of randomized reductions and the checkability of SAT. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, MA, 9\u201312 June 2010, pp. 64\u201375 (2010)","DOI":"10.1109\/CCC.2010.16"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem (extended abstract). In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May\u20132 June 2009, pp. 333\u2013342 (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"21_CR28","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, Baltimore, MD, USA, 22\u201324 May 2005, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"issue":"2","key":"21_CR29","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196\u2013249 (2003)","journal-title":"J. ACM"},{"key":"21_CR30","unstructured":"Vazirani, U.V.: Randomness, adversaries and computation (random polynomial time). Ph.D. thesis (1986)"},{"key":"21_CR31","unstructured":"Yu, Y., Zhang, J., Weng, J., Guo, C., Li, X.: Learning parity with noise implies collision resistant hashing. Cryptology ePrint Archive, Report 2017\/1260 (2017). https:\/\/eprint.iacr.org\/2017\/1260"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17659-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:00:37Z","timestamp":1710334837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17659-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030176587","9783030176594"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17659-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"24 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Darmstadt","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"38","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2019\/","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":"IACR websubrev","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"327","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":"76","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":"23% - 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":"19","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)"}}]}}