Abstract
Secure cloud storage often relies on Bloom filters for efficient keyword searching, but updating these filters without leaking information to the server remains a significant challenge. This paper presents OBFI (Oblivious Bloom Filter Insertion), a novel framework that allows clients with limited local storage to perform batch updates obliviously. By leveraging a new "Oblivious Bucket Distribution" technique, OBFI reduces the computational overhead to scale with the batch size rather than the total filter capacity, providing a more scalable solution for dynamic encrypted databases.
Introduction
In outsourced encrypted databases, Bloom filters are essential for fast membership testing (e.g., verifying if a document contains a specific keyword). However, these filters face a major efficiency bottleneck during updates. To maintain privacy, updates must be "oblivious," meaning the server should not learn which specific bits of the filter are being modified. Traditional methods to achieve this require either re-scanning the entire filter—which is prohibitively slow—or require the client to maintain significant local memory.
This paper addresses the needs of storage-limited clients, such as IoT devices, by introducing a method for efficient batch updates where the cost scales with the number of new elements ($m$) rather than the total capacity of the filter ($n$).
The OBFI Framework
The core innovation of this work is the Oblivious Bucket Distribution (OBD) protocol. The process follows a structured workflow to ensure data access patterns remain hidden from the untrusted server:
- Partitioning: The outsourced Bloom filter is logically divided into equal-sized segments.
- Hashing & Sorting: The client computes hash positions for a batch of $m$ elements. These positions are shuffled using an Oblivious Sort (OSORT) to hide the underlying values.
- Bucket Distribution: Using a newly proven mathematical property (Lemma 1), the authors determine a fixed threshold for bucket capacity. Hash positions are distributed into these fixed-size buckets. Because the bucket size is independent of the actual data distribution, the server learns nothing about which segments are being updated.
Protocol Variants
The authors propose two variants of OBFI to accommodate different client constraints:
- Variant 1: Requires $O(\lambda)$ local storage (where $\lambda$ is a security parameter) and processes buckets locally to update filter segments.
- Variant 2: Reduces client storage to a constant $O(1)$ by outsourcing the buckets as "mini-Bloom filters," though this introduces a marginal increase in the false-positive rate.
Comparative Analysis
OBFI significantly improves upon previous state-of-the-art methods by decoupling the update cost from the total database size. As shown in the table below, OBFI achieves an update cost of $O(m \log m)$, whereas previous methods like WS12 scaled with $O(n \log n)$.
Key Results and Security
- Efficiency: For scenarios where the batch size $m$ is much smaller than the total filter size $n$, OBFI provides a massive performance leap.
- Storage Optimization: Client-side memory requirements are reduced from $O(\lambda\sqrt{m})$ in earlier works to $O(\lambda)$ or $O(1)$.
- Adaptive Security: The protocols are proven to be adaptively data-oblivious in the Random Oracle Model, ensuring security even if an adversary chooses update batches based on previously observed traffic.
Conclusion
OBFI represents a significant step forward for secure, outsourced data structures. By shifting the complexity of updates to the batch size, it enables resource-constrained devices to interact with large-scale encrypted databases efficiently. Future work may focus on optimizing the linear scan required for re-encryption and exploring more storage-efficient methods for oblivious deletions using Counting Bloom Filters.
Summary updated