Prof. Dr. Marc Fischlin, TU Darmstadt

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.