Trustless Broker: Striking the Balance Between Privacy and Performance in Proximity Social Networks

TL;DR

Proximity-Based Mobile Social Networks (PMSN) allow users to find friends based on physical closeness and shared interests. However, sharing profiles often leads to "honest-but-curious" eavesdropping or identity theft. This paper proposes a protocol that uses a Trustless Broker and Paillier Additive Homomorphic Encryption to find the "best match" without a central server ever seeing the raw data, and without draining a smartphone's battery.

The Core Conflict: Privacy vs. Resource Constraints

Current matchmaking solutions face a "trilemma" of privacy, trust, and performance:

1. Centralized (TTP): Fast, but requires you to hand over your personal "Interest Vector" to a server.
2. Distributed (P2P): No server, but forces the mobile device to handle heavy cryptographic computations and risks exposing data to malicious neighbors.
3. Deterministic Encryption: Protocols like Commutative Encryption are efficient but weak; an attacker can pre-compute common interest hashes to "guess" your profile.

The authors' insight is to create a blind intermediary. The broker acts as a calculator that can add numbers without knowing what the numbers represent.

Methodology: The "Blind Calculator" Approach

The protocol transforms user interests into a binary vector (1 for interested, 0 for not). The magic happens through the Paillier Cryptosystem, an additive homomorphic scheme.

The Workflow:

1. Encryption: Users encrypt their interest vectors using Paillier. Because it is non-deterministic, encrypting "1" twice results in two completely different ciphertexts, preventing brute-force dictionary attacks.
2. Blind Computation: The broker receives these ciphertexts and uses the homomorphic property: $E(m_1)\cdot E(m_2)(\mathrm{mod}{n}^2)=E(m_1+m_2(\mathrm{mod}n))$ The broker sums the encrypted attributes of the initiator and potential friends.
3. Validation: The broker shuffles the results (to prevent pattern recognition) and sends them back. Users decrypt locally to find their match scores.

Figure 1: The system architecture showing the Initiator, Broker, and proximity-based users.

Experimental Results

The authors validated the concept using a real-world Android application (ADT) and an Intel i7 broker.

• Low Latency: Even as the number of interests increases up to 30, the computation time on the broker stays below 0.06 milliseconds.
• Storage Efficiency: By using serialized (.ser) files and compression, the entire encrypted profile is reduced to 1.5 KB, making it viable for slow 3G or constrained Wi-Fi connections.

Figure 2: Execution time on the broker showing near-linear scaling with the number of attributes.

Critical Insight & Conclusion

The true value of this work lies in the Inductive Bias that a broker does not need to be trusted if the math is robust. By using non-deterministic encryption, the broker can hold MAC addresses and Region-IDs for security (blocking malicious actors) without ever having the "key" to the users' social lives.

Limitations: While the protocol handles semi-honest users well, a fully malicious broker could still potentially perform traffic analysis or collude with a subset of users, though the authors suggest using Tor/Orbot to mitigate location tracking. For future work, exploring Multi-Party Computation (MPC) could further decentralize the power of the broker.