Achieving Obliviousness in Compressed Data Structures

Abstract

: Oblivious RAM (ORAM) is a general-purpose storage technique that hides memory access patterns, protecting data, queries, and results from untrusted honest-but-curious servers. While traditional ORAM supports only basic reads and writes, recent works have addressed the problem of enabling richer queries by designing oblivious versions of simple data structures (e.g., maps, sets, queues). In this paper, we take a distinct step by introducing two building blocks that make it easy to construct many advanced oblivious and compressed data structures efficiently and securely. Our approach builds on recent results showing that most (compressed) data structures can be implemented using two fundamental primitives: Rank and Select, which count and locate symbol occurrences within a sequence. We present the first oblivious implementations of Rank and Select that require only a single ORAM access per operation, use O(1) client-side space, and add negligible client computation overhead. Thanks to their simplicity and efficiency, our oblivious Rank and Select provide a foundation for building a wide range of other oblivious compressed data structures, enabling privacy-preserving (compressed) data storage, indexing, and search in the cloud.