PriMatch: Solving the Fairness Crisis in Mobile Social Friend Discovery

TL;DR

PriMatch is a novel protocol designed for Mobile Social Networks (MSNs) that enables users to find common-interest friends without leaking their personal profiles. Unlike previous methods, it introduces a Blind Vector Transformation technique to prevent "runaway attacks"—where a user steals information and vanishes. It achieves 40% faster performance than previous SOTA solutions while ensuring both privacy and protocol fairness.

The "Runaway" Problem in Digital Handshakes

In the context of Mobile Social Networks (MSNs), finding a friend is essentially an Interest-Profile Matching problem. However, traditional Private Set Intersection (PSI) methods suffer from a "fairness gap." Typically, if User A and User B want to see if they match, the protocol runs twice. A malicious User A might finish the first round to see User B's interests and then simply "run away" (abort) before User B gets the result.

Furthermore, most protocols assume your "profile" and your "search interest" are the same thing. In reality, you might have a broad profile but are only searching for a specific type of friend today. This mismatch between research models and real-world behavior makes existing solutions both unfair and inflexible.

Methodology: Blind Transformations and Fairness

The core innovation of PriMatch lies in its multi-layered Blind Vector Transformation. The authors leverage the Homomorphic properties of the Paillier Cryptosystem, allowing one party to operate on encrypted data without ever seeing the raw values.

1. Vector Operations

The protocol uses five specific primitives to transform data into a "blind" state:

• VecAdd: Adds a random vector to the encrypted profile.
• VecExt & VecRev: Appends dummy attributes to mask the actual count of matches.
• VecShuffle: Randomizes the order of attributes so the original index cannot be traced.

2. The Verification Logic

To stop attackers from guessing the result, PriMatch uses a Blind Linear Transformation ($y=ax+b$). Users send a hash of their results to a third-party verifier. Because the results are linearly masked, even a verifier colluding with one of the users cannot reverse-engineer the original match count.

Performance Benchmarks

Technical efficiency is critical for mobile apps. The research team implemented PriMatch in Java and tested it against varying vector sizes (up to 100 attributes).

• Efficiency: Matching 20 attributes takes only ~1.5 seconds, which is a 40% speed increase over previous secure discovery protocols.
• Scalability: The computation time grows linearly ($O(n)$) alongside the number of attributes, making it suitable for complex profiles.
• Minimal Overhead: The fairness-securing "Linear Transformation" check takes less than 48ms, proving that fairness doesn't have to come at the cost of speed.

Technical Insight: Why it Works

The "magic" of PriMatch is the Blind Reverse (VecRev). By intentionally changing $k$ elements in an encrypted vector and forcing the other side to match a target count of $s=e+l-k$, the protocol creates a system where a user only learns the result if they are honest. If they try to abort early or guess the result, Theorem 1 in the paper proves the mathematical probability of a successful guess is negligible (bounded by $3/\ln (n)$).

Conclusion & Future Outlook

PriMatch represents a significant step forward in making MSN interactions "secure by design." It effectively balances the tension between privacy, fairness, and performance.

While current benchmarks are impressive, the next frontier for this research involves Fuzzy Matching. Currently, PriMatch looks for exact attribute hits (e.g., "Gaming" == "Gaming"). Future iterations will need to handle semantic similarities (e.g., "Gaming" matching "PlayStation") to truly replicate the nuance of human social discovery.

Takeaway for Engineers:

If you are building decentralized social apps, the "Runaway Attack" is a real threat to user trust. PriMatch shows that you can implement a "Commit-Then-Verify" pattern using homomorphic blinding to ensure that no user is left empty-handed in a data exchange.