Systems and methods for performing data deduplication one storage blocks while the data is encrypted. An example method may comprise: selecting a first storage block and a second storage block from a plurality of encrypted storage blocks, wherein the first storage block and the second storage block are encrypted using different cryptographic input; causing the first storage block and the second storage block to be decrypted and further encrypted using a common cryptographic input; determining that a cipher text of the first storage block and a cipher text of the second storage block are the same; and updating a reference to the first storage block to reference the second storage block in response to the determining that the cipher text of the first storage block and the cipher text of the second storage block are the same.