Protecting Big Data Privacy Using Randomized Tensor Network Decomposition and Dispersed Tensor Computation

Jenn-Bing Ong, Wee Keong Ng, Ivan Tjuawinata, Chao Li, Jielin Yang, Sai None Myne, Huaxiong Wang, Kwok-Yan Lam, C.-c. Jay KuoarXiv 2021 · arXiv

Introduction

As organizations increasingly outsource big data storage and computation to the cloud, they face a persistent "privacy vs. utility" dilemma. While standard encryption methods like AES are highly secure for storage, they render data unusable for computation without decryption, creating significant security risks during the processing phase. Advanced alternatives such as Homomorphic Encryption (HE) or Secure Multi-Party Computation (SMPC) allow for computation on encrypted data but often suffer from massive computational overhead or communication bottlenecks that prevent them from scaling to "Big Data" dimensions.

This paper introduces a novel approach to this challenge by leveraging the mathematical properties of Tensor Networks (TN). By using randomized TN decompositions, the authors create "secret shares" of data that enable secure, dispersed storage and computation across multiple cloud providers without the heavy overhead of traditional cryptographic methods.

The Tensor Network Approach

The core innovation lies in treating Tensor Network decompositions—mathematical structures that break a large multi-dimensional array into smaller, interconnected "cores"—as a form of secret sharing. Unlike a simple file split, these decompositions are mathematically non-unique and uninterpretable in isolation. A single core typically appears as Gaussian or Laplacian noise, making it useless to an adversary who does not possess the other pieces and the associated metadata.

Randomized Decomposition and Controlled Perturbation

The authors propose randomized versions of four standard decompositions: rTD (Tucker), rHT (Hierarchical Tucker), rTT-SVD (Tensor-Train), and rTR-SVD (Tensor-Ring). These structures are visualized below:

Overview of Tensor Network architectures used for data decomposition: (a) Tucker, (c) Hierarchical Tucker, (d) Tensor Train, and (e) Tensor Ring.

To ensure privacy, the authors apply a controlled perturbation matrix ($\Delta$) during the Singular Value Decomposition (SVD) steps of the process. This perturbation "smears" the structural information of the original data across the resulting tensor cores. Because TNs are multilinear, operations like addition or matrix-vector multiplication can be performed directly on these individual randomized cores stored on different servers. The servers never see the full original tensor, only their specific randomized fragment.

Experimental Results and Insights

The framework was benchmarked using a variety of datasets, including 1D smartphone inertial sensor data, 3D face image databases, and synthetic tensors.

Privacy and Reconstruction Accuracy

Using metrics like Normalized Mutual Information (NMI) and Pearson correlation, the study demonstrated that privacy leakage to a "semi-honest" cloud provider is minimal, provided the tensor cores are sufficiently large. Crucially, the "controlled" nature of the perturbation ensures that the data can be reconstructed with very low distortion (measured by $L_2$-dissimilarity) once the cores are reunited, even at high compression ratios.

Efficiency and Compression

One of the primary advantages of this method is its natural efficiency. Because TNs are inherently designed for dimensionality reduction, this privacy method actually reduces the storage footprint of big data, whereas traditional encryption often increases it. The randomized algorithms (rTT-SVD, rTD) incur only a slight time penalty compared to standard versions—for instance, rTT-SVD took approximately 0.28s to decompose a face database compared to 0.18s for the non-randomized version.

Challenges and Future Directions

The authors identified a specific "low-rank" challenge: correlation structures contributing to higher variability (lower rank) are harder to perturb effectively. This means the most "important" parts of the data are theoretically the most vulnerable, requiring careful tuning of the perturbation thresholds.

Furthermore, while the stored cores are secure, performing dispersed computations can gradually leak information over time. The authors suggest "continually ingesting fresh entropy" (adding new randomness) during computation to mitigate this risk. Future work will focus on extending this framework to Federated Learning environments and integrating formal Differential Privacy guarantees to protect individual data points within large training sets.

Summary updated

Abstract

Data privacy is an important issue for organizations and enterprises to securely outsource data storage, sharing, and computation on clouds / fogs. However, data encryption is complicated in terms of the key management and distribution; existing secure computation techniques are expensive in terms of computational / communication cost and therefore do not scale to big data computation. Tensor network decomposition and distributed tensor computation have been widely used in signal processing and machine learning for dimensionality reduction and large-scale optimization. However, the potential of distributed tensor networks for big data privacy preservation have not been considered before, this motivates the current study. Our primary intuition is that tensor network representations are mathematically non-unique, unlinkable, and uninterpretable; tensor network representations naturally support a range of multilinear operations for compressed and distributed / dispersed computation. Therefore, we propose randomized algorithms to decompose big data into randomized tensor network representations and analyze the privacy leakage for 1D to 3D data tensors. The randomness mainly comes from the complex structural information commonly found in big data; randomization is based on controlled perturbation applied to the tensor blocks prior to decomposition. The distributed tensor representations are dispersed on multiple clouds / fogs or servers / devices with metadata privacy, this provides both distributed trust and management to seamlessly secure big data storage, communication, sharing, and computation. Experiments show that the proposed randomization techniques are helpful for big data anonymization and efficient for big data storage and computation.
BibTeX
@misc{ong2021protecting,
  author = {Jenn-Bing Ong and Wee Keong Ng and Ivan Tjuawinata and Chao Li and Jielin Yang and Sai None Myne and Huaxiong Wang and Kwok-Yan Lam and C.-C. Jay Kuo},
  title = {{Protecting Big Data Privacy Using Randomized Tensor Network Decomposition and Dispersed Tensor Computation}},
  year = {2021},
  eprint = {2101.04194},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.04194},
}
Figure