This paper addresses the problem of data retrievability in cloud computing systems performing deduplication to optimize
their space savings: While there exist a number of proof of retrievability (PoR) solutions that guarantee storage correctness
with cryptographic means, these solutions unfortunately come at odds with the deduplication technology.
To reconcile proofs of retrievability with le-based crossuser deduplication, we propose the message-locked PoR approach
whereby the PoR effect on duplicate data is identical and depends on the value of the data segment, only. As a proof of concept, we describe two instantiations of existing PoRs and show that the main extension is performed during the setup phase whereby both the keying material and the encoded version of the to-be-outsourced file is computed based on the file itself. We additionally propose a new server-aided message-locked key generation technique that compared with related work offers better security guarantees.