Message-Locked Encryption for Lock-Dependent Messages
Authors: M. Abadi, D. Boneh, I. Mironov, A. Raghunathan, and G. Segev
Abstract:
Motivated by the challenging problem of avoiding duplication in storage systems, Bellare, Keelveedhi, and Ristenpart (EUROCRYPT '13) have recently put forward the notion of Message-Locked Encryption (MLE) schemes which subsumes convergent encryption and its variants. Such schemes do not rely on permanent secret keys, but rather encrypt messages using keys that are derived from the messages themselves. Bellare et al. defined and realized strong notions of
security for MLE schemes within an adversarial model in which messages are unpredictable and chosen independently of the public parameters of the scheme.
Addressing the fact that in many realistic scenarios adversaries would take the public parameters into account when attacking a scheme, we strengthen the notions of security proposed by Bellare et al. and extend their framework to consider plaintext distributions that may depend on the public parameters. We refer to such inputs as lock-dependent messages. We construct two schemes that satisfy our new notions of security for message-locked encryption with lock-dependent messages.
Our main construction deviates from the approach of Bellare et al. by avoiding the usage of any ciphertext components that are derived deterministically from the messages. We design a fully randomized scheme that supports an equality-testing algorithm defined on the ciphertexts. This functionality enables us to satisfy a most stringent notion of security for MLE, allowing the adversary to specify the distribution of the plaintexts adaptively, with no further restrictions on the distribution other than its unpredictability.
Our second construction shows that even when having a deterministic ciphertext component (that enables more efficient equality testing), it is possible to guarantee security for lock-dependent messages by limiting the computational capabilities of the message distributions issued by the attacker. This model is inspired by the recent work of Raghunathan, Segev, and Vadhan (EUROCRYPT '13) who proposed a similar approach in the setting of deterministic public-key encryption.
In both of our schemes the overhead in the length of the ciphertext is only additive and independent of the message length, as desirable in storage systems.
Reference:
In Proceedings of Crypto 2013, pp. 374-391.
[BIBTEX]
Full paper: PDF