UP-MLE: Efficient and Practical Updatable Block-Level Message-Locked Encryption Scheme Based on Update Properties

Deduplication is widely used to improve space efficiency in cloud storage. The Updatable block-level Message-Locked Encryption (UMLE) has been proposed to achieve efficient block-level updates for a deduplication system. However, the update design of the current UMLE instantiation adopts a static structure, which does not fit in with real update scenarios. This paper analyzes the File System and Storage Lab (FSL) Homes datasets that are widely used in deduplication research and reveals two interesting properties: i) Updated blocks are more likely to be updated again; ii) Updated blocks are always clustered in files. Based on these properties, we propose and implement an efficient and practical UMLE scheme. Experiments on real-world datasets show that our update algorithm is 24.85% more efficient than its foremost counterpart, increasing the space overhead by <= 0.39%.