Efficient Private Matching: Reimagining Friend Discovery with Blind Signatures

TL;DR

In the world of Proximity-based Mobile Social Networks (PMSNs), finding like-minded friends usually requires sharing personal interests—a major privacy risk. This paper presents a novel protocol that uses Blind Signatures to calculate profile similarity (weighted Euclidean distance) without revealing actual interests or relying on a central server. It achieves a 50% reduction in communication overhead compared to previous SOTA methods.

Background: The Price of Privacy

In PMSNs, users discover each other via Bluetooth or WiFi. While "Private Set Intersection" (PSI) allows two people to find common interests without revealing non-common ones, it often ignores how much a user cares about a specific interest. Previous "fine-grained" solutions tried to solve this but introduced heavy computational costs (like Commutative Encryption) that drain smartphone batteries instantly.

The authors' insight is simple: Blind signatures can guarantee that the same attribute results in the same signature without the signer ever seeing the attribute itself.

Methodology: The Core Mechanism

The protocol uses a Partially Blind Signature scheme derived from bilinear pairings. Here is the flow:

1. Blinding: The initiator (Alice) prepares signatures for her attributes. The responder (Bob) "blinds" his attributes with random factors and sends them to Alice.
2. Signing: Alice signs Bob’s blinded attributes. Because it is a "blind" signature, Alice doesn't know what she is signing.
3. Unblinding & Matching: Bob unblinds the signature. If they share an attribute, their signatures will match exactly.
4. Similarity Calculation: Instead of just counting matches, the protocol uses a weighted Euclidean distance: $D(A,B)=\sqrt{{\sum }_{i=1}^n(v_{A_i}-v_{B_i}{)}^2\cdot {\omega }_{ii}}$ where $v$ represents the priority/interest level.

Performance Benchmarks

The real triumph of this paper lies in its efficiency comparisons. The authors compared their scheme (BSPM) against several established protocols like WAS and Fine-grained PSI.

1. Communication Efficiency

Mobile devices are bandwidth-constrained. As shown in the comparison, the BSPM scheme maintains a linear growth in communication cost that is significantly lower than competitors.

2. Execution Time

Online computation is critical for user experience. For a standard profile size ($n=200$), the online computation cost for the initiator and responder remains under 10ms, making the "handshake" nearly instantaneous.

Critical Insight: Why it Works

The "magic" here is the movement of complexity. By using Partially Blind Signatures, the heavy lifting (signing) can often be pre-computed offline. Furthermore, the protocol avoids the "all-or-nothing" nature of early PSI by allowing Alice to see the distance between priority levels without seeing the content of Bob's unique attributes. This provides a "soft-match" capability essential for real-world social interactions.

Conclusion and Future Directions

The proposed scheme successfully bridges the gap between high-security cryptographic theory and the practical constraints of mobile hardware. While the current model assumes "honest-but-curious" behavior, future iterations could look into Malicious Adversary Models—where users might intentionally forge attribute levels to force a match.

By shifting from heavy encryption to lightweight signatures, this work sets a new standard for decentralized, privacy-first social discovery.