Probabilistic Data Structures in Adversarial Environments

AMQ-PDSs are a class of probabilistic data structures (PDS) that represent a set of elements and answer approximate membership queries (AMQ). Popular representatives of this class are Bloom and Cuckoo filters. One common issue many AMQ-PDSs share is that their capacity needs to be fixed during their initialization and surpassing that capacity results in the degradation of their algorithm's accuracy. To alleviate this issue, scalable variants of some AMQ-PDSs have been proposed. Scalable Cuckoo filters are a widely used instance thereof, as they are implemented in the well-known memory-first database Redis. AMQ-PDSs -including scalable Cuckoo filters -are increasingly being deployed in settings where an adversary may adaptively choose or manipulate inputs in order to reach some adversarial goal, like decreasing the accuracy of the filter's algorithms. Most analyses of AMQ-PDSs commonly found in the literature, however, assume that inputs are chosen honestly, which results in a discrepancy between theoretical performance guarantees and actual use-cases of the data structure. While several AMQ-PDSs including Bloom, Cuckoo and Counting filters have already been analyzed under adversarial assumptions, scalable Cuckoo filters remain unexamined so far in both honest and adversarial settings. Therefore, we analyze scalable Cuckoo filters in this work. To this end, we apply an existing simulation-based framework to obtain concrete bounds on the adversarial correctness guarantees they provide. Along the way, we derive new bounds on the accuracy of their algorithms assuming honestly chosen inputs, thus, also providing an analysis of scalable Cuckoo filters in an honest setting.