Abstract
Differential Obliviousness (DO) is a relaxation of full obliviousness that offers significant performance gains by requiring that memory access patterns satisfy differential privacy. However, DO has historically lacked a robust theory of composition, making it difficult to build complex private systems from simpler components. This paper introduces Neighbor-Preserving Differential Obliviousness (NPDO), a new privacy notion that ensures the joint distribution of an algorithm's access patterns and its output remains close for neighboring inputs. This framework enables the first formal composition theorems for DO, provides optimal privacy amplification in the shuffle model, and facilitates the design of more efficient algorithms for fundamental tasks like stable compaction.
Introduction
In secure computation, oblivious algorithms are essential for hiding memory access patterns, which can otherwise leak sensitive information to an adversary monitoring the execution environment. While "full obliviousness" (where access patterns are identical regardless of the input) is the gold standard, it often incurs a high performance overhead. Differential Obliviousness (DO) was proposed as a more efficient alternative, requiring only that the access patterns of two neighboring inputs be statistically similar, rather than identical.
Despite its promise, DO faces a critical challenge: it does not compose naturally. In standard differential privacy, the privacy loss of sequential operations is additive. In DO, however, if the output of one DO algorithm is used as the input for another, the second algorithm may no longer be processing "neighboring" inputs in a way that preserves privacy. This "composition gap" has prevented DO from being used as a modular building block for complex applications like private SQL databases.
The NPDO Framework
To address the composition problem, the authors propose $(\epsilon, \delta)$-Neighbor-Preserving Differential Obliviousness (NPDO).
Defining NPDO
Unlike standard DO, which only considers the privacy of the view (the access patterns), NPDO requires that the joint distribution of the view and the algorithm's output remains $(\epsilon, \delta)$-indistinguishable for any two neighboring inputs. By ensuring that the output itself "preserves" the neighboring property, NPDO guarantees that the next algorithm in a sequence receives inputs that satisfy the necessary privacy conditions.
The $(\epsilon, \delta)$-Matching Lemma
A central technical contribution of this work is the $(\epsilon, \delta)$-Matching Lemma. Inspired by Hall’s Marriage Theorem, this lemma provides a necessary and sufficient condition for NPDO. It shows that an algorithm is NPDO if and only if there exists a specific type of "matching" between the probability spaces of its executions on neighboring inputs. This tool is instrumental in proving the framework's composition properties.
Key Results and Applications
Composition Theorems
The authors establish two primary composition rules:
- Sequential Composition: If an algorithm $M_1$ is NPDO and $M_2$ is DO, their composition $M_2 \circ M_1$ is DO.
- Strong Composition: If both $M_1$ and $M_2$ are NPDO, their composition is also NPDO, allowing for the creation of arbitrarily deep pipelines of private operations.
Privacy Amplification in the Shuffle Model
The paper demonstrates that the popular "shuffle model" for differential privacy can be analyzed through the lens of DO composition. The authors prove that a perfectly secure shuffler is not required for privacy amplification; a significantly more efficient differentially oblivious shuffler is sufficient to achieve optimal privacy amplification results, matching the best-known bounds for the slower, perfectly secure models.
Efficient Stable Compaction
Using the NPDO framework, the authors developed a new stable compaction algorithm that is DO with respect to edit distance. This algorithm achieves an overhead of $O(n \log \log n)$, a substantial improvement over the $\Theta(n \log n)$ overhead typically required by traditional oblivious sorting methods. This is made possible by DO's ability to utilize "noisy" running times or output lengths, avoiding the need to pad every operation to the absolute worst-case scenario.
Discussion and Limitations
While this work provides a rigorous foundation for DO composition, several areas remain for future exploration. The current proofs primarily address finite or countably infinite view and output spaces, which are standard for RAM models but may require further generalization for algorithms involving real-number arithmetic or uncountable spaces. Additionally, as a theoretical work, the practical "hidden constants" in the $O(n \log \log n)$ algorithms need to be empirically tested to determine the exact crossover points where these methods outperform traditional oblivious primitives in real-world systems.
Finally, while the paper extends these notions to computational DO (security against polynomial-time adversaries), the interaction between NPDO and specific cryptographic primitives remains a promising avenue for future research.
Summary updated