Papers for

cloud security architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Sublogarithmic cost achieves optimal privacy for priority queues

Differentially Oblivious Priority Queues with Sublogarithmic Cost

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.

Tue 3 NovData Structures and AlgorithmsComputational Complexity

The gist

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.

Open → 2611.04776v1