{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:21:14Z","timestamp":1768922474500,"version":"3.49.0"},"publisher-location":"Cham","reference-count":70,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031683817","type":"print"},{"value":"9783031683824","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-68382-4_7","type":"book-chapter","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T09:02:41Z","timestamp":1723712561000},"page":"210-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Systematic Study of\u00a0Sparse LWE"],"prefix":"10.1007","author":[{"given":"Aayush","family":"Jain","sequence":"first","affiliation":[]},{"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Sagnik","family":"Saha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,16]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dadush, D., Regev, O., Stephens-Davidowitz, N.: Solving the shortest vector problem in 2n time using discrete gaussian sampling. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 733\u2013742 (2015)","DOI":"10.1109\/FOCS.2015.41"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Alagic, G., et al.: Status Report on the Third Round of The NIST Post-Quantum Cryptography Standardization Process. US Department of Commerce, NIST (2022)","DOI":"10.6028\/NIST.IR.8413"},{"key":"7_CR3","unstructured":"Albrecht, M., et al.: Homomorphic encryption security standard. Tech. rep., HomomorphicEncryption.org, Toronto, Canada (2018)"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Albrecht, M., Cid, C., Faugere, J.C., Fitzpatrick, R., Perret, L.: Algebraic algorithms for LWE problems (2014)","DOI":"10.1145\/2815111.2815158"},{"issue":"2","key":"7_CR5","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10623-013-9864-x","volume":"74","author":"MR Albrecht","year":"2013","unstructured":"Albrecht, M.R., Cid, C., Faug\u00e8re, J.-C., Fitzpatrick, R., Perret, L.: On the complexity of the BKW algorithm on LWE. Des. Codes Crypt. 74(2), 325\u2013354 (2013). https:\/\/doi.org\/10.1007\/s10623-013-9864-x","journal-title":"Des. Codes Crypt."},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-319-98113-0_19","volume-title":"Security and Cryptography for Networks","author":"MR Albrecht","year":"2018","unstructured":"Albrecht, M.R., et al.: Estimate all the LWE, NTRU schemes! In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 351\u2013367. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98113-0_19"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1515\/jmc-2015-0016","volume":"9","author":"MR Albrecht","year":"2015","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169\u2013203 (2015)","journal-title":"J. Math. Cryptol."},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298\u2013307. IEEE Computer Society Press (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Allen, S.R., O\u2019Donnell, R., Witmer, D.: How to refute a random CSP. In: Guruswami, V. (ed.) 56th FOCS, pp. 689\u2013708. IEEE Computer Society Press (2015)","DOI":"10.1109\/FOCS.2015.48"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Schulman, L.J. (ed.) 42nd ACM STOC, pp. 171\u2013180. ACM Press (2010)","DOI":"10.1145\/1806689.1806715"},{"key":"7_CR11","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). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_35"},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-319-63688-7_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"B Applebaum","year":"2017","unstructured":"Applebaum, B., Damg\u00e5rd, I., Ishai, Y., Nielsen, M., Zichron, L.: Secure arithmetic computation with constant computational overhead. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 223\u2013254. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_8"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/11830924_25","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"B Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX\/RANDOM -2006. LNCS, vol. 4110, pp. 260\u2013271. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11830924_25"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, pp. 1087\u20131100. ACM Press (2016)","DOI":"10.1145\/2897518.2897554"},{"key":"7_CR15","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"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296(1), 625\u2013635 (1993)","journal-title":"Math. Ann."},{"key":"7_CR17","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":"7_CR18","doi-asserted-by":"crossref","unstructured":"Beullens, W., Lyubashevsky, V., Nguyen, N.K., Seiler, G.: Lattice-based blind signatures: Short, efficient, and round-optimal. Cryptology ePrint Archive, Report 2023\/077 (2023). https:\/\/eprint.iacr.org\/2023\/077","DOI":"10.1145\/3576915.3616613"},{"issue":"4","key":"7_CR19","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 (JACM) 50(4), 506\u2013519 (2003)","journal-title":"J. ACM (JACM)"},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-642-55220-5_30","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"D Boneh","year":"2014","unstructured":"Boneh, D., et al.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 533\u2013556. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_30"},{"key":"7_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-96878-0_3","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"Z Brakerski","year":"2018","unstructured":"Brakerski, Z.: Quantum FHE (almost) as secure as\u00a0classical. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 67\u201395. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_3"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U.V., Vidick, T.: A cryptographic test of quantumness and certifiable randomness from a single quantum device. In: Thorup, M. (ed.) 59th FOCS, pp. 320\u2013331. IEEE Computer Society Press (2018)","DOI":"10.1109\/FOCS.2018.00038"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, 8-10 January 2012, pp. 309\u2013325 (2012)","DOI":"10.1145\/2090236.2090262"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309\u2013325. ACM (2012)","DOI":"10.1145\/2090236.2090262"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehl\u00e9, D.: Classical hardness of learning with errors. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 575\u2013584. ACM Press (2013)","DOI":"10.1145\/2488608.2488680"},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97\u2013106. IEEE Computer Society Press (2011)","DOI":"10.1109\/FOCS.2011.12"},{"key":"7_CR27","doi-asserted-by":"crossref","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for $$\\cal{P}$$ from LWE. In: 62nd FOCS, pp. 68\u201379. IEEE Computer Society Press (2022)","DOI":"10.1109\/FOCS52979.2021.00016"},{"key":"7_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-030-84252-9_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"G Couteau","year":"2021","unstructured":"Couteau, G., Rindal, P., Raghuraman, S.: Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 502\u2013534. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_17"},{"key":"7_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-44683-4_24","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M Cryan","year":"2001","unstructured":"Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC0. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 272\u2013284. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44683-4_24"},{"key":"7_CR30","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-031-38545-2_11","volume-title":"CRYPTO 2023, Part II","author":"Q Dao","year":"2023","unstructured":"Dao, Q., Ishai, Y., Jain, A., Lin, H.: Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part II. LNCS, vol. 14082, pp. 315\u2013348. Springer, Heidelberg (Aug (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_11"},{"key":"7_CR31","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: 34th ACM STOC, pp. 534\u2013543. ACM Press (2002)","DOI":"10.1145\/509907.509985"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169\u2013178. ACM Press (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"7_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-29011-4_28","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"C Gentry","year":"2012","unstructured":"Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465\u2013482. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_28"},{"key":"7_CR34","doi-asserted-by":"crossref","unstructured":", Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197\u2013206. ACM Press (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC (2008). https:\/\/eprint.iacr.org\/2007\/432","DOI":"10.1145\/1374376.1374407"},{"key":"7_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75\u201392. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_5"},{"key":"7_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-22670-0_10","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 76\u201387. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22670-0_10"},{"key":"7_CR38","unstructured":"Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: Yao, A.C. (ed.) Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, 5-7 January 2010. Proceedings, pp. 230\u2013240. Tsinghua University Press (2010)"},{"key":"7_CR39","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 545\u2013554. ACM Press (2013)","DOI":"10.1145\/2488608.2488677"},{"key":"7_CR40","doi-asserted-by":"crossref","unstructured":"Goyal, R., Koppula, V., Waters, B.: Lockable obfuscation. In: Umans, C. (ed.) 58th FOCS, pp. 612\u2013621. IEEE Computer Society Press (2017)","DOI":"10.1109\/FOCS.2017.62"},{"key":"7_CR41","doi-asserted-by":"crossref","unstructured":"Goyal, R., Koppula, V., Waters, B.: Collusion resistant traitor tracing from learning with errors. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC, pp. 660\u2013670. ACM Press (2018)","DOI":"10.1145\/3188745.3188844"},{"key":"7_CR42","doi-asserted-by":"crossref","unstructured":"Henzinger, A., Dauterman, E., Corrigan-Gibbs, H., Zeldovich, N.: Private web search with tiptoe. In: Flinn, J., Seltzer, M.I., Druschel, P., Kaufmann, A., Mace, J. (eds.) Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pp. 396\u2013416. ACM (2023), https:\/\/doi.org\/10.1145\/3600006.3613134","DOI":"10.1145\/3600006.3613134"},{"key":"7_CR43","unstructured":"Henzinger, A., Hong, M.M., Corrigan-Gibbs, H., Meiklejohn, S., Vaikuntanathan, V.: One server for the price of two: Simple and fast single-server private information retrieval. In: Calandrino, J.A., Troncoso, C. (eds.) 32nd USENIX Security Symposium, USENIX Security 2023, Anaheim, CA, USA, August 9-11, 2023, pp. 3889\u20133905. USENIX Association (2023). https:\/\/www.usenix.org\/conference\/usenixsecurity23\/presentation\/henzinger"},{"key":"7_CR44","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 433\u2013442. ACM Press (2008)","DOI":"10.1145\/1374376.1374438"},{"key":"7_CR45","doi-asserted-by":"crossref","unstructured":"Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: Khuller, S., Williams, V.V. (eds.) 53rd ACM STOC, pp. 60\u201373. ACM Press (2021)","DOI":"10.1145\/3406325.3451093"},{"key":"7_CR46","doi-asserted-by":"crossref","unstructured":", Kothari, P.K., Mori, R., O\u2019Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th ACM STOC, pp. 132\u2013145. ACM Press (2017)","DOI":"10.1145\/3055399.3055485"},{"key":"7_CR47","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th FOCS, pp. 364\u2013373. IEEE Computer Society Press (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"7_CR48","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Math. Ann. 261(ARTICLE), 515\u2013534 (1982)","DOI":"10.1007\/BF01457454"},{"key":"7_CR49","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). https:\/\/doi.org\/10.1007\/11538462_32"},{"key":"7_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/978-3-642-03356-8_34","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"V Lyubashevsky","year":"2009","unstructured":"Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 577\u2013594. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_34"},{"key":"7_CR51","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-031-15979-4_3","volume-title":"CRYPTO 2022, Part II","author":"V Lyubashevsky","year":"2022","unstructured":"Lyubashevsky, V., Nguyen, N.K., Plan\u00e7on, M.: Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 71\u2013101. Springer, Heidelberg (Aug (2022)"},{"key":"7_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-13190-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1\u201323. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_1"},{"key":"7_CR53","doi-asserted-by":"crossref","unstructured":"Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th FOCS, pp. 332\u2013338. IEEE Computer Society Press (2018)","DOI":"10.1109\/FOCS.2018.00039"},{"key":"7_CR54","doi-asserted-by":"crossref","unstructured":"Mahadev, U.: Classical verification of quantum computations. In: Thorup, M. (ed.) 59th FOCS, pp. 259\u2013267. IEEE Computer Society Press (2018)","DOI":"10.1109\/FOCS.2018.00033"},{"key":"7_CR55","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: On the hardness of learning with errors with binary secrets. Theory Comput. 14(13), 1\u201317 (2018). https:\/\/theoryofcomputing.org\/articles\/v014a013","DOI":"10.4086\/toc.2018.v014a013"},{"key":"7_CR56","doi-asserted-by":"publisher","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective, vol. 671. Springer, New York (2002). https:\/\/doi.org\/10.1007\/978-1-4615-0897-7","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"7_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"D Micciancio","year":"2012","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700\u2013718. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_41"},{"key":"7_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-642-40041-4_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"D Micciancio","year":"2013","unstructured":"Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21\u201339. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_2"},{"key":"7_CR59","doi-asserted-by":"crossref","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On e-biased generators in NC0. In: FOCS, pp. 136\u2013145 (2003)","DOI":"10.1109\/SFCS.2003.1238188"},{"key":"7_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201999","author":"P Paillier","year":"1999","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223\u2013238. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_16"},{"key":"7_CR61","doi-asserted-by":"crossref","unstructured":"Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pp. 333\u2013342. ACM (2009)","DOI":"10.1145\/1536414.1536461"},{"key":"7_CR62","unstructured":"Player, R.: Parameter selection in lattice-based cryptography. Ph.D. thesis, Royal Holloway, University of London (2018)"},{"key":"7_CR63","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"7_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-319-63697-9_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"M Ro\u015fca","year":"2017","unstructured":"Ro\u015fca, M., Sakzad, A., Stehl\u00e9, D., Steinfeld, R.: Middle-product learning with errors. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 283\u2013297. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63697-9_10"},{"issue":"2\u20133","key":"7_CR65","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"CP Schnorr","year":"1987","unstructured":"Schnorr, C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53(2\u20133), 201\u2013224 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"7_CR66","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1017\/S0963548300001371","volume":"3","author":"C Schnorr","year":"1994","unstructured":"Schnorr, C.: Block reduced lattice bases and successive minima. Comb. Probab. Comput. 3, 507\u2013522 (1994)","journal-title":"Comb. Probab. Comput."},{"key":"7_CR67","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"CP Schnorr","year":"1994","unstructured":"Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181\u2013199 (1994)","journal-title":"Math. Program."},{"issue":"1","key":"7_CR68","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10623-012-9720-4","volume":"71","author":"NP Smart","year":"2012","unstructured":"Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Crypt. 71(1), 57\u201381 (2012). https:\/\/doi.org\/10.1007\/s10623-012-9720-4","journal-title":"Des. Codes Crypt."},{"key":"7_CR69","unstructured":"Vaikunthananthan, V.: CS 294 lecture 4: worst-case to average-case reductions for LWE. Class at UC Berkeley (2020). http:\/\/people.csail.mit.edu\/vinodv\/CS294\/lecture6.pdf"},{"key":"7_CR70","doi-asserted-by":"crossref","unstructured":"Wichs, D., Zirdelis, G.: Obfuscating compute-and-compare programs under LWE. In: Umans, C. (ed.) 58th FOCS, pp. 600\u2013611. IEEE Computer Society Press (2017)","DOI":"10.1109\/FOCS.2017.61"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68382-4_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T19:04:10Z","timestamp":1732647850000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68382-4_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031683817","9783031683824"],"references-count":70,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68382-4_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"16 August 2024","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":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}