{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T20:00:32Z","timestamp":1775332832804,"version":"3.50.1"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031070815","type":"print"},{"value":"9783031070822","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-07082-2_14","type":"book-chapter","created":{"date-parts":[[2022,5,28]],"date-time":"2022-05-28T00:09:51Z","timestamp":1653696591000},"page":"372-401","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Quantum Algorithms for\u00a0Variants of\u00a0Average-Case Lattice Problems via\u00a0Filtering"],"prefix":"10.1007","author":[{"given":"Yilei","family":"Chen","sequence":"first","affiliation":[]},{"given":"Qipeng","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Zhandry","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,25]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, 4\u20138 July 2011, Proceedings, Part I, pp. 403\u2013415 (2011)","DOI":"10.1007\/978-3-642-22006-7_34"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Bos, J.W., et al.: CRYSTALS - kyber: A cca-secure module-lattice-based KEM. In: EuroS&P, pp. 353\u2013367. IEEE (2018)","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/978-3-319-76581-5_24","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"Z Brakerski","year":"2018","unstructured":"Brakerski, Z., Kirshanova, E., Stehl\u00e9, D., Wen, W.: Learning with errors and extrapolated dihedral cosets. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 702\u2013727. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_24"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Biasse, J.F., Song, F.: Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 893\u2013902. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch64"},{"key":"14_CR6","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":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-46497-7_1","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2015","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Constrained key-homomorphic PRFs from standard lattice assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 1\u201330. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46497-7_1"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-662-49896-5_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"R Cramer","year":"2016","unstructured":"Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559\u2013585. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_20"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-319-56620-7_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"R Cramer","year":"2017","unstructured":"Cramer, R., Ducas, L., Wesolowski, B.: Short stickelberger class relations and application to ideal-SVP. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 324\u2013348. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_12"},{"key":"14_CR10","unstructured":"Campbell, P., Groves, M., Shepherd, D.: Soliloquy: A cautionary tale (2014)"},{"key":"14_CR11","unstructured":"Cai, J.Y., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: FOCS, pp. 468\u2013477. IEEE Computer Society (1997)"},{"key":"14_CR12","unstructured":"Childs, A.M., Dam, W.V.: Quantum algorithm for a generalized hidden shift problem. In: SODA, pp. 1225\u20131232. SIAM (2007)"},{"issue":"1","key":"14_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.46586\/tches.v2018.i1.238-268","volume":"2018","author":"L Ducas","year":"2018","unstructured":"Ducas, L.: Crystals-dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(1), 238\u2013268 (2018)","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-319-89339-6_16","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2018","author":"J-P D\u2019Anvers","year":"2018","unstructured":"D\u2019Anvers, J.-P., Karmakar, A., Sinha Roy, S., Vercauteren, F.: Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 282\u2013305. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89339-6_16"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-642-38348-9_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"N D\u00f6ttling","year":"2013","unstructured":"D\u00f6ttling, N., M\u00fcller-Quade, J.: Lossy codes and a new variant of the learning-with-errors problem. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 18\u201334. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_2"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Eisentr\u00e4ger, K., Hallgren, S., Kitaev, A.Y., Song, F.: A quantum algorithm for computing the unit group of an arbitrary degree number field. In: STOC, pp. 293\u2013302. ACM (2014)","DOI":"10.1145\/2591796.2591860"},{"key":"14_CR17","unstructured":"Eldar, L., Shor, P.W.: An efficient quantum algorithm for a variant of the closest lattice-vector problem (2016)"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Magniez, F., Santha, M., Sen, P.: Hidden translation and orbit coset in quantum computing. In: STOC, pp. 1\u20139. ACM (2003)","DOI":"10.1145\/780542.780544"},{"key":"14_CR19","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Electron. Colloq. Comput. Compl. (ECCC) 3(42) (1996)"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Grilo, A.B., Kerenidis, I., Zijlstra, T.: Learning-with-errors problem is easy with quantum samples. Phys. Rev. A 99(3), 032314 (2019)","DOI":"10.1103\/PhysRevA.99.032314"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197\u2013206 (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: STOC, pp. 545\u2013554. ACM (2013)","DOI":"10.1145\/2488608.2488677"},{"key":"14_CR23","unstructured":"Ivanyos, G., Prakash, A., Santha, M.: On learning linear functions from subset and its applications in quantum computing. In: ESA, vol. 112 of LIPIcs, pp. 66:1\u201366:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005)","journal-title":"SIAM J. Comput."},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: FOCS, pp. 332\u2013338. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00039"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Improved cryptographic hash functions with worst-case\/average-case connection. In: STOC, pp. 609\u2013618. ACM (2002)","DOI":"10.1145\/509907.509995"},{"key":"14_CR27","unstructured":"Micciancio, D.: CSE 206A: Lattice Algorithms and Applications. Lecture 2: The dual lattice (2012)"},{"key":"14_CR28","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"},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measure. SIAM J. Comput. 37(1), 267\u2013302 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"14_CR30","doi-asserted-by":"publisher","first-page":"1313","DOI":"10.1137\/18M1210186","volume":"33","author":"SD Miller","year":"2019","unstructured":"Miller, S.D., Stephens-Davidowitz, N.: Kissing numbers and transference theorems from generalized tail bounds. SIAM J. Disc. Math. 33(3), 1313\u20131325 (2019)","journal-title":"SIAM J. Disc. Math."},{"key":"14_CR31","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, Cambridge (2016)"},{"key":"14_CR32","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0375-9601(88)91034-1","volume":"128","author":"A Peres","year":"1988","unstructured":"Peres, A.: How to differentiate between non-orthogonal states. Phys. Lett. A 128, 19\u201319 (1988)","journal-title":"Phys. Lett. A"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Regev, O.: Quantum computation and lattice problems. In: FOCS, pp. 520\u2013529. IEEE Computer Society (2002)","DOI":"10.1109\/SFCS.2002.1181976"},{"key":"14_CR34","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393. ACM (2005)","DOI":"10.1145\/1060590.1060603"},{"issue":"1","key":"14_CR35","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF01581144","volume":"66","author":"C-P Schnorr","year":"1994","unstructured":"Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(1), 181\u2013199 (1994)","journal-title":"Math. Program."},{"key":"14_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"D Stehl\u00e9","year":"2009","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617\u2013635. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10366-7_36"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-07082-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T22:03:02Z","timestamp":1748383382000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-07082-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031070815","9783031070822"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-07082-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"25 May 2022","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":"Trondheim","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Norway","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 May 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 June 2022","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":"eurocrypt2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2022\/","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":"372","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":"85","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":"18","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":"Peer review was double-blind with rebuttal.","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)"}}]}}