Method and system for at least partially updating data encrypted with an all-or-nothing encryption scheme

1. A method for at least partially updating encrypted data stored on one or more servers, the encrypted data being encrypted with an all-or-nothing encryption (AONE) scheme, the method comprising:

a) dividing the encrypted data, which includes a first number m of plaintext blocks, into a second number N of equal sized chunks, wherein the second number is based on a number of the one or more servers on which the encrypted data is to be stored, and wherein each chunk includes m/N plaintext blocks,

b) encrypting each chunk using the AONE, wherein an additional randomness is embedded into the AONE by an initialization vector derived from the randomness being used as an initial seed for an AONE initialization vector of the AONE, and outputting a plurality of ciphertext blocks for each chunk,

c) storing the encrypted chunks in memory on the one or more servers, wherein storing the encrypted chunks comprises storing an i-th ciphertext block of each encrypted chunk on an i-th server, and wherein the randomness is encrypted using an XOR-combination of XOR operations performed on the ciphertext blocks for each chunk,

d) determining one or more parts of one or more chunks to update,

e) decrypting the randomness by accessing all the encrypted chunks to compute the XOR-combination,

f) decrypting the one or more chunks to update based on the result of e),

g) updating the decrypted chunks,

h) re-encrypting the updated decrypted chunks using the AONE, and

i) storing the re-encrypted chunks according to step c).

2. The method according to claim 1 , wherein an initialization vector for an (i+1)-th chunk is determined by performing a hash-function on an initialization vector for an i-th chunk, and wherein an initialization vector for a first chunk is determined by calculating the hash-function on the randomness.

3. The method according to claim 1 , wherein the encrypted randomness is stored on all of the one or more servers.

4. The method according to claim 1 , wherein a Fast-Fourier-Transform All-Or-Nothing transform—(FFT-AONT)—is applied prior or after the encrypting each chunk using the AONE.

5. The method according to claim 4 , wherein the one or more chunks to update include all data encrypted with the AONE stored on the one or more servers.

6. A system for at least partially updating encrypted data stored on one or more servers, the encrypted data being encrypted with an all-or-nothing encryption (AONE) scheme, the system comprising:

an updating entity including memory and one or more processors which are programmed to execute a method comprising:

a) dividing the encrypted data, which includes a first number m of plaintext blocks, into a second number N of equal sized chunks, wherein the second number is based on a number of the one or more servers on which the encrypted data is to be stored, and wherein each chunk includes m/N plaintext blocks,

b) encrypting each chunk using the AONE, wherein an additional randomness is embedded into the AONE by an initialization vector derived from the randomness being used as an initial seed for an AONE initialization vector of the AONE, and outputting a plurality of ciphertext blocks for each chunk,

c) storing the encrypted chunks on the one or more servers, wherein the updating entity is further configured to store an i-th ciphertext block of each encrypted chunk on an i-th server, and wherein the randomness is encrypted using an XOR-combination of XOR operations performed on the ciphertext blocks for each chunk,

d) determining one or more parts of one or more chunks to update,

e) decrypting the randomness by accessing all the encrypted chunks to compute the XOR-combination,

f) decrypting the one or more chunks to update based on the result of e),

g) updating the decrypted chunks,

h) re-encrypting the updated decrypted chunks using the AONE, and

i) storing the re-encrypted chunks according to step c).