International Association
for Cryptologic Research

Recent works~\cite{ben2023resistance,ratliff2024framework} have started to theoretically investigate how we can protect differentially private programs against timing attacks, by making the joint distribution the output and the runtime differentially private (JOT-DP). However, the existing approaches to JOT-DP have some limitations, particularly in the setting of unbounded DP (which protects the size of the dataset and applies to arbitrarily large datasets). First, the known conversion of pure DP programs to pure JOT-DP programs in the unbounded setting~\cite{ben2023resistance} (a) incurs a constant additive increase in error probability (and thus does not provide vanishing error as $n\to\infty$) (b) produces JOT-DP programs that fail to preserve the computational efficiency of the original pure DP program and (c) is analyzed in a toy computational model in which the runtime is defined to be the number of coin flips. For approximate JOT-DP, an efficient conversion with vanishing error in the RAM model is known~\cite{haeberlen2011differential,ratliff2024framework}, but only applies to programs that run in $O(n)$ time on datasets of size $n$, as linear runtime is implied by ``timing stability,'' the timing analogue of global sensitivity. In this work, we overcome these limitations. Specifically: \begin{enumerate} \item We show that the error required for pure JOT-DP in the unbounded setting depends on the model of computation. \begin{itemize} \item In a randomized RAM model where the dataset size $n$ is given (or can be computed in constant time) and we can generate random numbers (not just random bits) in constant time, polynomially small error probability is necessary and sufficient. \item If $n$ is not given or we only have a random-bit generator, an (arbitrarily small) constant error probability is necessary and sufficient. \end{itemize} \item The aforementioned positive results are proven by efficient procedures to convert any pure JOT-DP program $P$ in the upper-bounded setting to a pure JOT-DP program $P'$ in the unbounded setting, such that the output distribution of $P'$ is $\gamma$-close in total variation distance to that of $P$, where $\gamma$ is either an arbitrarily small constant or polynomially small, depending on the model of computation. \end{enumerate}