Matching Theory and Anonymity
Eva Infeld, Darthmouth College
March 11, 2016 2:00pm, in MC 5501
One of the fundamental paradigms in privacy technologies is k-anonymity—the idea that we should divide users of a system into sets and make them indistinguishable from each other within each set. But is k-anonymity really the optimal solution or simply what we know how to do? I will model an anonymity system as a bipartite graph and use the number of edges to represent infrastructure cost. Then I will use matching theory to show that k-anonymity does in fact maximize the number of ways in which behaviors can possibly be matched to users, for a given number of edges.
Eva is a graduate student in the Mathematics department at Dartmouth. Her main line of research is in avoidance coupling of Markov chains, that is: when can we put several Markov processes on the same graph in such a way that they never collide, but if we only see one of them, it's indistinguishable from a simple walk. She have been interested in privacy for years, and has been using her toolkit in probabilistic combinatorics to answer theoretical questions about it.