User-Level Local Differential Privacy

点击翻译按钮获取中文摘要

Due to growing user demands and legal requirements to protect the privacy of individuals' data, there is an increasing body of research in methods of privatising and anonymising data. Ad-hoc methods of removing personal identifying information such as names or email addresses have been shown to be inadequate due to ability to link data across a range of sources. In particular, in high dimensional datasets, it is often the case that each individual holds a unique combination of characteristics, making identification possible even with personal identifiers removed. Because of this, rigorous mathematical formulations of privacy are desirable. Differential Privacy is one such formulation, often seen as the gold standard, where a trusted data aggregator perturbs the output statistic with random noise such that a malicious adversary cannot deduce with a high degree of confidence the original value of any individual in the dataset. Local Differential Privacy (LDP) is an even more stringent condition where there is no trusted data aggregator, and so each individual instead perturbs their data before sending it to a (possibly malicious) data aggregator so that the original value cannot be deduced with a high degree of confidence. If each individual holds multiple pieces of data, then the problem of privatising their data becomes harder, as not only does one need to privatise each piece of data, but also the possible interactions of those data. On the other hand, if each individual holds multiple pieces of data, it should be possible in theory to construct better estimators than if each user only had a single piece of data, due to the simple fact that there is more available data. This setup, where each individual holds multiple pieces of data and we seek to privatise the entire collection, is referred to as User-Level LDP. The aim of our research thus far is to construct estimators of statistical quantities under a range of estimation problems under User-Level LDP, and to prove that these estimators are minimax rate optimal. Whilst there are already a few instances of estimators for some problems under User-Level LDP, there is currently a lack of understanding of whether some of these are minimax optimal or not. As existing tools to prove the minimax optimality of standard LDP problems are not directly suited for User-Level LDP, either new methods will need to be developed or existing ones applied in careful and creative manners.