PEM: Achieving High-Utility Differential Privacy via Hybrid Secret Sharing

TL;DR

Building a privacy-preserving system for large-scale data mining usually forces a compromise: you either get strong privacy with high noise (useless results) or efficiency with weak privacy. PEM breaks this deadlock. By combining Secret Sharing for noise-free aggregation and Differential Privacy (DP) at the server level, it reduces noise variance by orders of magnitude (from $O(extclients)$ to $O(extservers)$) while supporting high-dimensional iterative algorithms like Gradient Descent and k-means.

The "Noise Explosion" Problem

In traditional distributed Differential Privacy, every participant (client) adds noise to their local data before sending it to a central aggregator. In a system with 1,000 clients, the final aggregate contains 1,000 instances of noise. For iterative algorithms, this noise compounds at every step, quickly drowning out the actual signal.

The alternative—Homomorphic Encryption—is theoretically sound but practically slow. Performing high-dimensional vector additions in an encrypted domain for thousands of clients is computationally prohibitive for real-time applications.

Methodology: The Best of Both Worlds

PEM's core insight is that cryptography can be used to perform aggregation without adding noise early.

1. Hybrid Architecture

The system involves three roles:

• Clients: Hold the raw data.
• Servers: (Typically 2 or 3) Non-colluding entities that receive secret-shared "fragments" of data.
• Aggregator: Combines the results from the servers to update the global model.

2. Secret Sharing over Small Fields

Instead of adding Laplace noise at the source, clients use Additive Secret Sharing. A client $C_i$ with vector $v_i$ splits it into $m$ random vectors $v_{i,j}$ such that their sum equals $v_i(\mathrm{mod}\varphi )$. Since these fragments look like random noise individually, no information is leaked to any single server.

3. Server-Side Noise Injection

Once the servers have summed the fragments from all $n$ clients, they add Laplace noise $r\sim extLap(L/ϵ)$. Because the aggregation was noise-free until this point, the final result only carries $m$ units of noise (where $m$ is the number of servers, e.g., 2), rather than $n$ (total clients).

Core Algorithms & Optimizations

PEM is designed to be a general framework. It provides a private Gradient Method that serves as a foundation for:

• Logistic Regression: Using the gradient of the loss function.
• k-means Clustering: Using $ϵ$-splitting to handle both centroid sums and cluster counts separately.
• Apriori: Using dynamic sensitivity ($L$) settings to handle different itemset lengths.

The Insight of $ϵ$-Splitting

In k-means, updating a centroid requires two values: the sum of the records ($\sum x$) and the count of records ($n$). PEM allows users to allocate ${ϵ}_1$ to the sum and ${ϵ}_2$ to the count. Since the "count" dimension is much less sensitive than the "data" dimension, this fine-grained control prevents over-noising of the most sensitive parts of the data.

Experimental Validation

The authors tested PEM against a "Noise-only" approach (adding noise at every client).

• Accuracy: For Logistic Regression on the Adult dataset, PEM's accuracy is nearly identical to the non-private version. In contrast, the noise-only approach sees a sharp drop in accuracy as the number of clients increases.
• Scalability: The computational cost for servers scales linearly with the number of clients, but the actual time spent on vector addition is negligible (refer to Figure 3c). The real bottleneck remains network communication, which PEM optimizes via mini-batching.

Critical Analysis & Takeaways

The brilliance of PEM lies in its pragmatism. It realizes that we don't need "Total Trust" or "No Trust." By assuming two or three major cloud providers (servers) won't collude, we can use lightweight crypto to make Differential Privacy actually work for big data.

Limitations: The system still relies on a semi-honest server assumption. If all servers collude, the differential privacy guarantee still holds (because of the server-side noise), but the underlying secret sharing protection is broken.

Future Impact: This work paves the way for cross-institutional AI in heavily regulated sectors like healthcare and finance, where "pooling" data is illegal but "sharing insights" is essential.