In this thesis we study in depth the problem of verifiability in cloud storage systems. We study Proofs of Storage -a family of cryptographic protocols that enable a cloud storage provider to prove to a user that the integrity of her data has not been compromised- and we identify their limitations with respect to two key characteristics of cloud storage systems, namely, reliable data storage with automatic maintenance and data deduplication. To cope with the first characteristic, we introduce the notion of Proofs of Data Reliability, a comprehensive verification scheme that aims to resolve the conflict between reliable data storage verification and automatic maintenance.
We further propose two Proofs of Data Reliability schemes, namely POROS and PORTOS, that succeed in verifying reliable data storage and, at the same time, enable the cloud storage provider to autonomously perform automatic maintenance operations. As regards to the second characteristic, we address the conflict between Proofs of Storage and deduplication.
More precisely, inspired by previous attempts in solving the problem of deduplicating encrypted data, we propose message-locked PoR, a solution that combines Proofs of Storage with deduplication. In addition, we propose a novel message-locked key generation protocol which is more resilient against off-line dictionary attacks compared to existing solutions.
