Differential Privacy Under a Constrained Dynamic Database Model

The collection, storage, and use of sensitive data often requires a trade-off between individual privacy and public utility. Differential privacy (DP) formalises this trade-off, for releasing information about sensitive data, by providing provable privacy guarantees for individual dataset participants. There is a wealth of literature proposing DP algorithms, with good utility, for static datasets; however, privacy and accuracy losses accrue over multiple releases. In dynamic settings, where the dataset is growing or changing over time, the same queries are likely repeated as the dataset changes, requiring large numbers of private releases. Dynamic DP is an active area of research, with most work considering data streams, where each entry is fixed once it is added, or trajectory data, with a separate stream of updates for each individual; databases where records are updated over time, with only the latest update available for analysis, are common in practice but less thoroughly researched in the DP literature. In this thesis, we consider a setting where the set of individuals in the database is fixed, and one individual's state is updated per unit of time. Prior to introducing our model, we present a taxonomy of the models used in key dynamic DP papers. We classify these models primarily according to their update types, and further distinguish them according to their privacy definitions. This allows us to bring together previously fragmented research into a cohesive framework. We then introduce our fixed-size dynamic database (FSDD) model. We provide a base mechanism, tau-RQ, for repeating the same query after each update to the FSDD. Using properties of the FSDD model, we can utilise existing results from static DP to determine the optimal query frequency in the worst case, balancing the effects of random noise, added to preserve privacy, with the accrued changes to the underlying database. We extend tau-RQ to provide a mechanism to convert any static DP mechanism t