Bloom Filter

Bloom filters achieve extreme memory efficiency by representing a set as a fixed-size bit array rather than storing the elements themselves. A Bloom filter for 1 million elements with a 1% false positive rate requires only about 1.14 MB of memory, compared to storing the raw elements which could consume orders of magnitude more space. This compact representation is critical in bandwidth-constrained PSI protocols where the filter is transmitted between parties.

• Uses k independent hash functions to map each element to k positions in the bit array
• Memory footprint depends only on target false positive rate and expected element count
• Size remains constant regardless of element length or complexity

A Bloom filter provides a one-sided error guarantee: if the filter reports an element is not in the set, that answer is always correct. This property is essential in PSI protocols where a false negative would mean missing a genuine intersection element. The filter achieves this by only setting bits to 1 during insertion and never clearing them.

• Query returns definitely not in set or possibly in set
• Absence of an element is provably certain
• This asymmetry makes Bloom filters ideal as a pre-filter before more expensive cryptographic checks

The false positive probability can be precisely tuned by adjusting three parameters: the bit array size (m), the number of hash functions (k), and the expected number of elements (n). The optimal number of hash functions is approximately k = (m/n) * ln(2). For a target false positive rate p, the required bits per element is m/n ≈ -1.44 * log₂(p).

• 1% false positive rate: ~9.6 bits per element
• 0.1% false positive rate: ~14.4 bits per element
• Trade-off: lower false positive rates require more memory and hash computations

In Private Set Intersection protocols, Bloom filters serve as an efficient pre-filtering mechanism. One party encodes their entire set into a Bloom filter and sends it to the other party, who can quickly eliminate elements that are definitely not in the intersection before performing expensive cryptographic operations on the remaining candidates.

• Dramatically reduces the number of oblivious transfer or garbled circuit evaluations needed
• Commonly used in KKRT-style PSI protocols with OT extension
• The false positive rate directly impacts the protocol's communication overhead, as false positives trigger unnecessary cryptographic work

A Garbled Bloom Filter (GBF) extends the standard Bloom filter for secure computation. Instead of storing bits, each position holds a secret share of the element. During PSI, the GBF enables one party to encode their set such that the other party can only recover elements they also possess, without learning anything about non-matching entries.

• Each array position stores a λ-bit string rather than a single bit
• Uses XOR-based secret sharing across the k hash positions
• Enables asymmetric PSI where only one party learns the intersection
• Provides information-theoretic security against the receiver

Bloom filters have inherent constraints that affect their use in privacy-preserving applications. They do not support deletion of elements (standard variant), and the false positive rate increases as more elements are inserted beyond the designed capacity. Additionally, transmitting a Bloom filter reveals its bit density, which can leak information about the set size.

• Counting Bloom filters extend the structure with counters to support deletions
• Compressed Bloom filters optimize for network transmission rather than memory
• In PSI, the filter's bit pattern may leak the cardinality of the sender's set if not properly padded