B. H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, vol.13, issue.7, pp.422-426, 1970.
DOI : 10.1145/362686.362692

S. A. Crosby and D. S. Wallach, Denial of Service via Algorithmic Complexity Attacks, USENIX Security Symposium, pp.3-3, 2003.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2009.

A. Appleby, SMHasher -Test your hash functions, 2010.

R. Jenkins, A Hash Function for Hash Table Lookup, 1996.

J. Aumasson and D. J. Bernstein, SipHash: A Fast Short-Input PRF, Progress in Cryptology -INDOCRYPT 2012, pp.489-508, 2012.
DOI : 10.1007/978-3-642-34931-7_28

Q. Dang, Recommendation for Applications Using Approved Hash Algorithms National Institute of Standards & Technology, 2012.

A. Broder and M. Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics, vol.1, issue.4, 2005.
DOI : 10.1080/15427951.2004.10129096

L. Fan, P. Cao, J. M. Almeida, and A. Z. Broder, Summary cache: a scalable wide-area Web cache sharing protocol, IEEE/ACM Transactions on Networking, vol.8, issue.3, pp.281-293, 2000.
DOI : 10.1109/90.851975

J. W. Byers, J. Considine, M. Mitzenmacher, and S. Rost, Informed content delivery across adaptive overlay networks, Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication -ACM SIGCOMM 2002, pp.47-60, 2002.

E. Goh, Secure Indexes Cryptology ePrint Archive, Report, vol.216216, 2003.

C. Dong, L. Chen, and Z. Wen, When private set intersection meets big data, Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, CCS '13, 2013.
DOI : 10.1145/2508859.2516701
URL : http://strathprints.strath.ac.uk/44686/1/https_eprint.iacr.org_2013_515.pdf

P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin et al., On the false-positive rate of Bloom filters, Information Processing Letters, vol.108, issue.4, pp.210-213, 2008.
DOI : 10.1016/j.ipl.2008.05.018

D. Guo, Y. Liu, X. Li, and P. Yang, False negative problem of counting bloom filter Knowledge and Data Engineering, IEEE Transactions on, vol.22, issue.5, pp.651-664, 2010.

C. Olston and M. Najork, Web Crawling, Foundations and Trends?? in Information Retrieval, vol.4, issue.3, pp.175-246, 2010.
DOI : 10.1561/1500000017

N. Nikiforakis, F. Maggi, G. Stringhini, M. Z. Rafique, W. Joosen et al., Stranger danger, Proceedings of the 23rd international conference on World wide web, WWW '14, pp.51-62, 2014.
DOI : 10.1145/2566486.2567983

N. Gupta, A. Aggarwal, and P. Kumaraguru, bit.ly/can-do-better, poster presented at Security Privacy Symposium -SPS 2014, 2014.

P. S. Almeida, C. Baquero, N. M. Preguiça, and D. Hutchison, Scalable Bloom Filters, Information Processing Letters, vol.101, issue.6, pp.255-261, 2007.
DOI : 10.1016/j.ipl.2006.10.007

A. Kirsch and M. Mitzenmacher, Less hashing, same performance: Building a better Bloom filter, Random Structures and Algorithms, vol.32, issue.2, pp.187-218, 2008.
DOI : 10.1002/rsa.20208

D. Wessels, Squid: The Definitive Guide . O'Reilly Media, 2004.

A. Rousskov and D. Wessels, Cache digests, Computer Networks and ISDN Systems, pp.22-23, 1998.
DOI : 10.1016/S0169-7552(98)00251-7

L. Carter and M. N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing , STOC '77, pp.106-112, 1977.
DOI : 10.1145/800105.803400

A. Peslyak, Designing and Attacking Port Scan Detection Tools Phrack Magazine, p.13, 1998.

N. Bar-yosef and A. Wool, Remote Algorithmic Complexity Attacks against Randomized Hash Tables, International Conference on Security and Cryptography -SECRYPT 2007, pp.117-124, 2007.
DOI : 10.1016/S1389-1286(99)00112-7

A. Klink and J. Wälde, Multiple implementations denial-of-service via hash algorithm collision Open Source Computer Security Incident Response Team, Tech. Rep. oCERT advisory, pp.2011-2014, 2011.

