Towards efficient fully randomized message-locked encryption

Cross-user data deduplication will greatly reduce the storage cost of storage service provider. Motivated by secure data deduplication, Abadi et al. extended the work Message-Locked Encryption (MLE) and introduced the primitive of MLE2 with nice security properties. However, their fully randomized scheme (R-MLE2) requires the inefficient equality-testing algorithm to identify all duplicate ciphertexts. Thus, an interesting open problem is how to reduce the overhead of R-MLE2 and propose an efficient construction for R-MLE2. In this paper, we introduce a new primitive called μR-MLE2, which gives a partial positive answer to this open problem. Our main trick is to use the client-assistant way based on static or dynamic decision trees. The advantage gained from it is that by interacting with clients, the server will reduce the time complexity of deduplication equality test from linear time to efficient logarithmic time over the whole database items.