We present sec-cs, a hash-table-like data structure for contents on untrusted storage that is provably secure and storage-efficient. We achieve authenticity and confidentiality with zero storage overhead using deterministic authenticated encryption. State-of-the-art data deduplication approaches prevent redundant storage of shared parts of different contents irrespective of whether relationships between contents are known a priori.,,,,Instead of just adapting existing approaches, we introduce novel (multi-level) chunking strategies, ML-SC and ML-CDC, which are significantly more storage-efficient than existing approaches in presence of high redundancy.,,,,We prove sec-cs's security, publish an implementation, and present evaluation results indicating suitability for, e.g., future backup systems that should preserve many versions of files on little available storage.
@cite_3: Many objects, such as files, electronic messages, and web pages, contain overlapping content. Numerous past research projects have observed that one can compress one object relative to another one by computing the differences between the two, but these delta-encoding systems have almost invariably required knowledge of a specific relationship between them—most commonly, two versions using the same name at different points in time. We consider cases in which this relationship is determined dynamically, by efficiently determining when a sufficient resemblance exists between two objects in a relatively large collection. We look at specific examples of this technique, namely web pages, email, and files in a file system, and evaluate the potential data reduction and the factors that influence this reduction. We find that delta-encoding using this resemblance detection technique can improve on simple compression by up to a factor of two, depending on workload, and that a small fraction of objects can potentially account for a large portion of these savings.
A comparison of advantages of the different schemes is shown in Tab. : Delta-based approaches are clearly able to yield lowest storage costs for changed contents in principle, but they have important limitations in practice: First, their efficiency depends on a priori knowledge of relations between chunks---a problem tackled by, e.g., the DERD framework @cite_3 . Second, they substantially increase retrieval costs as reconstruction of delta-encoded chunks requires retrieval of corresponding base chunks of which only parts are actually required. Chunking-based schemes achieve savings when storing changed contents (data) irrespective of knowledge about relations (their best values are highlighted in green in the table). The most efficient strategies CDC ASC yield their savings depending on the distribution of contents specific file formats.