{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:08:19Z","timestamp":1766279299385,"version":"3.48.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031223648"},{"type":"electronic","value":"9783031223655"}],"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.springernature.com\/gp\/researchers\/text-and-data-mining"},{"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.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22365-5_20","type":"book-chapter","created":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T03:04:30Z","timestamp":1671591870000},"page":"565-592","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Public-Key Encryption from\u00a0Homogeneous CLWE"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0338-6151","authenticated-orcid":false,"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2505-4246","authenticated-orcid":false,"given":"Miguel","family":"Cueto Noval","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2027-5549","authenticated-orcid":false,"given":"Charlotte","family":"Hoffmann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3021-7150","authenticated-orcid":false,"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,21]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 171\u2013180. Association for Computing Machinery, New York (2010)","DOI":"10.1145\/1806689.1806715"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 284\u2013293. Association for Computing Machinery, New York (1997)","DOI":"10.1145\/258533.258604"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Annual IEEE Symposium on Foundations of Computer Science, Proceedings, pp. 298\u2013307 (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"20_CR4","unstructured":"Brennan, M.S., Bresler, G.: Reducibility and statistical-computational gaps from secret leakage. In: Abernethy, J.D., Agarwal, S. (eds.) Conference on Learning Theory, COLT 2020, 9\u201312 July 2020, Virtual Event [Graz, Austria], Proceedings of Machine Learning Research, , vol. 125, pp. 648\u2013847. PMLR (2020)"},{"key":"20_CR5","unstructured":"Bogdanov, A., Noval, M.C., Hoffmann, C., Rosen, A.: Public-key encryption from continuous LWE. Cryptology ePrint Archive, Paper 2022\/093 (2022). https:\/\/eprint.iacr.org\/2022\/093"},{"key":"20_CR6","unstructured":"Berthet, Q., Rigollet, P.: Complexity theoretic lower bounds for sparse principal component detection. In: Shalev-Shwartz, S., Steinwart, I. (eds.) Proceedings of the 26th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 30, pp. 1046\u20131066. PMLR, Princeton, 12\u201314 June 2013"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Bruna, J., Regev, O., Song, M.J., Tang, Y.: Continuous LWE. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pp. 694\u2013707. Association for Computing Machinery, New York (2021)","DOI":"10.1145\/3406325.3451000"},{"issue":"4","key":"20_CR8","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/13090818X","volume":"44","author":"M Belkin","year":"2015","unstructured":"Belkin, M., Sinha, K.: Polynomial learning of distribution families. SIAM J. Comput. 44(4), 889\u2013911 (2015)","journal-title":"SIAM J. Comput."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D.M., Stewart, A.: Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73\u201384 (2017)","DOI":"10.1109\/FOCS.2017.16"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-24676-3_21","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"C Dwork","year":"2004","unstructured":"Dwork, C., Naor, M., Reingold, O.: Immunizing encryption schemes from decryption errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 342\u2013360. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24676-3_21"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/3-540-39568-7_2","volume-title":"Advances in Cryptology","author":"T ElGamal","year":"1985","unstructured":"ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10\u201318. Springer, Heidelberg (1985). https:\/\/doi.org\/10.1007\/3-540-39568-7_2"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 1\u20139. Association for Computing Machinery, New York (1998)","DOI":"10.1145\/276698.276704"},{"issue":"1","key":"20_CR13","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":"20_CR14","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17\u201320 May 2008, pp. 197\u2013206. ACM (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-48405-1_30","volume-title":"Advances in Cryptology\u2014CRYPTO\u2019 99","author":"O Goldreich","year":"1999","unstructured":"Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467\u2013484. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48405-1_30"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Gupte, A., Vafa, N., Vaikuntanathan, V.: Continuous LWE is as hard as LWE & applications to learning gaussian mixtures. Cryptology ePrint Archive, Report 2022\/437 (2022). https:\/\/ia.cr\/2022\/437","DOI":"10.1109\/FOCS54457.2022.00112"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Hardt, M., Price, E.: Tight bounds for learning a mixture of two gaussians. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, 14\u201317 June 2015, pp. 753\u2013760 (2015)","DOI":"10.1145\/2746539.2746579"},{"key":"20_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/11535218_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"T Holenstein","year":"2005","unstructured":"Holenstein, T., Renner, R.: One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 478\u2013493. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11535218_29"},{"key":"20_CR19","unstructured":"Hajek, B., Wu, Y., Xu, J.: Computational lower bounds for community detection on random graphs. In: Proceedings of The 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 40, pp. 899\u2013928. PMLR, Paris, 03\u201306 Jul 2015"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Zuckerman, D.: How to recycle random bits,pp. 248\u2013253. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63486"},{"key":"20_CR21","first-page":"114","volume":"44","author":"RJ McEliece","year":"1978","unstructured":"McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Netw. Progr. Rep. 44, 114\u2013116 (1978)","journal-title":"Deep Space Netw. Progr. Rep."},{"key":"20_CR22","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 measures. SIAM J. Comput. 37, 267\u2013302 (2007)","journal-title":"SIAM J. Comput."},{"key":"20_CR23","unstructured":"Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization. MIT Laboratory for Computer Science (1979)"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393 (2005). Full version in [Reg09]","DOI":"10.1145\/1060590.1060603"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)","DOI":"10.1145\/1568318.1568324"},{"issue":"2","key":"20_CR26","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"issue":"2","key":"20_CR27","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196\u2013249 (2003)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22365-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:02:16Z","timestamp":1766278936000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22365-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031223648","9783031223655"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22365-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"21 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chicago, IL","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":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-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":"139","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":"60","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":"43% - 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.1","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":"9.9","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":"This content has been made available to all.","name":"free","label":"Free to read"}]}}