Abstract
Modern machine learning relies heavily on sparse data representations to optimize storage and computational performance. However, traditional information-theoretic privacy methods, such as Shamir’s Secret Sharing, typically destroy this sparsity by introducing dense random noise. This paper proposes a novel secret sharing scheme that maintains data sparsity by relaxing the requirement for perfect privacy. By utilizing a tunable trade-off between information leakage and sparsity, the authors demonstrate a method to generate shares that remain computationally efficient while providing strictly bounded privacy guarantees.
Introduction
In the landscape of modern machine learning (ML), data is frequently represented as sparse matrices—structures where the vast majority of entries are zero. Examples range from high-dimensional feature vectors in face recognition to the weight matrices of pruned neural networks. The primary advantage of sparsity is efficiency: it allows for significant compression and accelerates mathematical operations by skipping zero-valued entries.
Protecting this sensitive data in distributed environments usually involves secret sharing. However, standard cryptographic approaches are often incompatible with sparse structures. For instance, Shamir’s Secret Sharing requires adding a dense, uniformly random matrix to the private data to ensure perfect information-theoretic security. This process transforms sparse secrets into dense shares, negating the storage and speed benefits of the original data. This paper addresses this conflict by introducing a coding scheme that preserves sparsity at the cost of a controlled, minimal amount of information leakage.
Methodology
The authors propose a coding framework where the "padding" or noise matrix $R$ is not independent of the input matrix $A$, but rather specifically designed to align with its structure.
1. Optimization Framework
The core of the approach is a convex minimization problem. The objective is to determine the optimal probability distribution for the entries of the padding matrix $R$ such that the total information leakage—quantified by mutual information—is minimized, subject to a target sparsity level for the resulting shares ($R$ and the padded matrix $A+R$).
2. Probability Mass Function (PMF) Design
The search for an optimal distribution is narrowed to a class of PMFs that prioritize three specific structural outcomes:
- Zero Inheritance: Maintaining a zero where the original data already has a zero.
- Padding Sparsity: Forcing a zero in the padding matrix $R$, even if it introduces minor leakage.
- Padded Sparsity: Forcing a zero in the sum $A+R$ to ensure the share remains sparse.
3. Straggler Tolerance via Fractional Repetition
To ensure the system is robust against slow or unresponsive storage nodes (stragglers), the authors integrate their sparse shares with fractional repetition codes. By dividing sparse shares into sub-shares and distributing them across $n$ nodes, the system ensures that the secret can be reconstructed from any $k$ nodes while maintaining the desired sparsity at each individual node.
Key Insights and Theoretical Contributions
The Sparsity-Privacy Trade-off
The research establishes that perfect privacy and high sparsity are mutually exclusive in distributed storage. However, by allowing a mathematically bounded amount of leakage, systems can achieve significant gains in efficiency. The authors suggest that in many contexts, such as biometric features, a small amount of leakage might reveal a general contour without compromising the specific identity of the subject.
Dependent Noise and Symmetry
A critical finding of the paper is that the noise must be dependent on the data to preserve structure. By aligning the zeros of the noise with the zeros of the data, the shares remain sparse. Furthermore, numerical results indicate that the minimum information leakage is achieved when both shares ($R$ and $A+R$) are designed to have identical levels of sparsity.
Results and Performance
The authors evaluated their scheme using mathematical proofs and numerical simulations based on i.i.d. sparse matrix models over a finite field $\mathbb{F}_q$. Key findings include:
- Optimal Leakage Curves: The paper provides a polynomial-time solution (Theorem 1) to calculate the exact distribution required to minimize leakage for any given sparsity target.
- Storage Efficiency: The proposed scheme significantly outperforms classical secret sharing in storage-constrained environments when high average sparsity ($s_{avg}$) is required.
- Quantitative Benchmarks: In a simulation with a field size of $q=256$ and an initial data sparsity of $0.95$, the scheme maintained high share sparsity with a relative leakage ($\bar{\epsilon}$) of only $0.0135$. This represents a leakage of only 1.35% of the total entropy, a negligible amount compared to the massive reduction in storage overhead.
Limitations and Future Directions
While the paper provides a robust theoretical foundation, several areas remain for future exploration:
- Structural Correlations: The current model assumes entries are independent and identically distributed (i.i.d.). Real-world ML data often contains complex correlations that could be exploited to further optimize sparsity or might necessitate different privacy bounds.
- Node Collusion: The current privacy guarantees assume a single-node adversary ($z=1$). Future work is needed to extend these bounds to scenarios where multiple storage nodes collude to reconstruct the secret.
- Computational Overhead: Although the resulting shares are sparse and efficient to process, the initial optimization and encoding process introduce computational costs that require further characterization for real-time applications.
Summary updated