Secure Sharing of Private Locations: Bridging Homomorphic Encryption and Bloom Filters

TL;DR

Researchers from the University of Tennessee have developed a system that allows users to find common locations (intersections) in their trajectories without ever revealing their actual coordinates to each other or the cloud server. By combining Fully Homomorphic Encryption (FHE) with Bloom Filters, they created a "blind" computation framework where the server processes encrypted data it cannot understand, returning results only the data owner can decrypt.

Background & Positioning

In the era of autonomous vehicles and geo-social apps like Pokémon Go, location privacy is a critical vulnerability. Most current solutions either trust the service provider (Google, Facebook) or degrade data quality to hide the user. This paper targets the SOTA (State-of-the-Art) transition from Partially Homomorphic Encryption (which is too restrictive) to a practical implementation of Fully Homomorphic Encryption for specific Geometric/Set-theory tasks.

The Problem: The "Untrusted Server" Paradox

Modern apps need to calculate things like "Is Alice near a coffee shop Bob recommended?" To do this, servers usually need Alice and Bob's raw coordinates. If the server is hacked, every user's movement history is leaked.

• Prior Work Limits: Methods like k-anonymity "blur" locations, making them useless for precise navigation.
• The Goal: Perform "Blind Matching"—determining if two sets intersect without seeing the elements of the sets.

Methodology: The Homomorphic Bloom Filter

The core innovation lies in the transformation of location points into a Bloom Filter (BF)—a space-efficient probabilistic data structure. Instead of encrypting coordinates $(x,y)$, the system encrypts the bits of the Bloom Filter.

The Framework Architecture

The interaction follows a three-party model:

1. Alice: Hashes her locations into a Bloom Filter $B{F}_A$, encrypts it with her public key, and uploads it.
2. Bob: Hashes his query into $B{F}_B$, encrypts it, and sends it to the server.
3. Server: Performs homomorphic operations (AND/XOR/Addition) on the ciphertexts.
4. Alice: Decrypts the result to see if an intersection exists.

Three Practical Optimizations

The authors realized that pure "Ideal FHE" (using complex polynomials) is too slow for real-time mobile apps. They proposed:

• O1 (Lightweight): Uses simple homomorphic addition. It's fast but leaks the number of "1" bits Bob is querying to the server.
• O2 (Improved Security): Adds intentional randomness ($z$) to the results so Alice can't reverse-engineer Bob's query using the decryption result.
• O3 (Bit-wise/Cross-layer): Treats the FHE scheme as a boolean circuit (AND/XOR gates), mimicking the native structure of Bloom Filters. This is the most "elegant" but computationally heaviest approach.

Experiments & Results

The team tested their prototypes using cellular data access records (7,607 users) on the SEAL (Simple Encrypted Arithmetic Library).

Computation vs. Communication

• Computation: Encryption time dominates, especially for Alice. O3 can take up to 24 seconds for complex trajectories, whereas O1 and O2 are significantly faster.
• Communication: O3 is the clear winner here, requiring only a few dozen Kilobytes because it treats the filters as compact integer arrays rather than individual encrypted bits.

Accuracy Trade-offs

Because Bloom Filters are probabilistic, there is a small "False Positive" chance (e.g., the system says there is an intersection when there isn't). The authors show that by adjusting the filter size ($m$) and number of hash functions ($k$), they can balance speed and accuracy perfectly for mobile use cases.

Critical Insight & Future Outlook

This paper proves that we don't need to choose between Privacy and Functionality. By "downcycling" complex location data into simple binary representations (Bloom Filters) before applying heavy-duty encryption (FHE), we achieve a middleware that is secure against even a fully compromised cloud server.

Limitations: While communication is optimized (KB scale), the encryption/decryption latency (seconds) still suggests this is better suited for background location "matching" (finding friends, finding ride-shares) rather than millisecond-level autonomous driving decisions.

Future Work: Integrating "Bootsrapping" techniques to allow for an infinite number of operations and exploring hardware-accelerated FHE could bring these "seconds" down to "milliseconds."