Cryptography, Security, and Privacy (CrySP)

This speaker series is made possible by an anonymous charitable donation in memory of cypherpunks and privacy advocates Len Sassaman, Hugh Daniel, Hal Finney, and Caspar Bowden.

View the list of past and upcoming speakers

Matching Theory and Anonymity

Eva Infeld, Darthmouth College

[Download (MP4)] [View on Youtube]

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.