Foundations of Differential Privacy Against Timing Attacks

Abstract

The framework of differential privacy (DP), introduced by Dwork, McSherry, Nissim, and Smith in 2006, provides rigorous mathematical guarantees on what an algorithm's output can reveal about its input. However, real systems often expose information through observable channels beyond the algorithm's output. In particular, the algorithm's runtime may also be observable, creating a \emph{timing side channel} through which information about the input can leak. This thesis studies differential privacy in the presence of timing side channels. We begin by developing a theoretical framework for reasoning about \emph{timing-private} DP programs, whose privacy must hold under the joint observation of their output and execution time. We then show that if a DP program has bounded timing stability, meaning that small changes to the input induce only limited changes in runtime, one can add carefully calibrated randomized delay to achieve $(\varepsilon, \delta)$-\emph{joint output/timing privacy} (JOT-DP). This framework supports modular reasoning about the runtime behavior of programs and yields efficient constructions of timing-private DP programs for common data analysis tasks. Building on this framework, the thesis makes three further contributions. \begin{enumerate} \item We show that timing side channels are a practical threat to real implementations of differential privacy. In particular, we identify timing vulnerabilities in popular DP libraries across a range of common DP data analysis tasks, and we develop an auditing methodology for quantifying the resulting privacy loss when both outputs and runtimes are observable. \item We study \emph{pure} timing privacy ($\delta = 0$) in the unbounded setting, where dataset size itself is sensitive and can be arbitrarily large. We give efficient constructions of pure JOT-DP programs in this setting, show that the achievable error depends on the model of computation, and prove matching lower bounds for the computational models we study, showing that these constructions are optimal. \item We extend the study of timing privacy to the user-level setting, where privacy is defined with respect to adding or removing all records contributed by a single user. We show that bounded per-user contributions allow ordinary user-level DP algorithms to be transformed into JOT-DP programs with only small statistical error in their output distributions. In contrast, when user contributions are unbounded, even approximate ($\delta > 0$) timing-private guarantees are incompatible with nontrivial utility. We then recover positive results under natural structural assumptions on the input. \end{enumerate}