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_18: Version control systems are widely used in software development and document management. Unfortunately, versioning confidential files is not normally supported: Existing solutions encrypt the transport channel, but store data in plaintext within a repository. We come up with an access control solution that allows secure versioning of confidential files even in the presence of a malicious server administrator. Using convergent encryption as a building block, we enable space-efficient storage of version histories despite secure encryption. We describe an implementation of our concept for the Subversion (SVN) system, and evaluate storage efficiency and runtime of this implementation. Our implementation is compatible with existing SVN versions without requiring changes to the storage backend.
@cite_41: The Farsite distributed file system provides availability by replicating each file onto multiple desktop computers. Since this replication consumes significant storage space, it is important to reclaim used space where possible. Measurement of over 500 desktop file systems shows that nearly half of all consumed space is occupied by duplicate files. We present a mechanism to reclaim space from this incidental duplication to make it available for controlled file replication. Our mechanism includes: (1) convergent encryption, which enables duplicate files to be coalesced into the space of a single file, even if the files are encrypted with different users' keys; and (2) SALAD, a Self-Arranging Lossy Associative Database for aggregating file content and location information in a decentralized, scalable, fault-tolerant manner. Large-scale simulation experiments show that the duplicate-file coalescing system is scalable, highly effective, and fault-tolerant.
@cite_1: As the world moves to digital storage for archival purposes, there is an increasing demand for systems that can provide secure data storage in a cost-effective manner. By identifying common chunks of data both within and between files and storing them only once, deduplication can yield cost savings by increasing the utility of a given amount of storage. Unfortunately, deduplication exploits identical content, while encryption attempts to make all content appear random; the same content encrypted with two different keys results in very different ciphertext. Thus, combining the space efficiency of deduplication with the secrecy aspects of encryption is problematic. We have developed a solution that provides both data security and space efficiency in single-server storage and distributed storage systems. Encryption keys are generated in a consistent manner from the chunk data; thus, identical chunks will always encrypt to the same ciphertext. Furthermore, the keys cannot be deduced from the encrypted chunk data. Since the information each user needs to access and decrypt the chunks that make up a file is encrypted using a key known only to the user, even a full compromise of the system cannot reveal which chunks are used by which users.
@cite_32: 
@cite_16: Cumulus is a system for efficiently implementing filesystem backups over the Internet, specifically designed under a thin cloud assumption—that the remote datacenter storing the backups does not provide any special backup services, but only a least-common-denominator storage interface. Cumulus aggregates data from small files for storage and uses LFS-inspired segment cleaning to maintain storage efficiency. While Cumulus can use virtually any storage service, we show its efficiency is comparable to integrated approaches.
@cite_25: 
To allow efficient usage of cloud storage for, e.g., backups, more specialized tools are required. Common backup tools like duplicity @cite_32 rely on backups, i.e., they store differences to previous backups. This can be used in combination with GnuPG to preserve snapshots in a storage-efficient and secure manner, but causes communication overhead when specific versions are read. VCS could be used for delta-based backups to a limited extent, but they are typically inefficient w.r.t. large files and have limited security properties: Git @cite_25 only ensures integrity authenticity of the version history by integrating signatures. SVN does not, but an extension @cite_18 adds storage-efficient file-level encryption. Cumulus @cite_16 is a backup system that supports large files and allows direct access to arbitrary snapshots, but it is less storage-efficient as it only deduplicates identical data between different versions of individual files. Farsite @cite_41 , in contrast, is a distributed file system targeting on chunking-based backups that deduplicates different identical files despite secure encryption. It cannot save space for snapshots of different versions of a file, though, as it relies on WFC. @cite_1 extend Farsite's concept to CDC, but they do not provide any explicit authenticity guarantees.