A multi-tenant storage system can store clear text data and associated clear text checksum received from a storage tenant using their associated cryptographic key (“cryptokey”). When the clear text data is compressible, cryptographic data (“cryptodata”) is generated from a concatenation of the clear text checksum and compressed clear text data using the cryptokey. A cryptographic checksum (“cryptochecksum”) is generated from the cryptodata. When the clear text data is uncompressible, cryptographic data (“cryptodata”) is generated by encrypting the clear text data using the cryptokey with an extra verification step to make sure the clear text checksum can be rebuilt during the read request. A cryptographic checksum (“cryptochecksum”) is generated from the cryptodata. The cryptodata and associated cryptochecksum are stored in the multi-tenant storage system, so that repairs to damaged cryptodata can be made using the associated cryptochecksum.