{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T00:29:56Z","timestamp":1766449796485,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"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":[[2022,11,7]]},"DOI":"10.1145\/3548606.3560621","type":"proceedings-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T11:41:28Z","timestamp":1667821288000},"page":"1037-1050","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Adversarial Correctness and Privacy for Probabilistic Data Structures"],"prefix":"10.1145","author":[{"given":"Mia","family":"Filic","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}]},{"given":"Kenneth G.","family":"Paterson","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}]},{"given":"Anupama","family":"Unnikrishnan","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}]},{"given":"Fernando","family":"Virdia","sequence":"additional","affiliation":[{"name":"Intel Labs, Z\u00fcrich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"volume-title":"SipHash: a fast short-input PRF","author":"Aumasson Jean-Philippe","key":"e_1_3_2_1_2_1","unstructured":"Jean-Philippe Aumasson and Daniel J Bernstein . 2012. SipHash: a fast short-input PRF . In INDOCRYPT. Springer . Jean-Philippe Aumasson and Daniel J Bernstein. 2012. SipHash: a fast short-input PRF. In INDOCRYPT. Springer."},{"key":"e_1_3_2_1_3_1","volume-title":"Cheswick","author":"Bellovin Steven M.","year":"2004","unstructured":"Steven M. Bellovin and William R . Cheswick . 2004 . Privacy-Enhanced Searches Using Encrypted Bloom Filters. Cryptology ePrint Archive, Report 2004\/022. (2004). Steven M. Bellovin and William R. Cheswick. 2004. Privacy-Enhanced Searches Using Encrypted Bloom Filters. Cryptology ePrint Archive, Report 2004\/022. (2004)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33627-0_27"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Dan Boneh Eyal Kushilevitz Rafail Ostrovsky and William E Skeith. 2007. Public key encryption that allows PIR queries. In CRYPTO.  Dan Boneh Eyal Kushilevitz Rafail Ostrovsky and William E Skeith. 2007. Public key encryption that allows PIR queries. In CRYPTO.","DOI":"10.1007\/978-3-540-74143-5_4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426746.3434063"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_3_2_1_11_1","volume-title":"Hash table implementations vulnerable to algorithmic complexity attacks. https:\/\/www.kb.cert.org\/vuls\/id\/903934. (December","author":"CERT Coordination Center","year":"2011","unstructured":"CERT Coordination Center . 2011. Hash table implementations vulnerable to algorithmic complexity attacks. https:\/\/www.kb.cert.org\/vuls\/id\/903934. (December 2011 ). CERT Coordination Center. 2011. Hash table implementations vulnerable to algorithmic complexity attacks. https:\/\/www.kb.cert.org\/vuls\/id\/903934. (December 2011)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"David Clayton Christopher Patton and Thomas Shrimpton. 2019. Probabilistic data structures in adversarial environments. In ACM SIGSAC CCS.  David Clayton Christopher Patton and Thomas Shrimpton. 2019. Probabilistic data structures in adversarial environments. In ACM SIGSAC CCS.","DOI":"10.1145\/3319535.3354235"},{"key":"e_1_3_2_1_13_1","unstructured":"Graham Cormode. 2008. Count-Min Sketch. Springer US 1--6. https:\/\/doi.org\/10. 1007\/978-3-642-27848-8_579--1  Graham Cormode. 2008. Count-Min Sketch. Springer US 1--6. https:\/\/doi.org\/10. 1007\/978-3-642-27848-8_579--1"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_1_15_1","volume-title":"USENIX Security Symposium. 29--44","author":"Crosby Scott A","year":"2003","unstructured":"Scott A Crosby and Dan S Wallach . 2003 . Denial of Service via Algorithmic Complexity Attacks .. In USENIX Security Symposium. 29--44 . Scott A Crosby and Dan S Wallach. 2003. Denial of Service via Algorithmic Complexity Attacks.. In USENIX Security Symposium. 29--44."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0018"},{"key":"e_1_3_2_1_17_1","volume-title":"Mitzenmacher","author":"Fan Bin","year":"2014","unstructured":"Bin Fan , Dave G. Andersen , Michael Kaminsky , and Michael D . Mitzenmacher . 2014 . Cuckoo Filter : Practically Better Than Bloom. In Proceedings of CoNEXT '14. https:\/\/doi.org\/10.1145\/2674005.2674994 10.1145\/2674005.2674994 Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. Cuckoo Filter: Practically Better Than Bloom. In Proceedings of CoNEXT '14. https:\/\/doi.org\/10.1145\/2674005.2674994"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hy- perloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science. 137--156.  Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hy- perloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science. 137--156.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2015.21"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2664243.2664267"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811056"},{"key":"e_1_3_2_1_23_1","volume-title":"NeurIPS","author":"Hassidim Avinatan","year":"2020","unstructured":"Avinatan Hassidim , Haim Kaplan , Yishay Mansour , Yossi Matias , and Uri Stemmer . 2020. Adversarially Robust Streaming Algorithms via Differential Privacy . In NeurIPS 2020 . https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/ 0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. 2020. Adversarially Robust Streaming Algorithms via Differential Privacy. In NeurIPS 2020. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/ 0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Haim Kaplan Yishay Mansour Kobbi Nissim and Uri Stemmer. 2021. Separating adaptive streaming from oblivious streaming using the bounded storage model. In CRYPTO.  Haim Kaplan Yishay Mansour Kobbi Nissim and Uri Stemmer. 2021. Separating adaptive streaming from oblivious streaming using the bounded storage model. In CRYPTO.","DOI":"10.1007\/978-3-030-84252-9_4"},{"volume-title":"A constraint satisfaction cryptanalysis of Bloom filters in private record linkage","author":"Kuzu Mehmet","key":"e_1_3_2_1_25_1","unstructured":"Mehmet Kuzu , Murat Kantarcioglu , Elizabeth Durham , and Bradley Malin . 2011. A constraint satisfaction cryptanalysis of Bloom filters in private record linkage . In PETS. Springer . Mehmet Kuzu, Murat Kantarcioglu, Elizabeth Durham, and Bradley Malin. 2011. A constraint satisfaction cryptanalysis of Bloom filters in private record linkage. In PETS. Springer."},{"volume-title":"CRLite: A scalable system for pushing all TLS revocations to all browsers","author":"Larisch James","key":"e_1_3_2_1_26_1","unstructured":"James Larisch , David Choffnes , Dave Levin , Bruce M Maggs , Alan Mislove , and Christo Wilson . 2017. CRLite: A scalable system for pushing all TLS revocations to all browsers . In IEEE S &P. James Larisch, David Choffnes, Dave Levin, Bruce M Maggs, Alan Mislove, and Christo Wilson. 2017. CRLite: A scalable system for pushing all TLS revocations to all browsers. In IEEE S&P."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190898"},{"key":"e_1_3_2_1_29_1","volume-title":"Efficient counting of k-mers in DNA sequences using a bloom filter. BMC Bioinformatics 12","author":"Melsted P\u00e1ll","year":"2011","unstructured":"P\u00e1ll Melsted and Jonathan K Pritchard . 2011. Efficient counting of k-mers in DNA sequences using a bloom filter. BMC Bioinformatics 12 ( 2011 ). P\u00e1ll Melsted and Jonathan K Pritchard. 2011. Efficient counting of k-mers in DNA sequences using a bloom filter. BMC Bioinformatics 12 (2011)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Moni Naor and Eylon Yogev. 2015. Bloom filters in adversarial environments. In CRYPTO.  Moni Naor and Eylon Yogev. 2015. Bloom filters in adversarial environments. In CRYPTO.","DOI":"10.1007\/978-3-662-48000-7_28"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306193"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1745475.1745477"},{"key":"e_1_3_2_1_33_1","volume-title":"HyperLogLog: Exponentially Bad in Adversarial Settings. In 7th IEEE European Symposium on Security and Privacy, Euro S&P 2022","author":"Kenneth","year":"2022","unstructured":"Kenneth G. Paterson and Mathilde Raynal. 2022 . HyperLogLog: Exponentially Bad in Adversarial Settings. In 7th IEEE European Symposium on Security and Privacy, Euro S&P 2022 , Genoa, Italy , June 6-10, 2022 . IEEE, 154--170. https:\/\/doi. org\/10.1109\/EuroSP53844.2022.00018 Kenneth G. Paterson and Mathilde Raynal. 2022. HyperLogLog: Exponentially Bad in Adversarial Settings. In 7th IEEE European Symposium on Security and Privacy, Euro S&P 2022, Genoa, Italy, June 6-10, 2022. IEEE, 154--170. https:\/\/doi. org\/10.1109\/EuroSP53844.2022.00018"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/eScience.2012.6404484"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1655008"},{"key":"e_1_3_2_1_36_1","volume-title":"Woodruff and Samson Zhou","author":"David","year":"2020","unstructured":"David P. Woodruff and Samson Zhou . 2020 . Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR abs\/2011.07471 (2020). arXiv:2011.07471 https:\/\/arxiv.org\/abs\/2011.07471 David P. Woodruff and Samson Zhou. 2020. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR abs\/2011.07471 (2020). arXiv:2011.07471 https:\/\/arxiv.org\/abs\/2011.07471"}],"event":{"name":"CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"],"location":"Los Angeles CA USA","acronym":"CCS '22"},"container-title":["Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560621","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3548606.3560621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:58Z","timestamp":1750182538000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3548606.3560621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":34,"alternative-id":["10.1145\/3548606.3560621","10.1145\/3548606"],"URL":"https:\/\/doi.org\/10.1145\/3548606.3560621","relation":{},"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"2022-11-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}