Tom Shrimpton, University of Florida
From 16:00 until 17:00
At Zoom: https://ethz.zoom.us/j/98363015201
https://ethz.zoom.us/j/98363015201
Abstract:
Probabilistic data structures use space-efficient representations of data in order to (approximately) respond to queries about the data. Traditionally, these structures are accompanied by probabilistic bounds on query-response errors. These bounds implicitly assume benign attack models, in which the data and the queries are chosen non-adaptively, and independent of the randomness used to construct the representation. Yet probabilistic data structures are increasingly used in settings where these assumptions may be violated.
This talk will explore a provable-security treatment of data structures, in the presence of adversaries whose goal is to cause query-response errors. We will formalize notions of security that capture settings in which the data structure is publicly viewable (i.e., visible to the adversary), and when it is private. We'll analyze the ubiquitous Bloom filter, the counting filter, and count-min sketch with respect to these notions. In cases where the data structure is insecure, we will examine the benefits of proposed defenses, e.g., salting and secretly keying.
Join the Zoom meeting at 16:00 on Thursday, February 25th: https://ethz.zoom.us/j/98363015201