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_9: A practical digital signature system based on a conventional encryption function which is as secure as the conventional encryption function is described. Since certified conventional systems are available it can be implemented quickly, without the several years delay required for certification of an untested system.
@cite_40: We study the problem of authenticated storage, where we wish to construct protocols that allow to outsource any complex file system to an untrusted server and yet ensure the file-system's integrity. We introduce Athos, a new, platform-independent and user-transparent architecture for authenticated outsourced storage. Using light-weight cryptographic primitives and efficient data-structuring techniques, we design authentication schemes that allow a client to efficiently verify that the file system is fully consistent with the exact history of updates and queries requested by the client. In Athos, file-system operations are verified in time that is logarithmic in the size of the file system using optimal storage complexity--constant storage overhead at the client and asymptotically no extra overhead at the server. We provide a prototype implementation of Athos validating its performance and its authentication capabilities.
@cite_13: Outsourced storage has become more and more practical in recent years. Users can now store large amounts of data in multiple servers at a relatively low price. An important issue for outsourced storage systems is to design an efficient scheme to assure users that their data stored at remote servers has not been tampered with. This paper presents a general method and a practical prototype application for verifying the integrity of files in an untrusted network storage service. The verification process is managed by an application running in a trusted environment (typically on the client) that stores just one cryptographic hash value of constant size, corresponding to the "digest" of an authenticated data structure. The proposed integrity verification service can work with any storage service since it is transparent to the storage technology used. Experimental results show that our integrity verification method is efficient and practical for network storage systems.
@cite_6: An efficient and practical method for dynamically maintaining an authenticated dictionary uses a skip list data structure and communicative hash functions to provide a dictionary database (201) that stores information objects so that any individual object can be authenticated as belonging or not belonging to the dictionary. The authentication consists of a short sequence of vales that begin with an element and a sequence of values that, when hashed in order using a cryptographic associative hash function, create the same value as the hashed digest of the entire dictionary. Rather than hashing up a dynamic 2-3 tree, hashes are created in a skip list. Validation of the result of the authenticating step is provided if the hash of the short sequence matches a signed hash of the entire skip list.
Many more works exist in the field of cloud storage security. Most of them, however, have a different focus and are orthogonal to our work. Athos @cite_40 , e.g., is a solution for outsourcing file systems that achieves integrity in a way that file system operations are possible with logarithmic communication costs. The solution is orthogonal to our work in the sense that this requirement is w.r.t. the total number of files directories in the file system and not w.r.t. the size of single file contents. A similar goal is pursued by @cite_13 . Both works are based on authenticated skip lists, an authenticated data structure (ADS) initially proposed by @cite_6 , while our work is based on another ADS---the Merkle tree @cite_9 .