P-match: Why Shared Priorities Matter More Than Shared Interests in Mobile Socializing

TL;DR

P-match is a novel privacy-preserving protocol for "friend discovery" in proximity-based networks (like searching for people nearby via Bluetooth). Unlike previous methods that just count how many interests you share, P-match looks at how much you care about them using a priority-aware similarity function, all while keeping your sensitive data encrypted.

The Problem: The "Quality vs. Quantity" Gap in Privacy

In the world of Proximity-based Mobile Social Networks (PMSNs), the standard way to find friends is "Private Set Intersection" (PSI). If Alice and Bob both have "Jazz" in their profiles, they get a match.

However, current SOTA (State Of The Art) approaches suffer from two fatal flaws:

1. Lack of Importance: Alice might value "Cancer Support" at a priority of 10 and "Music" at 1. If Bob also has both, standard protocols treat them as equal. P-match argues that matching on high-priority sensitive topics is a much stronger indicator of social compatibility.
2. The Third-Party Trap: Many existing schemes rely on a central server, creating a single point of failure and a massive privacy target.

Methodology: Turning Priorities into Math

The core innovation of P-match is the construction of a Priority-aware Similarity Function based on the Ochiai Coefficient.

1. Representation

Instead of a simple set, each user has a vector of tuples: $⟨interest,priority⟩$. To make this computable privately, the authors treat the priority as a "count." If you like "Music" with priority 3, it's mathematically treated as having three instances of that interest.

2. Encryption Strategy

The protocol uses Commutative Encryption. This is a powerful cryptographic tool where the order of encryption doesn't matter: $E_{Alice}(E_{Bob}(Interest))=E_{Bob}(E_{Alice}(Interest))$. This allows both parties to find intersections of their encrypted data without ever seeing the raw text.

The interaction flow between Alice (Initiator) and Bob (Responder) showing the multi-step handshake and local decryption.

Experiments: Performance on Real Hardware

The authors didn't just write a paper; they tested it on Nexus S smartphones. In mobile environments, CPU cycles equal battery drain, so efficiency is king.

Key Findings:

• Computation Speed: P-match is significantly faster than earlier protocols (like [7] and [8] in the paper). For 100 interests, P-match completes the handshake in ~19 seconds, whereas competing high-security models took over 6 minutes—an eternity in a "handshake" scenario.
• Energy Efficiency: Because it uses fewer intensive exponentiation operations, P-match consumes only ~9.8 Joules on the initiator side, making it practical for all-day background use on a smartphone.

The chart clearly illustrates that as the number of interests (m) increases, P-match maintains a much lower computation overhead than existing methods.

Critical Insight: Balancing Thresholds

A fascinating aspect of the security analysis is the Threshold Defense. If an attacker (Alice) tries to "fish" for Bob's data by inputting thousands of high-priority interests, the denominator of the P-match similarity function blows up, causing the match score to plummet. Bob’s device would then automatically terminate the connection, effectively neutralizing the "dictionary attack" on interests.

Summary & Future Outlook

P-match proves that we don't need to choose between rich social features (priorities) and strict privacy. By using clever set-to-vector transformations and commutative math, the authors created a system that is:

• Autonomous: No central server needed.
• Nuanced: High-priority matches are weighed more heavily.
• Fast: Optimized for the limited hardware of mobile devices.

As we move toward a more decentralized web (Web3/dApps), protocols like P-match will likely serve as the blueprint for how we discover communities without surrendering our personal profiles to a tech giant.