Recent works [9, 25] 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 [9] (a) incurs a constant additive increase in error probability (and thus does not provide vanishing error as \(n\rightarrow \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 [17, 25], 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: