Theoretical Limits of Data Privacy

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

The project falls within the EPRSC ICT Networks and Distributed Systems research area. The focus of the project is the use of information theory to investigate the fundamental limits of data privacy in communications and storage scenario It will also be of interest to look more practically into ways we can come close to approaching those limits in real life systems. Information theory concerns the quantification of the amount of information held in an event or random variable, which in the context of communication could be a message to be conveyed to an intended recipient. It can tell us the amount of information (i.e., number of bits) needed to represent an event, and the rate at which this information can reliably be transmitted across a channel. In the context of data privacy, the goal of this research will be to construct mathematical theorems that specify the conditions under which data privacy can be maintained in various settings. This could for example answer the question: "How much information can a data miner theoretically collect, given access to a certain network?", where the network in question could be something as simple as a user's social media connections. Data breaches as a result of data mining are a very current and serious concern. At present, there are very few results pertaining to the maximum amount of information that could possibly be accessed in such an incident. The methodology employed to achieve such results will involve experimenting with information inequalities and random coding arguments. Proofs related to ergodic data sources are likely to make use of the asymptotic equipartition property (AEP), but new methods may need to be developed for more realistic non-ergodic sources. The second main aim of the project will be to consider the practical meaning of the results, and assess if and how one could come close to achieving the theoretical limits in a real system. In information theory, there exist fundamental bounds that have been known for many years, that we still do not come close to achieving in practice. Thus, this second aim is quite distinct from the first. For example, many transmission bounds are derived with the idea of infinite block lengths (i.e., codewords of infinite length), allowing for the use of the AEP. Clearly, codewords in real life are not infinitely long, so the actual rate achieved by practical coding schemes does not follow directly from the theoretical achievable bound. Returning to the example of data privacy: the information that a data miner can collect following their current best practical methodology may be much less (or more) than what is theoretically possible. In terms of application, it would be useful to know both how much information could be available in a worst-case scenario, as well as how much is realistically accessed, and how this could be done.