Sublogarithmic cost achieves optimal privacy for priority queues
Differentially Oblivious Priority Queues with Sublogarithmic Cost
Data Structures and AlgorithmsComputational Complexity
Summary
Keeping the order of tasks private while managing many of them efficiently is a tricky problem. The authors study a special kind of data structure called a priority queue, which helps manage tasks by importance while hiding access patterns to protect privacy. They create a method that does these operations faster than before while keeping the process differentially oblivious, meaning it carefully limits what can be learned from its usage. They also prove that their method is as efficient as possible for this level of privacy.
What this means in practice
- •For secure database engineers: Design priority queue operations that hide data access patterns with the least possible performance overhead to protect user privacy in encrypted databases.
- •For cloud security architects: Implement efficient, privacy-preserving task scheduling that prevents leakage of sensitive information from operation sequences in remote cloud services.
A theory result. No direct application yet.
Authors
Zimai Guo, Cheng Hong, Zhechen Li
Abstract
In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.