Entangled Cloud Storage

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

This paper, "Entangled Cloud Storage," presents a rigorous cryptographic framework for a "one-for-all, all-for-one" approach to data integrity in the cloud. By weaving multiple users' files into a single data structure, the authors ensure that a cloud provider cannot delete or modify even a small portion of the data without destroying the ability of every user to recover their files.

TL;DR

The authors provide the first formal, simulation-based security definition for "entangled cloud storage," a system where files are intertwined into a single "clew." This ensures that if a malicious cloud provider deletes any significant part of the storage, all files become unrecoverable, effectively turning every user's routine data access into an implicit integrity audit for the entire community.

What Problem Does This Paper Address?

In standard cloud storage, users worry about "Byzantine" providers—servers that might delete rarely accessed files to save space or hide data corruption. Current solutions like Provable Data Possession (PDP) and Proof of Retrievability (POR) allow users to "audit" the server. However, these require users to actively and regularly challenge the server to prove the data is still there. If a user forgets to audit, their data could be gone.

Data Entanglement offers a different incentive structure. Instead of individual audits, it "entangles" files from many different clients into a single digital "clew." The goal is to make it so that any significant change to the clew disrupts the content of all files. This creates a collective defense: as long as one client can successfully recover their file, everyone else can be confident their data is still intact.

Prior work on this concept (Aspnes et al., 2004) relied on a "trusted authority" to create the entanglement, which is a major bottleneck and security risk. This paper seeks to remove that requirement and provide a mathematically sound security proof.

Methods

The authors employ several advanced cryptographic building blocks to build a decentralized entangled storage system:

  1. Entangled Encoding (Polynomial Interpolation): To entangle $n$ files, the system treats each file (plus some randomness) as a point $(x_i, y_i)$ on a 2D plane. It then calculates a unique polynomial $c(x)$ of degree $n-1$ that passes through all these points. The coefficients of this polynomial form the "clew" stored on the server.
  2. Universal Composability (UC) Framework: The authors define security using the UC framework, a "gold standard" in cryptography that ensures a protocol remains secure even when it is run alongside other unknown protocols.
  3. Somewhat Homomorphic Encryption (SHE): To recover a file without revealing which file is being accessed (maintaining privacy), the client sends an encrypted version of their coordinate $x_i$. The server uses the homomorphic properties of the encryption to evaluate the polynomial $c(x_i)$ while the data is still encrypted.
  4. Succinct Arguments of Knowledge (SNARKs/Interactive Arguments): To prevent the server from lying about the computation, the server must provide a short mathematical proof that it evaluated the polynomial correctly.

Datasets

Not discussed in the paper. As a theoretical cryptography paper, the focus is on mathematical proofs and algorithmic complexity rather than empirical testing on specific datasets.

Key Insights and Ideas

  • Implicit Auditing: The most powerful idea is that entanglement transforms data recovery into an audit. A user doesn't need to send a special "challenge" to the server; simply downloading their own file proves the server hasn't tampered with the global "clew."
  • All-or-Nothing Integrity (AONI): The authors formalize the "All-or-Nothing" property. They prove that if a server has even a small amount of "uncertainty" about the clew (e.g., because they deleted a few blocks), the probability of them successfully answering any client's recovery request becomes negligibly small.
  • Privacy within the Clew: Despite the files being "tangled" together, the authors prove that the clew reveals no information about the individual files it contains, and clients do not need to cooperate with each other to recover their own data.
  • Removing the Middleman: By using secure multi-party computation (MPC) techniques, the authors show how clients can entangle their files themselves, eliminating the need for a trusted third party to manage the "clew."

Key Results

  • First Simulation-Based Definition: The paper provides the first formal security model for entangled storage that accounts for collusion between a malicious server and some of the clients.
  • Information-Theoretic Integrity: They prove that their polynomial-based encoding scheme achieves "All-or-Nothing Integrity" even against an adversary with infinite computing power.
  • Efficiency Optimizations: While the initial entanglement is computationally heavy, the authors propose a recovery method that reduces communication complexity from $O(n)$ to $O(\log n)$ or even $O(\sqrt{n})$ using clever polynomial encoding tricks.

Limitations and Future Work

  • Static Setting: The current protocol is "static," meaning once the files are entangled, they cannot be easily updated, added, or deleted without re-computing the entire clew. The authors highlight "fully dynamic" entangled storage as a major open problem.
  • Coordination Overhead: Clients must coordinate and run an expensive procedure to build the initial entanglement. This makes the system more suitable for specific groups (like a consortium of banks or researchers) rather than the general public.
  • Computational Cost: While communication is optimized, the server's computational load for homomorphic evaluation of high-degree polynomials remains a practical hurdle for very large numbers of users.

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},
}

Loading related content...

Figure