Adversarial Correctness and Privacy for Probabilistic Data Structures
Mia Filić and Anu Unnikrishnan
Abstract:
Probabilistic data structures (PDS) compactly represent data, at the cost of giving approximate answers to queries about the data. They are commonplace in today's computing systems, finding use in databases, networking, and more. While PDS are designed to work reliably under benign inputs, nowadays they are often used in settings where adversaries can gain benefit from carefully selecting inputs. In our work, we address these security issues - focusing on PDS that support approximate membership queries (AMQ), such as Bloom and Cuckoo filters. We develop a simulation-based framework for analysing correctness and privacy properties of AMQ-PDS in adversarial settings. Using this, we show how to provably protect AMQ-PDS at low cost, going all the way from a theoretical analysis to parameter selection for securing AMQ-PDS in practice.