{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T20:07:38Z","timestamp":1778789258058,"version":"3.51.4"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"I-CORE Program of the Planning and Budgeting Committee, the Israel Science Foundation, BSF, and the Israeli Ministry of Science and Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are\n            <jats:italic>independent<\/jats:italic>\n            of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the\n            <jats:italic>adversarial model<\/jats:italic>\n            . Roughly speaking, this model allows an adversary to choose inputs and queries\n            <jats:italic>adaptively<\/jats:italic>\n            according to previous responses. Specifically, we consider a data structure known as a \u201cBloom filter\u201d and prove a tight connection between Bloom filters in this model and cryptography.\n          <\/jats:p>\n          <jats:p>\n            A Bloom filter represents a set\n            <jats:italic>S<\/jats:italic>\n            of elements approximately by using fewer bits than a precise representation. The price for succinctness is allowing for some errors: For any\n            <jats:italic>x \u2208 S<\/jats:italic>\n            , it should always answer Yes, and for any\n            <jats:italic>x \u2209 S<\/jats:italic>\n            it should answer Yes only with small probability.\n          <\/jats:p>\n          <jats:p>\n            In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the number of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries, we show that there exists a Bloom filter for sets of size\n            <jats:italic>n<\/jats:italic>\n            and error\n            <jats:italic>\u03b5<\/jats:italic>\n            that is secure against\n            <jats:italic>t<\/jats:italic>\n            queries and uses only\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log 1\/\u03b5 +\n            <jats:italic>t<\/jats:italic>\n            ) bits of memory. In comparison,\n            <jats:italic>n<\/jats:italic>\n            log 1\/\u03b5 is the best possible under a non-adaptive adversary.\n          <\/jats:p>","DOI":"10.1145\/3306193","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Bloom Filters in Adversarial Environments"],"prefix":"10.1145","volume":"15","author":[{"given":"Moni","family":"Naor","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8599-2472","authenticated-orcid":false,"given":"Yogev","family":"Eylon","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Austin Appleby. 2011. Murmurhash3 64-bit Finalizer. Technical Report. Version 19\/02\/15. Retrieved from https:\/\/code.google. com\/p\/smhasher\/wiki\/MurmurHash3.  Austin Appleby. 2011. Murmurhash3 64-bit Finalizer. Technical Report. Version 19\/02\/15. Retrieved from https:\/\/code.google. com\/p\/smhasher\/wiki\/MurmurHash3."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38980-1_8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9840-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 13th Annual International Advances in Cryptology Conference (CRYPTO\u201993)","author":"Blum Avrim","unstructured":"Avrim Blum , Merrick L. Furst , Michael J. Kearns , and Richard J. Lipton . 1993. Cryptographic primitives based on hard learning problems . In Proceedings of the 13th Annual International Advances in Cryptology Conference (CRYPTO\u201993) . 278--291. Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. 1993. Cryptographic primitives based on hard learning problems. In Proceedings of the 13th Annual International Advances in Cryptology Conference (CRYPTO\u201993). 278--291."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978)","author":"Carter Larry","unstructured":"Larry Carter , Robert W. Floyd , John Gill , George Markowsky , and Mark N. Wegman . 1978. Exact and approximate membership testers . In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978) . 59--65. Larry Carter, Robert W. Floyd, John Gill, George Markowsky, and Mark N. Wegman. 1978. Exact and approximate membership testers. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978). 59--65."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , and Ayellet Tal . 2004 . The Bloomier filter: An efficient data structure for static support lookup tables . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . 30--39. Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. 2004. The Bloomier filter: An efficient data structure for static support lookup tables. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). 30--39."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2004.1268997"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 3rd Theory of Cryptography Conference (TCC\u201906)","author":"Dwork Cynthia","unstructured":"Cynthia Dwork , Frank McSherry , Kobbi Nissim , and Adam D. Smith . 2006. Calibrating noise to sensitivity in private data analysis . In Proceedings of the 3rd Theory of Cryptography Conference (TCC\u201906) . 265--284. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference (TCC\u201906). 265--284."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_21_1","volume-title":"The Foundations of Cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich . 2001. The Foundations of Cryptography , Volume 1 , Basic Techniques. Cambridge University Press . Oded Goldreich. 2001. The Foundations of Cryptography, Volume 1, Basic Techniques. Cambridge University Press."},{"key":"e_1_2_1_22_1","volume-title":"Intel\u2019s New AES Instructions for Enhanced Performance and Security","author":"Gueron Shay","unstructured":"Shay Gueron . 2009. Intel\u2019s New AES Instructions for Enhanced Performance and Security . Springer , Berlin , 51--66. Shay Gueron. 2009. Intel\u2019s New AES Instructions for Enhanced Performance and Security. Springer, Berlin, 51--66."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Symposium on Theory of Computing Conference (STOC\u201913)","author":"Hardt Moritz","unstructured":"Moritz Hardt and David P. Woodruff . 2013. How robust are linear sketches to adaptive inputs? In Proceedings of the Symposium on Theory of Computing Conference (STOC\u201913) . 121--130. Moritz Hardt and David P. Woodruff. 2013. How robust are linear sketches to adaptive inputs? In Proceedings of the Symposium on Theory of Computing Conference (STOC\u201913). 121--130."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_2_1_25_1","unstructured":"Bob Jenkins. 2006. lookup3.c. Retrieved at http:\/\/burtleburtle.net\/bob\/c\/lookup3.c.  Bob Jenkins. 2006. lookup3.c. Retrieved at http:\/\/burtleburtle.net\/bob\/c\/lookup3.c."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140277.1140317"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190898"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00032-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733772"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT\u201914)","author":"Morris Ben","year":"2014","unstructured":"Ben Morris and Phillip Rogaway . 2014 . Sometimes-recurse shuffle - Almost-random permutations in logarithmic expected time . In Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT\u201914) . 311--326. Ben Morris and Phillip Rogaway. 2014. Sometimes-recurse shuffle - Almost-random permutations in logarithmic expected time. In Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology (EUROCRYPT\u201914). 311--326."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.52778"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003817"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906)","author":"Naor Moni","unstructured":"Moni Naor and Guy N. Rothblum . 2006. Learning to impersonate . In Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906) . 649--656. Moni Naor and Guy N. Rothblum. 2006. Learning to impersonate. In Proceedings of the 23rd International Conference on Machine Learning (ICML\u201906). 649--656."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0007-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/060658400"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Pagh Anna","unstructured":"Anna Pagh , Rasmus Pagh , and S. Srinivasa Rao . 2005. An optimal Bloom filter replacement . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . 823--829. Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao. 2005. An optimal Bloom filter replacement. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 823--829."},{"key":"e_1_2_1_38_1","volume-title":"Encyclopedia of Algorithms","author":"Pagh Rasmus","unstructured":"Rasmus Pagh . 2008. Cuckoo hashing . In Encyclopedia of Algorithms . Springer . Rasmus Pagh. 2008. Cuckoo hashing. In Encyclopedia of Algorithms. Springer."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP\u201914)","author":"Pappas Vasilis","unstructured":"Vasilis Pappas , Fernando Krell , Binh Vo , Vladimir Kolesnikov , Tal Malkin , Seung Geol Choi , Wesley George , Angelos D. Keromytis , and Steven M. Bellovin . 2014. Blind Seer: A scalable private DBMS . In Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP\u201914) . 359--374. Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos D. Keromytis, and Steven M. Bellovin. 2014. Blind Seer: A scalable private DBMS. In Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP\u201914). 359--374."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78978"},{"key":"e_1_2_1_43_1","unstructured":"Geoff Pike and Jyrki Alakuijala. 2011. Introducing cityhash. Retrieved from http:\/\/google-opensource.blogspot.com\/2011\/04\/introducing-cityhash.html.  Geoff Pike and Jyrki Alakuijala. 2011. Introducing cityhash. Retrieved from http:\/\/google-opensource.blogspot.com\/2011\/04\/introducing-cityhash.html."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1594230"},{"key":"e_1_2_1_45_1","first-page":"254","article-title":"FastPRP: Fast pseudo-random permutations for small domains","volume":"2012","author":"Stefanov Emil","year":"2012","unstructured":"Emil Stefanov and Elaine Shi . 2012 . FastPRP: Fast pseudo-random permutations for small domains . IACR Cryptology ePrint Archive 2012 (2012), 254 . Emil Stefanov and Elaine Shi. 2012. FastPRP: Fast pseudo-random permutations for small domains. IACR Cryptology ePrint Archive 2012 (2012), 254.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSAC.2006.26"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.98"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 2004 IEEE International Conference on Cluster Computing (CLUSTER\u201904)","author":"Zhu Yifeng","year":"2004","unstructured":"Yifeng Zhu , Hong Jiang , and Jun Wang . 2004 . Hierarchical Bloom filter arrays (HBA): A novel, scalable metadata management system for large cluster-based storage . In Proceedings of the 2004 IEEE International Conference on Cluster Computing (CLUSTER\u201904) . 165--174. Yifeng Zhu, Hong Jiang, and Jun Wang. 2004. Hierarchical Bloom filter arrays (HBA): A novel, scalable metadata management system for large cluster-based storage. In Proceedings of the 2004 IEEE International Conference on Cluster Computing (CLUSTER\u201904). 165--174."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306193","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:21Z","timestamp":1750273461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3306193"],"URL":"https:\/\/doi.org\/10.1145\/3306193","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}