U. Ben-porat, A. Bremler-barr, H. Levy, and B. Plattner, On the Vulnerability of Hardware Hash Tables to Sophisticated Attacks, Networking Lecture Notes in Computer Science, vol.7289, issue.1, pp.135-148, 2012.
DOI : 10.1007/978-3-642-30045-5_11

M. D. Mcilroy, A killer adversary for quicksort, Software: Practice and Experience, vol.23, issue.4, pp.341-344, 1999.
DOI : 10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R

D. Bethea and M. K. Reiter, Data Structures with Unpredictable Timing, European Symposium on Research in Computer Security -ESORICS 2009, pp.456-471, 2009.
DOI : 10.1214/aoms/1177692631

]. L. Huang, A. D. Joseph, B. Nelson, B. I. Rubinstein, and J. D. Tygar, Adversarial machine learning, Proceedings of the 4th ACM workshop on Security and artificial intelligence, AISec '11, pp.43-58, 2011.
DOI : 10.1145/2046684.2046692

S. A. Crosby, Denial of Service through Regular Expressions, USENIX Security Symposium: Work-In-Progress Reports, p.1, 2003.

A. Papadogiannakis, M. Polychronakis, and E. P. Markatos, Tolerating Overload Attacks Against Packet Capturing Systems, USENIX Annual Technical Conference, pp.197-202, 2012.

X. Cai, Y. Gui, and R. Johnson, Exploiting Unix File-System Races via Algorithmic Complexity Attacks, 2009 30th IEEE Symposium on Security and Privacy, pp.27-41, 2009.
DOI : 10.1109/SP.2009.10

J. Mirkovic and P. L. Reiher, A taxonomy of DDoS attack and DDoS defense mechanisms, ACM SIGCOMM Computer Communication Review, vol.34, issue.2, pp.39-53, 2004.
DOI : 10.1145/997150.997156

X. Sun, L. Cheng, and Y. Zhang, A Covert Timing Channel via Algorithmic Complexity Attacks: Design and Analysis, 2011 IEEE International Conference on Communications (ICC), pp.1-5, 2011.
DOI : 10.1109/icc.2011.5962718

S. Venkataraman, D. X. Song, P. B. Gibbons, and A. Blum, New streaming algorithms for fast detection of superspreaders, Network and Distributed System Security Symposium, NDSS 2005, 2005.

S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford, Path-quality monitoring in the presence of adversaries, International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2008, pp.193-204, 2008.

R. Nojima and Y. Kadobayashi, Cryptographically Secure Bloom-Filters, Transactions on Data Privacy, vol.2, issue.2, pp.131-139, 2009.

S. Bellovin and W. R. Cheswick, Privacy-Enhanced Searches Using Encrypted Bloom Filters, DIMACS/PORTIA Workshop on Privacy-Preserving Data Mining, pp.274-285, 2004.

F. Kerschbaum, Public-Key Encrypted Bloom Filters with Applications to Supply Chain Integrity, Data and Applications Security and Privacy XXV -25th Annual IFIP WG 11.3 Conference, pp.60-75, 2011.
DOI : 10.1007/978-3-642-22348-8_7

M. Särelä, C. E. Rothenberg, A. Zahemszky, P. Nikander, and J. Ott, BloomCasting: Security in Bloom Filter Based Multicast, Nordic Conference on Secure IT Systems, pp.1-16, 2010.
DOI : 10.1145/1151659.1159917

K. Nyberg, Fast Accumulated Hashing, " in Fast Software Encryption -FSE 1996, ser, Lecture Notes in Computer Science, vol.1039, 1996.

S. Farrell, D. Kutscher, C. Dannewitz, B. Ohlman, A. Keranen et al., Naming Things with Hashes, 2013.
DOI : 10.17487/rfc6920

S. S. Lumetta and M. Mitzenmacher, Using the Power of Two Choices to Improve Bloom Filters, Internet Mathematics, vol.4, issue.1, pp.17-33, 2007.
DOI : 10.1080/15427951.2007.10129136

P. Flajolet, Theory and practice of probabilistic counting algorithms (abstract of invited talk), Workshop on Analytic Algorithmics and Combinatorics -ANALC 2004, p.152, 2004.

R. N°-8627 and R. Centre-grenoble-?-rhône-alpes, Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria, pp.249-6399