Crypto Seminar Talk with Tamalika Mukherjee
Info about event
Time
Location
Lille AUD (building 5510, room 103), INCUBA, Åbogade 15, 8200 Aarhus N
Title: Private Graph Property Testing
Abstract: Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property testers typically inspect only a small, randomly sampled portion of the input, they appear naturally compatible with differential privacy and privacy amplification by subsampling. Despite this, few results link these two fields. We initiate a systematic study of differentially private graph property testing with the goal of designing efficient testers with formal privacy guarantees in the dense and bounded-degree graph models. We develop new privacy amplification theorems for several widely used graph-sampling procedures such as induced subgraph sampling, random walks and k-disc sampling. We then leverage these privacy amplification techniques to design a private canonical tester in the dense graph model, as well as private bipartiteness testers and subgraph freeness testers in the dense and bounded-degree graph models. Finally, using the new privacy amplification theorem for k-disc sampling, we prove that every property of hyperfinite graphs is privately testable. The resulting query complexities of our private testers are comparable to those of their non-private counterparts.
About the Speaker: Tamalika Mukherjee is a Research Group Leader at the Max Planck Institute for Security & Privacy in Bochum, Germany. This week and next week she is visiting Department of Computer Science, Aarhus University.
This seminar talk is joint with the Algorithms, Data Structures & Artificial Intelligence Section.