PAIRING: Accelerating Privacy-Preserving Friend Matching for the 5G Era

TL;DR

Finding friends with common interests in mobile apps usually requires handing over your entire profile to a centralized server. While Private Set Intersection (PSI) offers a cryptographic solution, it has historically been too slow for mobile devices. This paper introduces PAIRING, a framework powered by a new protocol called LL-PSI, which slashes matching latency by 50%, enabling secure "active matching" without compromising user identities or interest sets.

The "Privacy vs. Performance" Bottleneck

Modern social networks rely on interest-based matching. Usually, a server sits in the middle, reading everyone's sensitive profiles. While encryption can hide these profiles, traditional methods like Attribute-Based Encryption (ABE) suffer from "key escrow" issues (you have to trust the key issuer), and current PSI protocols are computationally "heavy."

Imagine waiting 40 seconds for your phone to tell you if someone nearby likes the same music as you. That is the current SOTA barrier. The core challenge is: How can we compute the intersection of two private sets (Initiator's interests vs. Candidate's interests) in a few seconds on a mobile CPU?

Methodology: LL-PSI and the Architecture of PAIRING

The authors' breakthrough, LL-PSI, shifts the paradigm. Instead of the initiator doing the heavy lifting, the responder (Candidate) provides "pre-tags"—calculated arrays that allow the initiator to verify matches using simple multiplication rather than complex exponentiation.

The PAIRING Framework

The system involves three entities: the Server (facilitator), the Initiator, and the Candidate.

1. Blind Signatures: Users get one-time-use tokens from the server so the server can't link their real identity to their matching requests.
2. Tor Integration: All traffic is routed through Tor to mask network-level metadata (IP addresses).
3. The Pigeonhole: A one-time mailbox system ensures that even the communication "pattern" (who talks to whom and when) remains hidden from the server.

Fig 1: The three-party interaction model of PAIRING.

Why LL-PSI is Faster

In standard PSI, the initiator often performs $O(mimesl)$ operations ($m,l$ being set sizes). In LL-PSI, the candidate pre-computes power-of-two variants of blinded tags ($x^2,x^4,x^8...$). The initiator then only needs to perform a "Product of Sums" operation based on the bits of their secret key. This drastically reduces the CPU cycles required on the mobile side.

Fig 2: The LL-PSI workflow showing the shift to pre-tag arrays.

Experimental Results

The authors tested PAIRING using the NIST P-512 curve on a standard mobile-grade processor.

• Latency: For a scenario with 99 candidates, the initiator completes matching in ~10 seconds, roughly 2x faster than previous benchmarks.
• Communication: The cost remains manageable at the KB level per request. As 5G provides massive throughput, the slight increase in communication data (sending arrays instead of single points) is a winning trade-off for the massive gain in speed.

Fig 3: Initiator computation latency vs. number of responding candidates.

Critical Insight: The Future of "Blind" Discovery

The real value of PAIRING lies in its Matching Pattern Protection. Most privacy schemes protect the content of the interests but reveal who is matching. PAIRING uses fixed-length padding and random mailbox addresses to ensure the server cannot even distinguish between a "failed match" and a "successful conversation."

Limitations:

• The protocol assumes a semi-honest server. If a server acts maliciously (e.g., dropping packets selectively), further verification steps would be needed.
• While 10 seconds is a 50% improvement, it still feels slow for "instant" discovery; hardware acceleration (TEE/GPU) might be the next step.

Conclusion

PAIRING demonstrates that we don't have to sacrifice our privacy for social convenience. By re-engineering the mathematical flow of PSI, the authors have brought decentralized, private friend discovery one step closer to our pockets.