Paper 2018/422

Message-locked Encryption with File Update

Suyash Kandele and Souradyuti Paul


Message-locked encryption (MLE) (formalized by Bellare, Keelveedhi and Ristenpart, 2013) is an important cryptographic primitive that supports deduplication in the cloud. Updatable block-level message-locked encryption (UMLE) (formalized by Zhao and Chow, 2017) adds the update functionality to the MLE. In this paper, we formalize and extensively study a new cryptographic primitive file-updatable message-locked encryption (FMLE). FMLE can be viewed as a generalization of the UMLE, in the sense that unlike the latter, the former does not require the existence of BL-MLE (block-level message-locked encryption). FMLE allows more flexibility and efficient methods for updating the ciphertext and tag. Our second contribution is the design of two efficient FMLE constructions, namely, RevD-1 and RevD-2, whose design principles are inspired from the very unique reverse decryption functionality of the FP hash function (designed by Paul, Homsirikamol and Gaj, 2012) and the APE authenticated encryption (designed by Andreeva et al., 2014). With respect to UMLE – which provides so far the most efficient update function – RevD-1 and RevD-2 reduce the total update time by at least 50%, on average. Additionally, our constructions are storage efficient. We also give extensive comparison between our and the existing constructions.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.Applied Cryptography and Network Security (ACNS) 2018
Message-locked encryptionsymmetric key cryptographyhash mode of operation
Contact author(s)
suyashk @ iitbhilai ac in
2018-05-10: received
Short URL
Creative Commons Attribution


      author = {Suyash Kandele and Souradyuti Paul},
      title = {Message-locked Encryption with File Update},
      howpublished = {Cryptology ePrint Archive, Paper 2018/422},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.