MDS-DSSE: Securing Search for Decentralized Social Data

TL;DR

Modern Searchable Symmetric Encryption (SSE) usually assumes one user owns all the data. In reality, your social data is scattered across phones, laptops, and cloud servers. This paper introduces MDS-DSSE, a framework that allows multiple devices to independently encrypt their data and indexes, which the cloud then merges into a single searchable index without ever knowing which device provided which search result.

The "Centralization" Fallacy in SSE

Most Dynamic Searchable Symmetric Encryption (DSSE) research operates under a hidden assumption: that a single entity can aggregate all data before outsourcing it. In the context of Social Networking, this is a deal-breaker. Chat history is fragmented across multiple "Data Sources" (DS).

If you try to use existing tools in this setting, you face a dilemma:

• Naive Multi-Indexing: Every device uploads its own index. The server searches all of them. Result? The server learns exactly which keywords are on your phone vs. your laptop—a massive privacy leak.
• Coordination Overheads: Forcing devices to coordinate "counters" for keywords requires an online table, which creates a performance bottleneck and a single point of failure.

Methodology: The XOR Fusion Approach

The core "Aha!" moment of this paper is replacing the traditional counter-based dictionary (like that of Cash et al.) with an encrypted bit-string index.

1. Independent Local Indexing

Instead of mapping a keyword to a list of file IDs, each keyword is mapped to a bit-string of length $n$ (total files). During the Setup phase, each Data Source is assigned a unique segment of this bit-string.

2. Blind Merging

Because the encryption of these bit-strings relies on XOR operations, the Storage Provider (SP) can merge local indexes from different sources by simply XORing the encrypted segments together. The SP never sees the underlying distribution of files across sources.

3. Efficient Updates and Lazy Deletion

The scheme handles new data through a pre-computed key queue, ensuring that "Add" operations are lightning-fast. For deletions, it uses a Lazy Deletion strategy: bits are not flipped immediately in the encrypted index but are corrected during the next search operation, minimizing the performance hit on write-heavy social apps.

Figure 1: The MDS-DSSE system model showing multiple data sources independently interacting with the cloud.

Performance vs. The State-of-the-Art

The authors compared MDS-DSSE against an extended version of the iconic Cash et al. (NDSS'14) scheme. The findings were revealing:

• Search Efficiency: In Cash et al., search time grows linearly with the number of results because each result requires a separate dictionary lookup. In MDS-DSSE, once the bit-string is decrypted, identifying results is just a bit-scan—making it much faster for common keywords.
• Index Size: While traditional indexes grow as you add more unique content to files, MDS-DSSE's index size is primarily governed by the total number of files and keywords, making it more predictable for large-scale deployments.

Figure 2: Performance metrics showing MDS-DSSE's superior scaling in index size compared to traditional DSSE extensions.

Critical Insight & Conclusion

MDS-DSSE solves a crucial structural problem: Decentralized indexing without centralized coordination. By moving from a "list-of-IDs" to a "bit-string-per-keyword" philosophy, the authors enable a "mergeable" property that is vital for the multi-device era.

Takeaway: If you are building an encrypted backup or search feature for a social app where data originates from multiple user devices, the XOR-merging strategy described here provides the best balance of multi-source privacy and search performance currently available in the standard model.

Limitations: The scheme still leaks Access Patterns (which files are accessed) and Search Patterns (when the same keyword is searched twice). For ultra-high security, one would still need to layer this with ORAM, albeit at a much higher computational cost.