Entangled Cloud Storage

Giuseppe Ateniese, Özgür Dagdelen, Ivan Damgård, Daniele Venturi

Abstract

In traditional cloud storage, data integrity relies on active auditing by individual users, a process that is both burdensome and prone to neglect. This paper introduces a formal cryptographic framework for "Entangled Cloud Storage," a paradigm where multiple users' files are woven into a single, inseparable data structure known as a "clew." By leveraging polynomial interpolation and homomorphic encryption, the authors ensure that a malicious provider cannot delete or corrupt even a small portion of the data without destroying the ability of every user to recover their files. This creates a system of implicit, collective auditing: any successful file recovery serves as a proof of integrity for the entire dataset.

Introduction

As data storage increasingly migrates to the cloud, the risk of "Byzantine" providers—servers that may delete rarely accessed data to save costs or hide corruption—becomes a primary concern. Existing solutions, such as Provable Data Possession (PDP) and Proof of Retrievability (POR), require users to periodically challenge the server to prove data existence. However, these methods place the onus of security on the user; if a user fails to audit their data, the provider can delete it with impunity.

"Entangled Cloud Storage" shifts this incentive structure. By "entangling" files from diverse clients into a single digital clew, the system ensures that any significant modification to the storage medium disrupts the content of all constituent files. This paper provides the first formal, simulation-based security definition for such a system, removing the previous requirement for a trusted central authority and establishing a mathematically rigorous foundation for collective data defense.

The Problem: The Burden of Active Auditing

In standard cloud models, data is stored in silos. If a provider deletes User A's file, User B remains unaffected and unaware. To prevent this, users must engage in active auditing. This is problematic for several reasons:

  1. User Negligence: Users may forget or lack the resources to perform regular audits.
  2. Incentive Misalignment: Providers are incentivized to delete "cold" data that is rarely checked.
  3. Coordination Complexity: Prior attempts at entanglement (e.g., Aspnes et al., 2004) required a trusted third party to manage the entanglement process, creating a single point of failure and a significant security bottleneck.

Methodology

The authors propose a decentralized entangled storage system built upon several advanced cryptographic primitives:

1. Entangled Encoding via Polynomial Interpolation

To entangle $n$ files, the system treats each file (combined with unique randomness) as a coordinate $(x_i, y_i)$ on a 2D plane. The system then calculates a unique polynomial $c(x)$ of degree $n-1$ that passes through all these points. The coefficients of this polynomial constitute the "clew" stored on the server. Because the polynomial is defined by all points, any change to the coefficients fundamentally alters the value of the polynomial at every $x_i$.

2. Universal Composability (UC) Framework

The authors define their security model using the UC framework. This ensures that the protocol remains secure even when executed concurrently with other unknown protocols, providing a "gold standard" for cryptographic reliability.

3. Privacy-Preserving Recovery

To maintain privacy, users must be able to recover their data without revealing which file they are accessing. The authors utilize Somewhat Homomorphic Encryption (SHE). A client sends an encrypted version of their coordinate $x_i$, and the server uses the homomorphic properties of the encryption to evaluate the polynomial $c(x_i)$ on the encrypted data. The server then returns the result, which only the client can decrypt.

4. Integrity Proofs

To prevent the server from returning incorrect results during recovery, the system employs Succinct Arguments of Knowledge (SNARKs) or interactive arguments. The server must provide a short mathematical proof alongside the recovery data, demonstrating that the polynomial was evaluated correctly according to the stored clew.

Key Insights and Results

Implicit Auditing and All-or-Nothing Integrity (AONI)

The core contribution of the paper is the formalization of All-or-Nothing Integrity (AONI). The authors prove that if a server has even a small amount of uncertainty regarding the clew (e.g., due to partial deletion), the probability of successfully answering any client's recovery request becomes negligible. This transforms every routine data download into an implicit audit of the entire clew. As long as one user can recover their data, the entire community can be confident that the global data structure is intact.

Decentralization and Privacy

By utilizing secure multi-party computation (MPC) techniques, the authors demonstrate how clients can entangle their files themselves. This removes the need for a trusted middleman. Furthermore, they prove that the resulting clew reveals no information about individual files, ensuring that entanglement does not come at the cost of confidentiality.

Efficiency Optimizations

While the initial entanglement process is computationally intensive, the authors provide methods to optimize recovery. By using clever polynomial encoding tricks, they reduce communication complexity from $O(n)$ to $O(\log n)$ or $O(\sqrt{n})$, making the system more viable for larger groups of users.

Limitations and Future Work

Despite its theoretical strengths, the current framework faces practical challenges:

  • Static Nature: The current protocol is static; adding, updating, or deleting a single file requires re-computing the entire clew. Developing a "fully dynamic" entangled storage system remains a significant open challenge.
  • Coordination Overhead: The initial MPC-based entanglement requires significant coordination among clients, making it most suitable for structured groups (e.g., financial consortiums or research networks) rather than unorganized public users.
  • Server Computation: The computational load on the server for homomorphic evaluation of high-degree polynomials is substantial and may limit scalability for extremely large datasets.

Conclusion

Entangled Cloud Storage represents a shift from individual to collective security in the cloud. By mathematically linking the fate of all files in a clew, the framework ensures that the provider must protect all data to satisfy any single user. This research provides the necessary formal definitions and cryptographic tools to move data entanglement from a conceptual idea to a provably secure reality.

Summary updated

BibTeX
@article{ateniese2012entangled,
  author = {Giuseppe Ateniese and Özgür Dagdelen and Ivan Damgård and Daniele Venturi},
  title = {{Entangled Cloud Storage}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2012},
  url = {https://openreview.net/forum?id=xFeDkgJb5Eq},
}
Figure