EWPM: Revolutionizing Private Friend Discovery with Confusion Matrix Transformation

TL;DR

In the world of Proximity-based Mobile Social Networks (PMSNs), finding "the right friend" usually requires revealing sensitive personal profiles. EWPM (Efficient Weight-based Private Matching) breaks the trade-off between privacy and performance. By ditching heavy Homomorphic Encryption in favor of a lightweight Confusion Matrix Transformation (CMT), it enables fine-grained, weight-aware matching that runs in under 10ms on mobile hardware.

Background: The Price of Privacy

In a PMSN, your phone looks for nearby peers with similar interests via Bluetooth or WiFi. Traditional solutions use Private Set Intersection (PSI). However, these methods have two major flaws:

1. Lack of Nuance: They treat all interests equally. They can't distinguish between someone who "likes" coffee and someone who is a "professional barista."
2. Computational Overhead: To hide data, they use complex math (exponentiations in huge prime fields) that drains batteries and causes lag.

The Core Insight: Weight-Awareness Meets Matrix Masking

The authors propose that professional-grade privacy doesn't always require expensive asymmetric encryption. Instead, they represent a user's profile as a Profile Matrix ($P_{limesn}$), where $l$ represents weight levels and $n$ represents attributes.

1. Fine-Grained Weighting

Instead of a simple binary "yes/no" for an interest, users assign a weight ($1$ to $l$). A specialized Weight Matrix ($W$) is used to prioritize matches where both users have high interest levels in the same topic.

2. The CMT Algorithm

The "magic" resides in how the data is hidden. Instead of encrypting an attribute $a_{ij}$, the initiator masks it using two large primes $p,q$ and random noise matrices $C$ and $R$:

• If the user has the attribute: $a_{ij}^{\prime }=p+c_{ij}+r_{ij}q$
• If not: $a_{ij}^{\prime }=c_{ij}+r_{ij}q$

This transformation allows the responder to perform matrix multiplication on the "confused" data. The result, when decrypted with a secret key $K$, yields the common attributes scaled by $p^2$, effectively separating the signal from the noise.

Figure 1: The mathematical formulation for calculating the weighted similarity $H$ via matrix dot-products.

Security: Level-I vs. Level-II

• Level-I (HBC): Protects against "Honest-But-Curious" users who follow the rules but want to peek at your data.
• Level-II (Internal Attackers): An enhanced version (Algorithm 3) where the responder only sends back a single aggregated value $\delta$, preventing the initiator from reverse-engineering specific attributes from the result matrix $D$.

Performance: Why it Wins

The most striking part of the paper is the performance gap between EWPM and previous SOTA methods like Fine-grained [10] or WAS [11].

• Online Execution: While WAS requires $n$ 1024-bit exponentiations (very slow), EWPM mostly uses 1024-bit modular multiplications.
• Results: At $n=100$, the total execution time stays well within the "instantaneous" range (< 10ms).

Figure 2: Complexity analysis showing the dramatic reduction in online computation compared to WAS and Fine-grained protocols.

Figure 3: Online computation cost scales linearly with the number of attributes $n$, remaining significantly lower than baseline methods.

Conclusion & Insights

EWPM proves that for proximity-based social interactions, lightweight matrix transformations are the way forward. By moving the heavy lifting to "offline configuration" (Algorithm 1) and using CMT for the "online matching," the protocol respects both the user's privacy and the device's battery life.

Future Outlook: While highly efficient, this method relies on the "Honest-But-Curious" assumption for its basic version. Future iterations could explore integrating ZK-SNARKs to ensure honesty without sacrificing the efficiency gains of the CMT core.