A method for secure cloud storage of user data includes deriving, using content of the user data and a secret key stored by a server, an encryption key, encrypting, using the derived encryption key, the user data to provide encrypted user data, applying an all-or-nothing transform on the encrypted user data to produce blocks of transformed encrypted user data, partitioning the blocks of transformed encrypted user data to data partitions, creating, for each of the data partitions, an authenticator, and performing data deduplication on the transformed encrypted user data.