Paper 2012/631

Message-Locked Encryption and Secure Deduplication

Mihir Bellare, Sriram Keelveedhi, and Thomas Ristenpart


We formalize a new cryptographic primitive, Message-Locked Encryption (MLE), where the key under which encryption and decryption are performed is itself derived from the message. MLE provides a way to achieve secure deduplication (space-efficient secure outsourced storage), a goal currently targeted by numerous cloud-storage providers. We provide definitions both for privacy and for a form of integrity that we call tag consistency. Based on this foundation, we make both practical and theoretical contributions. On the practical side, we provide ROM security analyses of a natural family of MLE schemes that includes deployed schemes. On the theoretical side the challenge is standard model solutions, and we make connections with deterministic encryption, hash functions secure on correlated inputs and the sample-then-extract paradigm to deliver schemes under different assumptions and for different classes of message sources. Our work shows that MLE is a primitive of both practical and theoretical interest.

Available format(s)
Publication info
Published elsewhere. A preliminary version appears on EUROCRYPT 2013. This is the full version.
Convergent encryptiondeduplicationdeterministic encryption
Contact author(s)
sriramkr @ cs ucsd edu
2013-03-11: last of 2 revisions
2012-11-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Sriram Keelveedhi and Thomas Ristenpart},
      title = {Message-Locked Encryption and Secure Deduplication},
      howpublished = {Cryptology ePrint Archive, Paper 2012/631},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.