Efficient Private Storage of Sparse Machine Learning Data

Marvin Xhemrishi, Maximilian Egger, Rawad Bitar

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:

  1. 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.
  2. 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.
  3. 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

Abstract

We consider the problem of maintaining sparsity in private distributed storage of confidential machine learning data. In many applications, e.g., face recognition, the data used in machine learning algorithms is represented by sparse matrices which can be stored and processed efficiently. However, mechanisms maintaining perfect information-theoretic privacy require encoding the sparse matrices into randomized dense matrices. It has been shown that, under some restrictions on the storage nodes, sparsity can be maintained at the expense of relaxing the perfect information-theoretic privacy requirement, i.e., allowing some information leakage. In this work, we lift the restrictions imposed on the storage nodes and show that there exists a trade-off between sparsity and the achievable privacy guarantees. We focus on the setting of non-colluding nodes and construct a coding scheme that encodes the sparse input matrices into matrices with the desired sparsity level while limiting the information leakage.
BibTeX
@inproceedings{xhemrishi2022efficient,
  author = {Marvin Xhemrishi and Maximilian Egger and Rawad Bitar},
  title = {{Efficient Private Storage of Sparse Machine Learning Data}},
  booktitle = {ITW},
  year = {2022},
  url = {https://openreview.net/forum?id=zhfmTJCe9c},
}
Figure