Welcome to the resource topic for 2025/2116
Title:
Oblivious Batch Updates for Bloom-Filter-based Outsourced Cryptographic Protocols
Authors: Marten van Dijk, Dandan Yuan
Abstract: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.
ePrint: https://eprint.iacr.org/2025/2116
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .