{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:10Z","timestamp":1763468230250,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,1,11]],"date-time":"2015-01-11T00:00:00Z","timestamp":1420934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Institute","award":["Simons Investigator Award FA8750-11-2-0225"],"award-info":[{"award-number":["Simons Investigator Award FA8750-11-2-0225"]}]},{"name":"ERC","award":["Stg grant number 239985"],"award-info":[{"award-number":["Stg grant number 239985"]}]},{"name":"NSF","award":["CNS-1347364"],"award-info":[{"award-number":["CNS-1347364"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,1,11]]},"DOI":"10.1145\/2688073.2688082","type":"proceedings-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:42:45Z","timestamp":1421095365000},"page":"219-228","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Computational Benefit of Correlated Instances"],"prefix":"10.1145","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shafi","family":"Goldwasser","sequence":"additional","affiliation":[{"name":"MIT and Weizmann Institute of Science, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[{"name":"UCSB, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946338"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2009144.2009147"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214050"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_5_1","first-page":"45","volume-title":"ICS","author":"Applebaum B.","year":"2011","unstructured":"B. Applebaum , D. Harnik , and Y. Ishai . Semantic security under related-key attacks and applications . In ICS , pages 45 -- 60 , 2011 . B. Applebaum, D. Harnik, and Y. Ishai. Semantic security under related-key attacks and applications. In ICS, pages 45--60, 2011."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.20"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_9_1","volume-title":"On the (im)possibility of tamper-resilient cryptography: Using fourier analysis in computer viruses. IACR Cryptology ePrint Archive","author":"Austrin P.","year":"2013","unstructured":"P. Austrin , K.-M. Chung , M. Mahmoody , R. Pass , and K. Seth . On the (im)possibility of tamper-resilient cryptography: Using fourier analysis in computer viruses. IACR Cryptology ePrint Archive , 2013 :194, 2013. P. Austrin, K.-M. Chung, M. Mahmoody, R. Pass, and K. Seth. On the (im)possibility of tamper-resilient cryptography: Using fourier analysis in computer viruses. IACR Cryptology ePrint Archive, 2013:194, 2013."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422460"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881458"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_26"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1766171.1766214"},{"key":"e_1_3_2_1_14_1","first-page":"187","volume-title":"CRYPTO","author":"Ben-Aroya I.","year":"1993","unstructured":"I. Ben-Aroya and E. Biham . Differtial cryptanalysis of lucifer . In CRYPTO , pages 187 -- 199 , 1993 . I. Ben-Aroya and E. Biham. Differtial cryptanalysis of lucifer. In CRYPTO, pages 187--199, 1993."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00203965"},{"key":"e_1_3_2_1_16_1","first-page":"2","volume-title":"CRYPTO","author":"Biham E.","year":"1990","unstructured":"E. Biham and A. Shamir . Differential cryptanalysis of des-like cryptosystems . In CRYPTO , pages 2 -- 21 , 1990 . E. Biham and A. Shamir. Differential cryptanalysis of des-like cryptosystems. In CRYPTO, pages 2--21, 1990."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00630563"},{"key":"e_1_3_2_1_18_1","first-page":"156","volume-title":"CRYPTO","author":"Biham E.","year":"1991","unstructured":"E. Biham and A. Shamir . Differential cryptanalysis of snefru, khafre, redoc-ii, loki and lucifer . In CRYPTO , pages 156 -- 171 , 1991 . E. Biham and A. Shamir. Differential cryptanalysis of snefru, khafre, redoc-ii, loki and lucifer. In CRYPTO, pages 156--171, 1991."},{"key":"e_1_3_2_1_19_1","first-page":"1","volume-title":"EUROCRYPT","author":"Biham E.","year":"1991","unstructured":"E. Biham and A. Shamir . Differential cryptoanalysis of feal and n-hash . In EUROCRYPT , pages 1 -- 16 , 1991 . E. Biham and A. Shamir. Differential cryptoanalysis of feal and n-hash. In EUROCRYPT, pages 1--16, 1991."},{"key":"e_1_3_2_1_20_1","first-page":"278","volume-title":"CRYPTO","author":"Blum A.","year":"1993","unstructured":"A. Blum , M. L. Furst , M. J. Kearns , and R. J. Lipton . Cryptographic primitives based on hard learning problems . In CRYPTO , pages 278 -- 291 , 1993 . A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton. Cryptographic primitives based on hard learning problems. In CRYPTO, pages 278--291, 1993."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0034-0"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.010"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_31"},{"key":"e_1_3_2_1_24_1","first-page":"145","volume-title":"NIPS","author":"Daniely A.","year":"2013","unstructured":"A. Daniely , N. Linial , and S. Shalev-Shwartz . More data speeds up training time in learning halfspaces over sparse vectors . In NIPS , pages 145 -- 153 , 2013 . A. Daniely, N. Linial, and S. Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. In NIPS, pages 145--153, 2013."},{"key":"e_1_3_2_1_25_1","volume-title":"The computational benefit of correlated instances. Electronic Colloquium on Computational Complexity (ECCC), 21:83","author":"Dinur I.","year":"2014","unstructured":"I. Dinur , S. Goldwasser , and H. Lin . The computational benefit of correlated instances. Electronic Colloquium on Computational Complexity (ECCC), 21:83 , 2014 . I. Dinur, S. Goldwasser, and H. Lin. The computational benefit of correlated instances. Electronic Colloquium on Computational Complexity (ECCC), 21:83, 2014."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.44"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v32:4"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11799-2_16"},{"key":"e_1_3_2_1_31_1","volume-title":"Candidate one-way functions based on expander graphs. IACR Cryptology ePrint Archive","author":"Goldreich O.","year":"2000","unstructured":"O. Goldreich . Candidate one-way functions based on expander graphs. IACR Cryptology ePrint Archive , 2000 :63, 2000. O. Goldreich. Candidate one-way functions based on expander graphs. IACR Cryptology ePrint Archive, 2000:63, 2000."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875531"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 21st USENIX Security Symposium","author":"Heninger N.","year":"2012","unstructured":"N. Heninger , Z. Durumeric , E. Wustrow , and J. A. Halderman . Mining your Ps and Qs: Detection of widespread weak keys in network devices . In Proceedings of the 21st USENIX Security Symposium , Aug. 2012 . N. Heninger, Z. Durumeric, E. Wustrow, and J. A. Halderman. Mining your Ps and Qs: Detection of widespread weak keys in network devices. In Proceedings of the 21st USENIX Security Symposium, Aug. 2012."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_1_36_1","first-page":"196","volume-title":"AUSCRYPT","author":"Knudsen L. R.","year":"1992","unstructured":"L. R. Knudsen . Cryptanalysis of loki91 . In AUSCRYPT , pages 196 -- 208 , 1992 . L. R. Knudsen. Cryptanalysis of loki91. In AUSCRYPT, pages 196--208, 1992."},{"key":"e_1_3_2_1_37_1","volume-title":"Jet Propulsion lab, 44:114--116","author":"McEliece R. J.","year":"1978","unstructured":"R. J. McEliece . A publickey system based on algebraic coding theory pages. DSN Progress Report , Jet Propulsion lab, 44:114--116 , 1978 . R. J. McEliece. A publickey system based on algebraic coding theory pages. DSN Progress Report, Jet Propulsion lab, 44:114--116, 1978."},{"key":"e_1_3_2_1_38_1","volume-title":"Manuscript","author":"O'Donnell R.","year":"2012","unstructured":"R. O'Donnell and D. Witmer . Goldreich's prg: Evidence for near-optimal polynomial stretch . Manuscript , 2012 . R. O'Donnell and D. Witmer. Goldreich's prg: Evidence for near-optimal polynomial stretch. Manuscript, 2012."},{"key":"e_1_3_2_1_39_1","first-page":"256","volume-title":"WADS","author":"Spielman D. A.","year":"2003","unstructured":"D. A. Spielman and S.-H. Teng . Smoothed analysis (motivation and discrete models) . In WADS , pages 256 -- 270 , 2003 . D. A. Spielman and S.-H. Teng. Smoothed analysis (motivation and discrete models). In WADS, pages 256--270, 2003."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808710"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30057-8_16"}],"event":{"name":"ITCS'15: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rehovot Israel","acronym":"ITCS'15"},"container-title":["Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688082","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2688073.2688082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:12:14Z","timestamp":1750227134000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,11]]},"references-count":42,"alternative-id":["10.1145\/2688073.2688082","10.1145\/2688073"],"URL":"https:\/\/doi.org\/10.1145\/2688073.2688082","relation":{},"subject":[],"published":{"date-parts":[[2015,1,11]]},"assertion":[{"value":"2015-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}