PE-MAP: Balancing Hidden Access Policies and Performance in Decentralized Social Networks

TL;DR

Decentralized Online Social Networks (DOSNs) aim to return data ownership to users, but current solutions often leak who is allowed to see a post through public access headers. This paper proposes a modified Predicate Encryption (PE) scheme that hides these policies. By using univariate polynomials to represent access rules and Bloom filters for fast membership checking, the authors demonstrate that complex, private access control can be achieved with a decryption latency of only 70ms.

Background: The Metadata Leakage Problem

In a typical decentralized social network (like Diaspora or Safebook), your data is stored on untrusted nodes. To control access, you encrypt your posts. However, for a friend to decrypt your post, they usually need to know which key to use. Most systems (using ABE or BE) attach the "Access Policy" (e.g., Friends AND Coworkers) directly to the ciphertext.

This is a massive privacy hole: an observer (or a non-authorized friend) can see exactly who you are talking to and what groups you belong to. The authors argue that Access Control must be privacy-preserving, meaning:

1. Only authorized users can decrypt.
2. Encrypted objects must not reveal the recipient list.
3. The existence/size of the recipient set should remain hidden.

Methodology: High-Performance Predicate Encryption

The authors identify Inner-Product Predicate Encryption as the solution because it naturally hides the policy within the mathematical structure of the ciphertext.

1. From Multivariate to Univariate

Standard PE is slow because it uses multivariate polynomials to handle complex "AND/OR" logic, leading to massive vector lengths.

• The Insight: The authors simplify this by using univariate polynomials.
• The Trade-off: To support "AND" (conjunctions), they create "virtual attributes" (e.g., a single attribute representing the intersection of 'Friend' and 'Family'). While this increases the number of keys a user holds ($2^g$ for $g$ groups), it keeps the ciphertext vectors short (recommended length: 10), which is the primary driver of performance.

2. The Efficiency Architecture

Figure 1: Comparison of encryption and decryption times as a function of the number of attributes.

3. Solving the "Blind Decryption" Problem

If the access policy is hidden, how does a user know which of the thousands of posts on a decentralized DHT they can actually decrypt? Trying to decrypt everything is computationally suicidal.

The authors introduce Bloom Filters.

• Each post includes a small Bloom filter containing salted hashes of the keyIDs of authorized recipients.
• To prevent size-leakage (i.e., seeing how many people can access a post), they pad the Bloom filter with random noise until it reaches a standard size.

Experimental Results: The News Feed Test

To prove this isn't just theoretical, the authors simulated building a Facebook-style news feed in a P2P environment.

• Setup: 300 friends, 1000+ DHT lookups, and PE-MAP decryption.
• Latency: Even with a 70ms decryption time per post, parallelizing DHT lookups allows the system to display the first 25 stories within 2 seconds.

Figure 2: News feed assembly time vs. decryption speed, showing that network latency (DHT) often outweighs cryptographic overhead.

Critical Insight & Conclusion

The "Academic Sweet Spot" of this paper is the realization that perfectly hidden policies are unfeasibly slow, but partially hidden policies (where a user might learn a bit about their own keys through usage, but external observers learn nothing) provide the necessary performance for a real-world application.

Limitations:

• The number of keys per user grows exponentially with the number of groups they belong to.
• Security relies on the profile owner correctly issuing and managing "virtual" attributes for every possible intersection of groups.

Takeaway: This work moves decentralized social networks away from "privacy-by-policy" toward "privacy-by-cryptography," proving that we can hide who is interacting without making the app unusable.