Abstract
Quantifying information leakage in continuous data is a critical challenge for privacy-preserving multiparty computation (MPC). This study investigates alternatives to standard Mutual Information (MI), such as f-divergences and Integral Probability Metrics (IPM), evaluating their performance and computational feasibility. We compare estimation techniques including histogram-based methods, k-Nearest Neighbors (k-NN), and Sinkhorn distances. Our findings highlight the "dimensionality wall" faced by traditional metrics and position Maximum Mean Discrepancy (MMD) as a scalable alternative for high-dimensional leakage assessment.
Introduction
In information theory, Mutual Information (MI) is the standard metric for measuring the information shared between two variables. While well-defined for discrete settings, MI can become infinite or difficult to interpret when applied to continuous variables. This poses a significant problem for modern privacy-preserving distributed computing, where newer MPC schemes operate directly on real numbers to enhance efficiency. In these continuous scenarios, robust methods are required to quantify how much a "share" of a secret might leak. This paper addresses the challenge of defining and estimating these leakage measures when underlying probability distributions are unknown and must be inferred from samples.
Methodology
The study evaluates standard KL-divergence-based MI against several alternative metrics:
- f-divergences: Kullback-Leibler (KL), Jensen-Shannon (JS), and Total Variation (TV).
- Integral Probability Metrics (IPM): Wasserstein-1 distance (Earth Mover’s Distance) and Maximum Mean Discrepancy (MMD).
Four primary estimation approaches are deployed:
- Histogram-based Estimation: Approximating probability density functions by binning the data domain.
- Optimal Transport (OT): Calculating Wasserstein distance via Linear Programming (LP) and the Sinkhorn distance (an entropic-regularized version).
- k-Nearest Neighbor (k-NN): A sample-based estimator for KL-divergence that avoids explicit density estimation.
- Kernel Mean Embedding: Utilizing the "kernel trick" (Gaussian kernel) to compute MMD in a high-dimensional feature space.
Experimental Evaluation
Two synthetic scenarios serve as benchmarks:
- Scenario 1 (Secret and Share): A 1D/2D case where a secret $X$ is obfuscated by Gaussian noise $R$, providing a closed-form theoretical ground truth.
- Scenario 2 (Three-Party Multiplication): A complex 5D scenario involving a Shamir secret sharing scheme over real numbers, testing scalability in higher dimensions.
Results and Discussion
Convergence and Stability
In the 1D Gaussian scenario, histogram-based KL, TV, and JS divergences demonstrated smooth convergence after approximately $10^5$ samples. As shown in Figure 1, the KL estimate successfully matched the theoretical value of 0.048. Conversely, k-NN estimators proved unstable, failing to converge for the more complex multiplication scenario within the tested sample sizes.
Computational Efficiency
A key finding is the significant speed advantage of the Sinkhorn approximation over standard Linear Programming for calculating Wasserstein distance. As detailed in the following comparison, for $10^7$ samples, the Sinkhorn estimation required only 0.015 seconds, compared to 2.04 seconds for the LP-based calculation.
The Dimensionality Wall
Histogram-based methods and Optimal Transport techniques encountered a "memory wall" in the 5D multiplication scenario. The exponential growth in required bins made the cost matrix too large for memory, rendering these methods impractical for high-dimensional leakage measurement. In contrast, MMD emerged as a highly practical tool; its convergence rate of $1/\sqrt{N}$ is independent of data dimensionality, allowing for stable performance where other methods failed.
Conclusion
The study highlights the "Curse of Dimensionality" as a primary hurdle for traditional leakage metrics. While MMD provides a promising, scalable alternative, it often serves as a lower bound rather than an exact MI equivalent. Future research should explore more efficient high-dimensional estimation techniques, potentially leveraging neural estimation for mutual information in continuous MPC settings.
Summary updated