Counter-based encryption of stored data blocks

• US 8,635,465 B1
• Filed: 03/28/2012
• Issued: 01/21/2014
• Est. Priority Date: 03/28/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Juels, Ari, Oprea, Alina M.
• Primary Examiner(s): ZECHER, CORDELIA P K
• Application Number:
  US13/432,577
• Time in Patent Office: 664 Days
• Field of Search: None
• US Class Current: 713/193
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

A processing device is configured to maintain counters for respective stored data blocks, and to encrypt a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter. The encryption may comprise a homomorphic encryption operation performed on the given data block as a function of the value of that data block and the value of its associated counter, with the homomorphic encryption operation comprising an operation such as addition or multiplication performed over a designated field. A given one of the counters is incremented each time the corresponding data block is subject to an update operation. The data block can be encrypted, for example, by combining a value of that data block with an additional value determined using the associated counter value, such as a one-time pad value determined as a function of the counter value.

Claims

1. A method comprising the steps of:

maintaining counters for respective stored data blocks; and

encrypting a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter;

wherein the maintaining and encrypting steps are performed by a processing device having a processor coupled to a memory; and

wherein the encrypting step comprises performing a homomorphic encryption operation on the given data block as a function of the value of that data block and the value of its associated counter.

2. The method of claim 1 wherein the homomorphic encryption operation is performed over a designated field.

3. The method of claim 1 wherein the data blocks have respective values m₁, . . . m_n arranged in an array of n values and the corresponding counters maintained for those data blocks have respective values c₁, . . . c_n.

4. The method of claim 1 wherein the data blocks have respective values m_ij arranged in a two-dimensional n-by-r array of values, 1≦

i≦

n and 1≦

j≦

r, and the corresponding counters maintained for those data blocks have respective values c_ij.

5. The method of claim 1 further comprising the step of utilizing at least a subset of the counters to provide integrity protection for respective ones of the stored data blocks.

6. The method of claim 5 wherein the utilizing step further comprises:

storing a message authentication code for a given one of the data blocks, wherein the message authentication code is computed over at least data block value m_i and corresponding counter value c_i using a secret key; and

authenticating the data block using the stored message authentication code.

7. The method of claim 6 wherein the secret key is a secret key of a cloud tenant on whose behalf the data blocks are stored in cloud infrastructure of a cloud service provider.

8. The method of claim 6 wherein message authentication codes computed for multiple respective stored data blocks are combined into a composite message authentication code.

9. A computer program product comprising a non-transitory processor-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by the processing device cause the processing device to perform the steps of the method of claim 1.

10. A method comprising the steps of:

maintaining counters for respective stored data blocks; and

encrypting a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter;

wherein the maintaining and encrypting steps are performed by a processing device having a processor coupled to a memory; and

wherein a given one of the counters is incremented each time the corresponding data block is subject to an update operation.

11. A method comprising the steps of:

maintaining counters for respective stored data blocks; and

encrypting a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter;

wherein the maintaining and encrypting steps are performed by a processing device having a processor coupled to a memory;

wherein the data blocks have respective values m₁, . . . m_n arranged in an array of n values and the corresponding counters maintained for those data blocks have respective values c₁, . . . c_n; and

wherein the encrypting step comprises encrypting an i-th one of the data blocks by combining the data block value m_i with an additional value determined as a function of the counter value c_i.

12. The method of claim 11 wherein the additional value comprises a one-time pad value determined as a function of the counter value c_i.

13. The method of claim 11 wherein the additional value is a pseudo-random function of the counter value c_i, such that the corresponding encrypted data block is computed in accordance with the following equation:

e_i=m_i+PRF_k(i,c_i),

where e_i denotes the encrypted data block, PRF_k denotes a pseudo-random function over a symmetric key k, and the addition operation is performed over a designated field.

14. The method of claim 13 wherein the encrypting step comprises encrypting each of the n data block values and wherein the method further comprises transmitting information characterizing the encrypted data block values and the counter values c₁, . . . c_n to a receiver such that the receiver can decrypt the encrypted data block values by removal of the additional values computed using the respective counter values.

15. The method of claim 13 wherein the encrypting step comprises encrypting each of the n data block values and wherein the method further comprises transmitting information characterizing the encrypted data block values to a receiver that independently tracks the counter values c₁, . . . c_n such that the receiver can decrypt the encrypted data block values by removal of the additional values computed using the respective counter values.

16. A method comprising the steps of:

maintaining counters for respective stored data blocks; and

encrypting a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter;

wherein the maintaining and encrypting steps are performed by a processing device having a processor coupled to a memory;

wherein the data blocks have respective values m_ij arranged in a two-dimensional n-by-r array of values, 1≦

i≦

n and 1≦

j≦

r, and the corresponding counters maintained for those data blocks have respective values c_ij; and

wherein the encrypting step comprises encrypting an i,j-th one of the data blocks by combining the data block value m_ij with an additional value determined as a function of the counter value c_ij.

17. The method of claim 16 wherein the additional value comprises a one-time pad value determined as a function of the counter value c_ij.

18. The method of claim 16 wherein the additional value is a pseudo-random function of the counter value c_ij, such that the corresponding encrypted data block is computed in accordance with the following equation:

e_ij=m_ij+PRF_k(i,j,c_ij),

where e_ij denotes the encrypted data block, PRF_k denotes a pseudo-random function over a symmetric key k, and the addition operation is performed over a designated field.

19. An apparatus comprising:

a processing device comprising a processor coupled to a memory;

wherein the processing device is configured to maintain counters for respective stored data blocks, and to perform a homomorphic encryption operation on a given one of the data blocks utilizing a value of the data block in combination with a value of its associated counter.

20. The apparatus of claim 19 wherein the processing device is implemented in cloud infrastructure of a cloud service provider.

21. An information processing system comprising a processing platform which incorporates the apparatus of claim 19.