James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, and Sheng Zhong. Towards a theory of data entanglement. Theoretical Computer Science 389(1–2):26–43, December 2007. An earlier version appeared in Ninth European Symposium on Research in Computer Security, Lecture Notes in Computer Science 3192, Springer-Verlag, September 2004, pp. 177–192.
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users' data in a way that makes it hard to corrupt the data of any one user without corrupting the data of all users. AONI can be a useful defense against negligent or dishonest storage providers who might otherwise be tempted to discard documents belonging to users without much clout. We show that, if all users use a fixed standard recovery algorithm, we can implement AONI using a MAC, but, if some of the users adopt instead a non-standard recovery algorithm provided by the dishonest storage provider, AONI can no longer be achieved. However, even for the latter scenario, we describe a simple entangling mechanism that provides AONI for a restricted class of destructive adversaries.
@article(AspnesFYZ2007,
title="Towards a theory of data entanglement",
author="James Aspnes and Joan Feigenbaum and Aleksandr Yampolskiy and Sheng Zhong",
journal="Theoretical Computer Science",
volume=389,
number={1--2},
month=dec,
year=2007,
)