A method for at least partially updating encrypted data stored on one or more servers includes dividing the encrypted data into equal sized chunks; encrypting each chunk using an all-or-nothing encryption scheme (AONE) with an encryption key, wherein an additional randomness per chunk is embedded into the AONE; outputting a plurality of ciphertext blocks for each chunk; storing the encrypted chunks on the one or more servers such that an i-th ciphertext block of each encrypted chunk is stored on an i-th server, wherein a result of a predetermined function performed on the randomness for all encrypted chunks is stored with each encrypted chunk; determining one or more chunks to update; reverting the predetermined function by accessing all the encrypted chunks; decrypting the one or more chunks to update based on the result of, updating the decrypted chunks; re-encrypting the updated decrypted chunks, and storing the re-encrypted chunks.