Oblivious Complex Queries on Variable-Length Strings
TL;DR
A practical design that combines Ring ORAM to hide access patterns to outsourced data, with a Patricia trie for space-efficient search over variable-length strings to support search over variable-length string datasets in an ORAM scenario, while retaining efficient storage and access both on the client and the server is proposed.
Abstract
: In this paper, we study the problem of storing and searching in datasets of variable-length strings, a core primitive in key-value stores, (graph) DBs, and search engines. However, enabling such search capabilities in ORAM scenarios, where data are stored on an honest-but-curious server, remains challenging. We address this problem by proposing a practical design that combines Ring ORAM (Ren et al., 2015) to hide access patterns to outsourced data, with a Patricia trie (Ferragina and Grossi, 1999; Ferragina et al., 2025) for space-efficient search over variable-length strings. The resulting scheme supports search over variable-length string datasets in an ORAM scenario, while retaining efficient storage and access both on the client and the server. We evaluated our scheme on datasets having size up to 273 GB, showing that it supports complex string queries, with only 2 Ring ORAM accesses on the server, incurring a client-server communication cost below 3 MiB, a client memory footprint of at most 200 MB, and negligible client computation time per query. Although we assume bounded-length strings, the bound is high enough to handle most practical use cases.