{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T01:06:27Z","timestamp":1764119187067,"version":"3.46.0"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031486142"},{"type":"electronic","value":"9783031486159"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-48615-9_10","type":"book-chapter","created":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T18:02:21Z","timestamp":1701021741000},"page":"268-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Public-Key Encryption, Local Pseudorandom Generators, and\u00a0the\u00a0Low-Degree Method"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,27]]},"reference":[{"issue":"3","key":"10_CR1","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00145-015-9202-8","volume":"29","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Bogdanov, A., Rosen, A.: A dichotomy for local small-bias generators. J. Cryptol. 29(3), 577\u2013596 (2016)","journal-title":"J. Cryptol."},{"key":"10_CR2","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"},{"issue":"1","key":"10_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/16M1085942","volume":"47","author":"B Applebaum","year":"2018","unstructured":"Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. SIAM J. Comput. 47(1), 52\u201379 (2018)","journal-title":"SIAM J. Comput."},{"key":"10_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, Graz, Austria, 9\u201312 July 2020, Virtual Event, vol. 125 of Proceedings of Machine Learning Research, pp. 648\u2013847. PMLR (2020)"},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/17M1138236","volume":"48","author":"B Barak","year":"2019","unstructured":"Barak, B., Hopkins, S.B., Kelner, J.A., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM J. Comput. 48(2), 687\u2013735 (2019)","journal-title":"SIAM J. Comput."},{"key":"10_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, vol. 30 of Proceedings of Machine Learning Research, Princeton, NJ, USA, 12\u201314 June 2013, pp. 1046\u20131066. PMLR (2013)"},{"key":"10_CR7","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":"10_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Kim, J.H., Ofek, E.: Witnesses for non-satisfiability of dense random 3cnf formulas. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 497\u2013508 (2006)","DOI":"10.1109\/FOCS.2006.78"},{"issue":"2","key":"10_CR9","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270\u2013299 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR10","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":"10_CR11","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Kothari, P.K., Potechin, A., Raghavendra, P., Schramm, T., Steurer, D.: The power of sum-of-squares for detecting hidden structures. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 October 2017, pp. 720\u2013731. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.72"},{"issue":"04","key":"10_CR12","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(04), 439\u2013562 (2006)","journal-title":"Bull. Am. Math. Soc."},{"key":"10_CR13","unstructured":"Hopkins, S.: Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University (2018)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Steurer, D.: Efficient bayesian estimation from few samples: community detection and related problems. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 October 2017, pp. 379\u2013390. IEEE Computer Society (2017)","DOI":"10.1109\/FOCS.2017.42"},{"key":"10_CR15","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, vol. 40 of Proceedings of Machine Learning Research, Paris, France, 03\u201306 July 2015, pp. 899\u2013928. PMLR (2015)"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-97127-4_1","volume-title":"Mathematical Analysis, its Applications and Computation","author":"D Kunisky","year":"2022","unstructured":"Kunisky, D., Wein, A.S., Bandeira, A.S.: Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio. In: Cerejeiras, P., Reissig, M. (eds.) ISAAC 2019, vol. 385, pp. 1\u201350. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-97127-4_1"},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"E Mossel","year":"2006","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On epsilon-biased generators in nc$${}^{\\text{0 }}$$. Random Struct. Algor. 29(1), 56\u201381 (2006)","journal-title":"Random Struct. Algor."},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Witmer, D.: Goldreich\u2019s PRG: evidence for near-optimal polynomial stretch. In: 2014 IEEE 29th Conference on Computational Complexity (CCC), pp. 1\u201312 (2014)","DOI":"10.1109\/CCC.2014.9"}],"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-48615-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T01:02:59Z","timestamp":1764118979000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-48615-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031486142","9783031486159"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-48615-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"27 November 2023","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":"Taipei","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 November 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2023\/","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":"168","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":"68","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":"40% - 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":"13","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"}]}}