Timing Side Channels in Privacy Preserving Computations

27 concepts10 papers1 proposal

When we reason about privacy-preserving algorithms, we often treat them as mathematical abstractions. In the idealized world of differential privacy (DP) or secure multi-party computation (MPC), an algorithm takes an input, performs a black-box computation, and returns an obfuscated or encrypted output. If the mathematical proof shows that the output leaks no sensitive information, we consider the system secure.

However, physical computers do not execute abstract mathematics; they execute instructions that take time. As highlighted by Markus de Medeiros et al. in Verified Foundations for Differential Privacy, statistical privacy models frequently ignore physical execution vulnerabilities. If the execution time of a program varies based on the underlying sensitive data, a stopwatch becomes a powerful side-channel attack vector. Even a provably private output can be completely undermined if an observer can infer confidential data simply by measuring how long the computation took to complete.

The Mechanics of Variable-Time Sampling

Why does the runtime of a privacy mechanism depend on sensitive data in the first place? The vulnerability usually stems from the algorithms used to generate randomness or sample from complex probability distributions.

The Discrete Noise Loophole

To protect privacy, mechanisms often add random noise to a query result. Historically, implementations used floating-point numbers to draw this noise, but floating-point vulnerabilities allowed attackers to reverse-engineer private inputs. To fix this, modern systems transitioned to discrete mechanisms (such as the geometric or discrete Gaussian mechanisms).

However, as demonstrated by Jiankai Jin et al. in Are We There Yet? Timing and Floating-Point Attacks on Differential Privacy Systems, these discrete mechanisms often rely on iterative sampling loops. In a naive implementation, the loop runs until a specific condition is met, meaning the number of iterations—and thus the execution time—is directly proportional to the magnitude of the noise generated. Because the noise distribution is centered around the true, sensitive query result, an adversary measuring the execution time can accurately deduce the noise magnitude and reconstruct the private data.

Rejection Sampling and Perfect Simulation

A similar issue arises in rejection sampling, a foundational technique used to sample from complex distributions like the Exponential Mechanism. In standard rejection sampling, the algorithm repeatedly generates candidate samples until one passes an acceptance test.

As analyzed by Jordan Awan et al. in Privacy-Aware Rejection Sampling, the probability of accepting a candidate depends directly on the underlying dataset. Consequently, the number of iterations required to produce a valid sample varies based on the data. Even when researchers use advanced Markov Chain Monte Carlo (MCMC) methods or "artificial atoms" to achieve exact, finite-time privacy guarantees, the variable execution time of these sampling routines can still inadvertently leak the very data they are trying to protect (Jeremy Seeman et al. in Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms).

The Efficiency-Privacy Tension

The core challenge of eliminating timing side channels is that variable runtime is often a deliberate feature designed to maximize performance. This creates a fundamental tension between computational efficiency and data privacy.

Turing Machines vs. Boolean Circuits

In cryptographic architectures like Fully Homomorphic Encryption (FHE) or Functional Encryption, programs are traditionally evaluated as Boolean circuits. Circuits have a fixed structure: every gate is evaluated regardless of the input, meaning the execution time is always forced to the theoretical worst-case scenario. This is perfectly secure against timing attacks, but highly inefficient.

To overcome this "worst-case curse," Shafi Goldwasser et al. in Overcoming the Worst-Case Curse for Cryptographic Constructions proposed evaluating encrypted programs using the Turing Machine (TM) model. This allows for "input-specific" efficiency, where a program can halt early if the computation on a specific input is simple. However, the authors prove that this performance gain comes at a direct cost: the execution duration itself leaks information about the input data, creating an inherent trade-off between optimization and perfect obfuscation.

Algorithmic Complexity and Problem Structure

This trade-off is magnified in complex algorithmic tasks:

  • Graph Algorithms: When executing sublinear-time graph algorithms privately, converting expected runtime guarantees into high-probability bounds introduces severe risks of information leakage across multiple runs (Jeremiah Blocki et al. in Privately Estimating Graph Parameters in Sublinear time).
  • Private SAT Solving: In two-party private Boolean satisfiability (SAT) solving, the total time required to solve a hard problem reveals deep structural properties of the underlying formulas (Ning Luo 0002 et al. in ppSAT: Towards Two-Party Private SAT Solving).
  • RAM-based MPC: Even when internal machine states and memory access patterns are hidden using Oblivious RAM (ORAM), the total number of execution cycles remains exposed, leaking properties of the private function or its inputs (Keyu Ji et al. in Multi-party Private Function Evaluation for RAM).

Designing Time-Oblivious Mechanisms

To close these timing side channels, researchers are developing algorithms that decouple execution time from the underlying data, aiming for "time-oblivious" execution.

Naive Sampling (Data-Dependent Runtime):
Input A ───► [ Iterative Loop ] ───► Halts quickly (Fast)
Input B ───► [ Iterative Loop ] ───► Runs longer   (Slow)  ◄── Adversary measures delta

Time-Oblivious Sampling (Data-Independent Runtime):
Input A ───► [ Truncated / Padded Loop ] ───► Halts at fixed T ┐
Input B ───► [ Truncated / Padded Loop ] ───► Halts at fixed T ┴──► Constant runtime

1. Exploiting Memoryless Distributions

One elegant mathematical fix is to leverage the memoryless property of specific probability distributions. For instance, the geometric and exponential distributions are memoryless, meaning the probability of an event occurring in the next time step is independent of how much time has already elapsed. Jeremy Seeman et al. demonstrate that by structuring sampling algorithms around these properties, the total computation time can be mathematically decoupled from the sensitive input data.

2. Truncation and Additive Wait-Times

For rejection sampling, Jordan Awan et al. propose two primary modifications to achieve data-independent runtimes:

  • Truncated Sampling: Forcing the sampler to halt after a fixed, predetermined number of iterations, regardless of whether it has accepted a sample, and handling the resulting error deterministically.
  • Additive Geometric Wait-Times: Artificially padding the execution time by adding dummy iterations. If the true sampling loop finishes early, the system simulates additional work so that the total execution time matches a predictable, data-independent distribution.

3. Systematic and Verified Frameworks

Rather than patching algorithms ad-hoc, recent work focuses on building frameworks that guarantee timing resistance by design. Yoav Ben Dov et al. in Resistance to Timing Attacks for Sampling and Privacy Preserving Schemes provide a formal characterization of which probability distributions can be sampled in a time-oblivious manner, offering a blueprint for transforming vulnerable DP mechanisms into timing-resistant variants.

Simultaneously, programming languages and verification tools are evolving to catch these leaks before deployment. Frameworks like Fuzzi (Hengchu Zhang et al. in Fuzzi: A Three-Level Logic for Differential Privacy) use advanced logical systems to help developers automatically verify that their composite pipelines remain private, ensuring that the physical realities of execution time align with theoretical privacy budgets.

Key Foundational Work

Overcoming the Worst-Case Curse for Cryptographic Constructions (2013) — contributed 2 concept elements to this direction.
Fuzzi: A Three-Level Logic for Differential Privacy (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_runtime_side_channel_leakage_87e33c97,
  title = {runtime side-channel leakage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/runtime-side-channel-leakage/rdr_87e33c97e910464381732c428cc3fcb4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_runtime_side_channel_leakage_87e33c97_v1,
  title = {runtime side-channel leakage},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/runtime-side-channel-leakage/rdr_87e33c97e910464381732c428cc3fcb4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake