Resistance to Timing Attacks for Sampling and Privacy Preserving Schemes

Yoav Ben Dov, Liron David, Moni Naor, Elad TzalikFORC 2023 · DOI

TL;DR

This paper introduces the concept of "time oblivious" sampling and differential privacy mechanisms, aiming to prevent timing attacks that exploit execution time to infer sensitive information. The authors provide a characterization of distributions that can be sampled time obliviously and show how to transform existing differential privacy mechanisms into time oblivious ones, albeit with some trade-offs.

What Problem Does This Paper Address?

Side-channel attacks, particularly timing attacks, pose a significant threat to the security of cryptographic protocols and algorithms. These attacks exploit the fact that the time it takes for a computation to complete can leak information about the inputs or outputs. This is especially problematic in the context of differential privacy (DP), where algorithms are designed to protect individual data privacy. If the execution time of a DP mechanism leaks information about the underlying data, the privacy guarantees can be compromised. The paper addresses the challenge of designing sampling algorithms and DP mechanisms that are resistant to such timing attacks, ensuring that their execution time does not reveal sensitive information.

Methods

The core of the paper revolves around the concept of "time oblivious" algorithms. An algorithm is time oblivious if its output distribution and its running time distribution are independent.

  • Time Oblivious Sampling: The authors characterize distributions that can be sampled in a time oblivious manner. They prove that a distribution can be sampled time obliviously if and only if it has a finite support and rational probabilities. They then present an optimal algorithm for generating such distributions.
  • Time Oblivious Differential Privacy: The paper defines time oblivious DP mechanisms and investigates their properties. They show that for pure DP mechanisms with unbounded output ranges, time obliviousness can lead to useless outputs with a certain probability or infinite expected running times. However, they also demonstrate that any pure DP mechanism with a discrete range can be transformed into a time oblivious pure DP mechanism with nearly the same privacy guarantees and utility, albeit with a slightly relaxed privacy parameter.
  • DNF Sampling: The paper also explores the problem of sampling satisfying assignments for Disjunctive Normal Form (DNF) formulas. They show how to convert existing algorithms into time oblivious ones, but also prove that achieving "input hiding" time obliviousness (where neither the output nor the input is revealed by the running time) is computationally expensive for DNF formulas.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Time Oblivious" Paradigm: The paper introduces a formal definition of time oblivious algorithms, which is crucial for understanding and building secure systems against timing attacks. This concept extends beyond just fixed-time execution to a statistical independence between output and runtime.
  • Characterization of Sampleable Distributions: The key insight is that only distributions with finite support and rational probabilities can be sampled in a truly time oblivious manner. This has direct implications for DP, as many common noise distributions (like Laplace) are not in this category.
  • Trade-offs in DP: The paper highlights the inherent trade-offs when making DP mechanisms time oblivious. While it's possible to achieve time obliviousness, it can come at the cost of reduced utility or increased computational overhead, especially for pure DP.
  • Input Hiding is Hard: The result on DNF sampling demonstrates that achieving time obliviousness while also hiding the input structure is a significantly harder problem, requiring exponential resources in some cases.

Key Results

  • Characterization Theorem: A distribution D can be sampled by a time oblivious algorithm if and only if it has finite support and rational probabilities.
  • Optimal Time Oblivious Sampler: An efficient algorithm (Algorithm 1) is presented for sampling from such distributions, proven to be optimal in terms of randomness used.
  • DP Transformation: Any $\epsilon$-pure DP mechanism with a discrete range can be transformed into a time oblivious $\epsilon'$-pure DP mechanism (with $\epsilon' > \epsilon$) that is pointwise close to the original.
  • DNF Sampling Complexity: Sampling a uniform satisfying assignment of a DNF formula in an input-hiding time oblivious way requires $\Omega(2^n)$ bits in expectation, where $n$ is the number of variables.

Limitations and Future Work

  • Pure DP Drawbacks: For pure DP mechanisms with unbounded output ranges, achieving time obliviousness can lead to useless outputs with a certain probability or infinite expected running times. The paper suggests that approximate DP might be a more practical alternative in such cases.
  • Computational Efficiency of DP Transformation: While the paper shows how to transform DP mechanisms into time oblivious ones, the efficiency of this transformation is not always guaranteed. The authors pose a question about whether this transformation can preserve computational efficiency.
  • Markov Chain Sampling: The paper raises the question of whether Markov Chain algorithms, which are common for sampling from distributions, can be efficiently converted into time oblivious algorithms.
  • Input Hiding for DP: The paper touches upon the difficulty of input hiding in DP and suggests it as an area for future research.

Summary updated

BibTeX
@inproceedings{dov2023resistance,
  author = {Yoav Ben Dov and Liron David and Moni Naor and Elad Tzalik},
  title = {{Resistance to Timing Attacks for Sampling and Privacy Preserving Schemes}},
  booktitle = {FORC},
  year = {2023},
  doi = {10.4230/lipics.forc.2023.11},
}
Figure