Accession Number:

ADA461823

Title:

Towards a Theory of Data Entanglement

Descriptive Note:

Technical rept.

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Report Date:

2004-03-26

Pagination or Media Count:

30.0

Abstract:

We propose a formal model for data entanglement as used in storage systems like Dagster 25 and Tangler 26. These systems split data into blocks in such a way that a single block becomes a part of several documents these documents are said to be entangled. Dagster and Tangler use entanglement in conjunction with other techniques to deter a censor from tampering with unpopular data. In this paper, we assume that entanglement is a goal in itself. We measure the strength of a system by how thoroughly documents are entangled with one another and how attempting to remove a document affects the other documents in the system. We argue that while Dagster and Tangler achieve their stated goals, they do not achieve ours. In particular, we prove that deleting a typical document in Dagster affects, on average, only a constant number of other documents in Tangler, it affects virtually no other documents. This motivates us to propose two stronger notions of entanglement, called dependency and all-or-nothing integrity. All-or-nothing integrity binds the users data so that it is hard to delete or modify the data of any one user without damaging the data of all users. We study these notions in six submodels, differentiated by the choice of users recovery algorithms and restrictions placed on the adversary. In each of these models, we not only provide mechanisms for limiting the damage done by the adversary, but also argue, under reasonable cryptographic assumptions, that no stronger mechanisms are possible.

Subject Categories:

  • Computer Hardware
  • Computer Systems Management and Standards
  • Information Science

Distribution Statement:

APPROVED FOR PUBLIC RELEASE