Data structures provide a mechanism to organize data, usually providing methods to insert, delete, and search elements. Probabilistic data structures such as skip lists, hash tables, and Cuckoo hashing use randomized strategies to improve the efficiency, often yielding better average-case results for some operations. The performance analyses of these probabilistic data structures, however, usually hinge on non-adversarially chosen inputs. In this talk we discuss that these performance guarantees cannot be upheld for maliciously chosen data and present remedies against such vulnerabilities.

Marc Fischlin is Professor for Cryptography and Complexity Theory at the Technische Universität Darmstadt. Marc is a regular author and program committee member for the flagship security and cryptography  conferences. Marc has been the program chair of Eurocrypt 2015 and 2016 and acted as the general chair for Eurocrypt 2019. He is the spokesperson of the collaborative research center CROSSING for cryptography-based security solutions and of the profile topic Cybersecurity at TU Darmstadt.