International Association
for Cryptologic Research

In this work, we initiate the formal study of oblivious batch updates over outsourced encrypted Bloom filters, focusing on scenarios where a storage-limited sender must insert or delete batches of elements in a Bloom filter maintained on an untrusted server. Our survey identifies only two prior approaches (CCS 2008 and CCS 2012) that can be adapted to this problem. However, they either fail to provide adequate security in dynamic scenarios or incur prohibitive update costs that scale with the filter’s maximum capacity rather than the actual batch size.

To address these limitations, we introduce a new cryptographic primitive, $\textit{Oblivious Bloom Filter Insertion}$ ($\textsf{OBFI}$), and propose novel constructions. At the core of our design is a novel building block, $\textit{Oblivious Bucket Distribution}$ ($\textsf{OBD}$), which enables a storage-limited sender to distribute a large array of elements, uniformly sampled from a finite domain, into small, fixed-size buckets in a data-oblivious manner determined by element order. The design of $\textsf{OBD}$ is further supported by identifying and proving a new structural property of such arrays, which establishes tight and explicit probabilistic bounds on the number of elements falling within predefined subranges of the domain.

Our $\textsf{OBFI}$ constructions achieve adaptive data-obliviousness and ensure that batch update costs scale primarily with the batch size. Depending on the variant, the sender’s storage requirement ranges from $O(\lambda)$, where $\lambda$ is the security parameter, down to $O(1)$. Finally, we demonstrate the practicality of $\textsf{OBFI}$ by integrating it into representative Bloom-filter-based cryptographic protocols for Searchable Symmetric Encryption, Public-key Encryption with Keyword Search, and Outsourced Private Set Intersection, thereby obtaining batch-updatable counterparts with state-of-the-art security and performance.