A mechanism is provided which allows to de-duplicate encrypted data such that the de-duplication ratio for encrypted data is similar to the de-duplication ration of the corresponding un-encrypted data and the purpose of encryption is not obfuscated, i.e. only the originator of the data (the client) can decrypt—and hence read—the data. This is achieved by interwoven the de-duplication algorithm with the encryption algorithm in a way that the data are encrypted with a key that is generated from the unencrypted data. Afterwards, that key is itself encrypted with an encryption key being private to a particular client. Due to the fact that the private key is not effecting the encrypted data stream, it can still be de-duplicated efficiently.