{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:20Z","timestamp":1781078180256,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":82,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384342","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:36Z","timestamp":1624916916000},"page":"294-307","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Data structures meet cryptography: 3SUM with preprocessing"],"prefix":"10.1145","author":[{"given":"Alexander","family":"Golovnev","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siyao","family":"Guo","sequence":"additional","affiliation":[{"name":"New York University Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thibaut","family":"Horel","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sunoo","family":"Park","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA \/ Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_23"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70697-9_13"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Oswin Aichholzer Franz Aurenhammer Erik D. Demaine Ferran Hurtado Pedro Ramos and Jorge Urrutia. 2012. On-convex polygons. Comput. Geom. 45 3 ( 2012 ) 73-87.  Oswin Aichholzer Franz Aurenhammer Erik D. Demaine Ferran Hurtado Pedro Ramos and Jorge Urrutia. 2012. On-convex polygons. Comput. Geom. 45 3 ( 2012 ) 73-87.","DOI":"10.1016\/j.comgeo.2011.09.001"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"e_1_3_2_1_7_1","volume-title":"ISAAC","author":"Amir Amihood","year":"2016","unstructured":"Amihood Amir , Tsvi Kopelowitz , Avivit Levy , Seth Pettie , Ely Porat , and B. Riva Shalom . 2016. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap . In ISAAC 2016 . 12 : 1-12 : 12. Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. 2016. Mind the gap: Essentially optimal algorithms for online dictionary matching with one gap. In ISAAC 2016. 12 : 1-12 : 12."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195905001841"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Esther M. Arkin Yi-Jen Chiang Martin Held Joseph S. B. Mitchell Vera Sacristan Steven S. Skiena and Tae-Cheon Yang. 1998. On minimum-area hulls. Algorithmica 21 1 ( 1998 ) 119-136.  Esther M. Arkin Yi-Jen Chiang Martin Held Joseph S. B. Mitchell Vera Sacristan Steven S. Skiena and Tae-Cheon Yang. 1998. On minimum-area hulls. Algorithmica 21 1 ( 1998 ) 119-136.","DOI":"10.1007\/PL00009204"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669474"},{"key":"e_1_3_2_1_11_1","volume-title":"Computational complexity: a modern approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational complexity: a modern approach . Cambridge University Press . Sanjeev Arora and Boaz Barak. 2009. Computational complexity: a modern approach. Cambridge University Press."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897562"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.76"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000596"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_1"},{"key":"e_1_3_2_1_16_1","first-page":"272","volume-title":"Combiners for Backdoored Random Oracles. In CRYPTO","author":"Bauer Balthazar","year":"2018","unstructured":"Balthazar Bauer , Pooya Farshim , and Sogol Mazaheri . 2018 . Combiners for Backdoored Random Oracles. In CRYPTO 2018. Springer , 272 - 302 . Balthazar Bauer, Pooya Farshim, and Sogol Mazaheri. 2018. Combiners for Backdoored Random Oracles. In CRYPTO 2018. Springer, 272-302."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_3"},{"key":"e_1_3_2_1_18_1","volume-title":"Marc Van Kreveld, and Godfried Toussaint","author":"Bose Prosenjit","year":"1998","unstructured":"Prosenjit Bose , Marc Van Kreveld, and Godfried Toussaint . 1998 . Filling polyhedral molds. Comput.-Aided Des . 30, 4 ( 1998 ), 245-254. Prosenjit Bose, Marc Van Kreveld, and Godfried Toussaint. 1998. Filling polyhedral molds. Comput.-Aided Des. 30, 4 ( 1998 ), 245-254."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840761"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/110853327"},{"key":"e_1_3_2_1_21_1","volume-title":"arXiv","author":"Cabello Sergio","year":"1903","unstructured":"Sergio Cabello , Jean Cardinal , John Iacono , Stefan Langerman , Pat Morin , and Aur\u00e9lien Ooms . 2019. Encoding 3SUM. arXiv : 1903 . 02645 ( 2019 ). Sergio Cabello, Jean Cardinal, John Iacono, Stefan Langerman, Pat Morin, and Aur\u00e9lien Ooms. 2019. Encoding 3SUM. arXiv: 1903. 02645 ( 2019 )."},{"key":"e_1_3_2_1_22_1","first-page":"31","volume-title":"STOC","author":"Timothy","year":"2015","unstructured":"Timothy M. Chan and Moshe Lewenstein. 2015. Clustered Integer 3SUM via Additive Combinatorics . In STOC 2015 . ACM, 31 - 40 . Timothy M. Chan and Moshe Lewenstein. 2015. Clustered Integer 3SUM via Additive Combinatorics. In STOC 2015. ACM, 31-40."},{"key":"e_1_3_2_1_23_1","first-page":"468","volume-title":"CCS","author":"Checkoway Stephen","year":"2016","unstructured":"Stephen Checkoway , Jacob Maskiewicz , Christina Garman , Joshua Fried , Shaanan Cohney , Matthew Green , Nadia Heninger , Ralf-Philipp Weinmann , Eric Rescorla , and Hovav Shacham . 2016 . A Systematic Analysis of the Juniper Dual EC Incident . In CCS 2016. ACM, 468 - 479 . Stephen Checkoway, Jacob Maskiewicz, Christina Garman, Joshua Fried, Shaanan Cohney, Matthew Green, Nadia Heninger, Ralf-Philipp Weinmann, Eric Rescorla, and Hovav Shacham. 2016. A Systematic Analysis of the Juniper Dual EC Incident. In CCS 2016. ACM, 468-479."},{"key":"e_1_3_2_1_24_1","first-page":"319","article-title":"On the Practical Exploitability of Dual EC in TLS Implementations","volume":"2014","author":"Checkoway Stephen","year":"2014","unstructured":"Stephen Checkoway , Ruben Niederhagen , Adam Everspaugh , Matthew Green , Tanja Lange , Thomas Ristenpart , Daniel J. Bernstein , Jake Maskiewicz , Hovav Shacham , and Matthew Fredrikson . 2014 . On the Practical Exploitability of Dual EC in TLS Implementations . In USENIX 2014. 319 - 335 . Stephen Checkoway, Ruben Niederhagen, Adam Everspaugh, Matthew Green, Tanja Lange, Thomas Ristenpart, Daniel J. Bernstein, Jake Maskiewicz, Hovav Shacham, and Matthew Fredrikson. 2014. On the Practical Exploitability of Dual EC in TLS Implementations. In USENIX 2014. 319-335.","journal-title":"USENIX"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02441-2_15"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Otfried Cheong Alon Efrat and Sariel Har-Peled. 2007. Finding a guard that sees most and a shop that sells most. Discrete Comput. Geom. 37 4 ( 2007 ) 545-563.  Otfried Cheong Alon Efrat and Sariel Har-Peled. 2007. Finding a guard that sees most and a shop that sells most. Discrete Comput. Geom. 37 4 ( 2007 ) 545-563.","DOI":"10.1007\/s00454-007-1328-5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_23"},{"key":"e_1_3_2_1_28_1","first-page":"227","volume-title":"Random Oracles and Non-uniformity. In EUROCRYPT","author":"Coretti Sandro","year":"2018","unstructured":"Sandro Coretti , Yevgeniy Dodis , Siyao Guo , and John P. Steinberger . 2018 . Random Oracles and Non-uniformity. In EUROCRYPT 2018 . Springer , 227 - 258 . Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. 2018. Random Oracles and Non-uniformity. In EUROCRYPT 2018. Springer, 227-258."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Henry Corrigan-Gibbs and Dmitry Kogan. 2019. The Function-Inversion Problem: Barriers and Opportunities. In TCC.  Henry Corrigan-Gibbs and Dmitry Kogan. 2019. The Function-Inversion Problem: Barriers and Opportunities. In TCC.","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"e_1_3_2_1_30_1","first-page":"649","volume-title":"CRYPTO","author":"De Anindya","year":"2010","unstructured":"Anindya De , Luca Trevisan , and Madhur Tulsiani . 2010 . Time Space Tradeofs for Attacks against One-Way Functions and PRGs . In CRYPTO 2010. Springer , 649 - 665 . Anindya De, Luca Trevisan, and Madhur Tulsiani. 2010. Time Space Tradeofs for Attacks against One-Way Functions and PRGs. In CRYPTO 2010. Springer, 649-665."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00045-3"},{"key":"e_1_3_2_1_32_1","volume-title":"Vadhan","author":"Demaine Erik D.","year":"2001","unstructured":"Erik D. Demaine and Salil P . Vadhan . 2001 . Some notes on 3SUM. Unpublished manuscript. Erik D. Demaine and Salil P. Vadhan. 2001. Some notes on 3SUM. Unpublished manuscript."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_39"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46800-5_5"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-56614-6_16"},{"key":"e_1_3_2_1_36_1","volume-title":"Static Data Structure Lower Bounds Imply Rigidity. In STOC","author":"Dvir Zeev","year":"2019","unstructured":"Zeev Dvir , Alexander Golovnev , and Omri Weinstein . 2019 . Static Data Structure Lower Bounds Imply Rigidity. In STOC 2019. ACM. Zeev Dvir, Alexander Golovnev, and Omri Weinstein. 2019. Static Data Structure Lower Bounds Imply Rigidity. In STOC 2019. ACM."},{"key":"e_1_3_2_1_37_1","unstructured":"Jef Erickson. 1999. Bounds for Linear Satisfiability Problems. Chicago J. Theor. Comput. Sci. ( 1999 ).  Jef Erickson. 1999. Bounds for Linear Satisfiability Problems. Chicago J. Theor. Comput. Sci. ( 1999 )."},{"key":"e_1_3_2_1_38_1","volume-title":"Mount","author":"Erickson Jef","year":"2006","unstructured":"Jef Erickson , Sariel Har-Peled , and David M . Mount . 2006 . On the least median square problem. Discrete Comput. Geom . 36, 4 ( 2006 ), 593-607. Jef Erickson, Sariel Har-Peled, and David M. Mount. 2006. On the least median square problem. Discrete Comput. Geom. 36, 4 ( 2006 ), 593-607."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280512"},{"key":"e_1_3_2_1_40_1","first-page":"105","article-title":"Backdoored Hash Functions: Immunizing HMAC and HKDF. In CSF 2018","author":"Fischlin Marc","year":"2018","unstructured":"Marc Fischlin , Christian Janson , and Sogol Mazaheri . 2018 . Backdoored Hash Functions: Immunizing HMAC and HKDF. In CSF 2018 . IEEE , 105 - 118 . Marc Fischlin, Christian Janson, and Sogol Mazaheri. 2018. Backdoored Hash Functions: Immunizing HMAC and HKDF. In CSF 2018. IEEE, 105-118.","journal-title":"IEEE"},{"key":"e_1_3_2_1_41_1","volume-title":"Overmars","author":"Gajentaan Anka","year":"1995","unstructured":"Anka Gajentaan and Mark H . Overmars . 1995 . On a class of (2) problems in computational geometry. Comput. Geom . 5, 3 ( 1995 ), 165-185. Anka Gajentaan and Mark H. Overmars. 1995. On a class of (2) problems in computational geometry. Comput. Geom. 5, 3 ( 1995 ), 165-185."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443276"},{"key":"e_1_3_2_1_43_1","first-page":"305","article-title":"Lower Bounds on the Eficiency of Generic Cryptographic Constructions. In FOCS 2000","author":"Gennaro Rosario","year":"2000","unstructured":"Rosario Gennaro and Luca Trevisan . 2000 . Lower Bounds on the Eficiency of Generic Cryptographic Constructions. In FOCS 2000 . IEEE , 305 - 313 . Rosario Gennaro and Luca Trevisan. 2000. Lower Bounds on the Eficiency of Generic Cryptographic Constructions. In FOCS 2000. IEEE, 305-313.","journal-title":"IEEE"},{"key":"e_1_3_2_1_44_1","volume-title":"Foundations of Cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2001. Foundations of Cryptography . Vol. I . Basic tools. Cambridge University Press . Oded Goldreich. 2001. Foundations of Cryptography. Vol. I. Basic tools. Cambridge University Press."},{"key":"e_1_3_2_1_45_1","volume-title":"ESA","author":"Goldstein Isaac","year":"2016","unstructured":"Isaac Goldstein , Tsvi Kopelowitz , Moshe Lewenstein , and Ely Porat . 2016 . How Hard is it to Find (Honest) Witnesses? . In ESA 2016. 45 : 1-45 : 16. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. 2016. How Hard is it to Find (Honest) Witnesses?. In ESA 2016. 45 : 1-45 : 16."},{"key":"e_1_3_2_1_46_1","first-page":"421","volume-title":"WADS","author":"Goldstein Isaac","year":"2017","unstructured":"Isaac Goldstein , Tsvi Kopelowitz , Moshe Lewenstein , and Ely Porat . 2017 . Conditional lower bounds for space\/time tradeofs . In WADS 2017. Springer , 421 - 436 . Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. 2017. Conditional lower bounds for space\/time tradeofs. In WADS 2017. Springer, 421-436."},{"key":"e_1_3_2_1_47_1","volume-title":"Orthogonal Vectors Indexing. In ISAAC","author":"Goldstein Isaac","year":"2017","unstructured":"Isaac Goldstein , Moshe Lewenstein , and Ely Porat . 2017 . Orthogonal Vectors Indexing. In ISAAC 2017. 40 : 1-40 : 12. Isaac Goldstein, Moshe Lewenstein, and Ely Porat. 2017. Orthogonal Vectors Indexing. In ISAAC 2017. 40 : 1-40 : 12."},{"key":"e_1_3_2_1_48_1","volume-title":"3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. CoRR abs\/","author":"Golovnev Alexander","year":"1907","unstructured":"Alexander Golovnev , Siyao Guo , Thibaut Horel , Sunoo Park , and Vinod Vaikuntanathan . 2019. 3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. CoRR abs\/ 1907 .08355 ( 2019 ). arXiv: 1907.08355 http:\/\/arxiv.org\/abs\/ 1907.08355 Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park, and Vinod Vaikuntanathan. 2019. 3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications. CoRR abs\/ 1907.08355 ( 2019 ). arXiv: 1907.08355 http:\/\/arxiv.org\/abs\/ 1907.08355"},{"key":"e_1_3_2_1_49_1","unstructured":"Matthew Green. 2013. A few more notes on NSA random number generators. https:\/\/blog.cryptographyengineering.com\/ 2013 \/12\/28\/a-few-more-noteson-nsa-random-number\/  Matthew Green. 2013. A few more notes on NSA random number generators. https:\/\/blog.cryptographyengineering.com\/ 2013 \/12\/28\/a-few-more-noteson-nsa-random-number\/"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056220"},{"key":"e_1_3_2_1_51_1","unstructured":"Russell Impagliazzo. 1996. Very strong one-way functions and pseudo-random generators exist relative to a random oracle. Unpublished manuscript.  Russell Impagliazzo. 1996. Very strong one-way functions and pseudo-random generators exist relative to a random oracle. Unpublished manuscript."},{"key":"e_1_3_2_1_52_1","first-page":"44","volume-title":"Limits on the Provable Consequences of One-Way Permutations. In STOC","author":"Impagliazzo Russell","year":"1989","unstructured":"Russell Impagliazzo and Steven Rudich . 1989 . Limits on the Provable Consequences of One-Way Permutations. In STOC 1989. ACM, 44 - 61 . Russell Impagliazzo and Steven Rudich. 1989. Limits on the Provable Consequences of One-Way Permutations. In STOC 1989. ACM, 44-61."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.149"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Zahra Jafargholi and Emanuele Viola. 2016. 3SUM 3XOR Triangles. Algorithmica 74 1 ( 2016 ) 326-343.  Zahra Jafargholi and Emanuele Viola. 2016. 3SUM 3XOR Triangles. Algorithmica 74 1 ( 2016 ) 326-343.","DOI":"10.1007\/s00453-014-9946-9"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"e_1_3_2_1_56_1","volume-title":"The Strong 3SUM-INDEXING Conjecture is False. arXiv","author":"Kopelowitz Tsvi","year":"1907","unstructured":"Tsvi Kopelowitz and Ely Porat . 2019. The Strong 3SUM-INDEXING Conjecture is False. arXiv : 1907 . 11206 ( 2019 ). Tsvi Kopelowitz and Ely Porat. 2019. The Strong 3SUM-INDEXING Conjecture is False. arXiv: 1907. 11206 ( 2019 )."},{"key":"e_1_3_2_1_57_1","first-page":"293","article-title":"Higher Cell Probe Lower Bounds for Evaluating Polynomials. In FOCS 2012","author":"Larsen Kasper Green","year":"2012","unstructured":"Kasper Green Larsen . 2012 . Higher Cell Probe Lower Bounds for Evaluating Polynomials. In FOCS 2012 . IEEE , 293 - 301 . Kasper Green Larsen. 2012. Higher Cell Probe Lower Bounds for Evaluating Polynomials. In FOCS 2012. IEEE, 293-301.","journal-title":"IEEE"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190898"},{"key":"e_1_3_2_1_60_1","unstructured":"Moni Naor. 2013. Cryptography and Data Structures: A Match Made in Heaven. View online at: https:\/\/www.youtube.com\/watch?v= hCmbLypK0xE. The Sixth Israel CS Theory Day 13 \/3\/2013.  Moni Naor. 2013. Cryptography and Data Structures: A Match Made in Heaven. View online at: https:\/\/www.youtube.com\/watch?v= hCmbLypK0xE. The Sixth Israel CS Theory Day 13 \/3\/2013."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_51"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48000-7_28"},{"key":"e_1_3_2_1_63_1","unstructured":"NIST (National Institute of Standards and Technology). 2001. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197. Available online at: https:\/\/nvlpubs.nist.gov\/nistpubs\/FIPS\/NIST.FIPS. 197.pdf.  NIST (National Institute of Standards and Technology). 2001. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197. Available online at: https:\/\/nvlpubs.nist.gov\/nistpubs\/FIPS\/NIST.FIPS. 197.pdf."},{"key":"e_1_3_2_1_64_1","unstructured":"NIST (National Institute of Standards and Technology). 2015. SHA-3 Standard. Federal Information Processing Standards Publication 202. https:\/\/nvlpubs.nist. gov\/nistpubs\/FIPS\/NIST.FIPS. 202.pdf.  NIST (National Institute of Standards and Technology). 2015. SHA-3 Standard. Federal Information Processing Standards Publication 202. https:\/\/nvlpubs.nist. gov\/nistpubs\/FIPS\/NIST.FIPS. 202.pdf."},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.82"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_1_68_1","article-title":"Unifying the landscape of cell-probe lower bounds","volume":"40","author":"Pa\u02c7tra\u015fcu Mihai","year":"2011","unstructured":"Mihai Pa\u02c7tra\u015fcu . 2011 . Unifying the landscape of cell-probe lower bounds . SIAM J. Comput. 40 , 3 ( 2011 ), 827-847. Mihai Pa\u02c7tra\u015fcu. 2011. Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40, 3 ( 2011 ), 827-847.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_69_1","volume-title":"Higher Lower Bounds from the 3SUM Conjecture. View online at: https:\/\/www.youtube.com\/watch?v= OkagNfn7KQ","author":"Pettie Seth","year":"2015","unstructured":"Seth Pettie . 2015. Higher Lower Bounds from the 3SUM Conjecture. View online at: https:\/\/www.youtube.com\/watch?v= OkagNfn7KQ . Simons Institute Program on Fine-Grained Complexity and Algorithm Design, Fall 2015 . Seth Pettie. 2015. Higher Lower Bounds from the 3SUM Conjecture. View online at: https:\/\/www.youtube.com\/watch?v= OkagNfn7KQ. Simons Institute Program on Fine-Grained Complexity and Algorithm Design, Fall 2015."},{"key":"e_1_3_2_1_70_1","volume-title":"Equivalence of Systematic Linear Data Structures and Matrix Rigidity. arXiv","author":"Ramamoorthy Sivaramakrishnan Natarajan","year":"1910","unstructured":"Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian . 2019. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. arXiv : 1910 . 11921 ( 2019 ). Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian. 2019. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. arXiv: 1910. 11921 ( 2019 )."},{"key":"e_1_3_2_1_71_1","first-page":"241","volume-title":"Correcting Subverted Random Oracles. In CRYPTO","author":"Russell Alexander","year":"2018","unstructured":"Alexander Russell , Qiang Tang , Moti Yung , and Hong-Sheng Zhou . 2018 . Correcting Subverted Random Oracles. In CRYPTO 2018. Springer , 241 - 271 . Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou. 2018. Correcting Subverted Random Oracles. In CRYPTO 2018. Springer, 241-271."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"crossref","unstructured":"Michael Soss Jef Erickson and Mark Overmars. 2003. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom. 26 3 ( 2003 ) 235-246.  Michael Soss Jef Erickson and Mark Overmars. 2003. Preprocessing chains for fast dihedral rotations is hard or even impossible. Comput. Geom. 26 3 ( 2003 ) 235-246.","DOI":"10.1016\/S0925-7721(02)00156-6"},{"key":"e_1_3_2_1_74_1","first-page":"205","volume-title":"Random Oracles and Auxiliary Input. In CRYPTO","author":"Unruh Dominique","year":"2007","unstructured":"Dominique Unruh . 2007 . Random Oracles and Auxiliary Input. In CRYPTO 2007. Springer , 205 - 223 . Dominique Unruh. 2007. Random Oracles and Auxiliary Input. In CRYPTO 2007. Springer, 205-223."},{"key":"e_1_3_2_1_75_1","first-page":"162","article-title":"Graph-Theoretic Arguments in Low-Level Complexity","volume":"1977","author":"Valiant Leslie G.","year":"1977","unstructured":"Leslie G. Valiant . 1977 . Graph-Theoretic Arguments in Low-Level Complexity . In MFCS 1977. 162 - 176 . Leslie G. Valiant. 1977. Graph-Theoretic Arguments in Low-Level Complexity. In MFCS 1977. 162-176.","journal-title":"MFCS"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536477"},{"key":"e_1_3_2_1_77_1","first-page":"186","article-title":"Lower bounds for data structures with space close to maximum imply circuit lower bounds","volume":"25","author":"Viola Emanuele","year":"2018","unstructured":"Emanuele Viola . 2018 . Lower bounds for data structures with space close to maximum imply circuit lower bounds .. In ECCC , Vol. 25. 186 . Emanuele Viola. 2018. Lower bounds for data structures with space close to maximum imply circuit lower bounds.. In ECCC, Vol. 25. 186.","journal-title":"ECCC"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100226"},{"key":"e_1_3_2_1_79_1","volume-title":"Young and Moti Yung","author":"Adam","year":"1996","unstructured":"Adam L. Young and Moti Yung . 1996 . Cryptovirology : Extortion-Based Security Threats and Countermeasures. In S &P. IEEE , 129-140. Adam L. Young and Moti Yung. 1996. Cryptovirology: Extortion-Based Security Threats and Countermeasures. In S &P. IEEE, 129-140."},{"key":"e_1_3_2_1_80_1","volume-title":"Young and Moti Yung","author":"Adam","year":"1996","unstructured":"Adam L. Young and Moti Yung . 1996 . The Dark Side of \u201cBlack-Box\u201d Cryptography, or: Should We Trust Capstone?. In CRYPTO. Springer , 89-103. Adam L. Young and Moti Yung. 1996. The Dark Side of \u201cBlack-Box\u201d Cryptography, or: Should We Trust Capstone?. In CRYPTO. Springer, 89-103."},{"key":"e_1_3_2_1_81_1","volume-title":"Young and Moti Yung","author":"Adam","year":"1997","unstructured":"Adam L. Young and Moti Yung . 1997 . Kleptography : Using Cryptography Against Cryptography. In EUROCRYPT 1997. Springer , 62-74. Adam L. Young and Moti Yung. 1997. Kleptography: Using Cryptography Against Cryptography. In EUROCRYPT 1997. Springer, 62-74."},{"key":"e_1_3_2_1_82_1","volume-title":"MFCS 1998, Workshop \u201cRandomized Algorithms\u201d.","author":"Zimand Marius","year":"1998","unstructured":"Marius Zimand . 1998 . Eficient privatization of random bits . In MFCS 1998, Workshop \u201cRandomized Algorithms\u201d. Marius Zimand. 1998. Eficient privatization of random bits. In MFCS 1998, Workshop \u201cRandomized Algorithms\u201d."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384342","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":82,"alternative-id":["10.1145\/3357713.3384342","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384342","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}