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

• US 10,348,486 B2
• Filed: 09/30/2014
• Issued: 07/09/2019
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Karame, Ghassan
• Primary Examiner(s): Zarrineh, Shahriar
• Application Number:
  US15/514,851
• Publication Number:
  US 20170237552A1
• Time in Patent Office: 1,743 Days
• Field of Search: 380 28
• CPC Class Codes: G06F 17/142 Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

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.

Claims

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).