Concealing access patterns to electronic data storage for privacy

• US 9,015,853 B2
• Filed: 06/17/2013
• Issued: 04/21/2015
• Est. Priority Date: 06/15/2012
• Status: Expired due to Fees

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Stefanov, Emil, Shi, Elaine, Song, Dawn
• Primary Examiner(s): Zecher, Dede
• Assistant Examiner(s): LAKHIA, VIRAL S
• Application Number:
  US13/919,621
• Publication Number:
  US 20140007250A1
• Time in Patent Office: 673 Days
• Field of Search: 726 24- 26, 726/36, 713181-189, 713/170, 707/769
• US Class Current: 726/26
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2123 Dummy operation

Abstract

Methods and systems of concealing access patterns to data storage, such as within servers of a cloud computing environment are presented. Server data storage is securely partitioned into smaller electronic data storage partitions of predetermined size. The client side maintains a shuffling buffer and position map for these blocks as stored on the electronic data storage partitions of the server. Concealment is performed with respect to accesses from the client to server using an oblivious sorting protocol. Access operation is concealed with each block being randomly assigned to any of the data storage partitions, and whenever a block is accessed, the block is logically removed from its current partition and logically assigned to a fresh random partition selected from all partitions, while the client maintains tracking of which partition each block is associated with at any point of time.

Claims

1. A method of concealing access patterns to electronic data storage, the method comprising:

(a) within at least one server device configured for providing data storage services to at least one client, securely partitioning electronic data storage having N data blocks, each data block having a size of B bytes;

(b) wherein said electronic data storage is partitioned within a partitioning framework into a plurality of P smaller electronic data storage partitions having a size of N/P, and in which P is equal to √

N data blocks;

(c) performing electronic data storage access concealment, in which each block is randomly assigned to any of the P partitions, and whenever a data block is accessed during data accesses for reading a data block or writing a data block by the client, the data block is logically removed from its current partition and logically assigned to a fresh random partition selected from all P partitions, with the client tracking which partition each block is associated with at any point of time; and

(d) encrypting data by the client when data blocks are stored on the server;

(e) wherein the client repeatedly sorts and shuffles subsets of said data blocks in each partition during data accesses.

2. The method recited in claim 1, wherein performing electronic data storage access concealment comprises:

downloading and decrypting data blocks from said data blocks that are to be shuffled;

shuffling said data blocks locally; and

encrypting said data blocks and uploading them back to the server.

3. The method recited in claim 1, wherein performing electronic data storage access concealment comprises performing any desired oblivious sorting or shuffling process on said data blocks to be shuffled without downloading them all at any one time.

4. The method recited in claim 1, wherein said electronic data storage comprises random access memory (RAM), hard disk drives (HDD), or any combination thereof.

5. The method recited in claim 1, further comprising the client maintaining P slots as a data cache for temporarily storing data blocks fetched from the server, and maintaining a position map to track which partition or cache slot in which each data block resides.

6. The method recited in claim 5, further comprising storing metadata in said position map with state information about the data blocks.

7. The method recited in claim 1, wherein server side determination of which data blocks are being accessed, how old data blocks were when last accessed, whether identical data blocks are accessed, determination of data block access patterns, and whether each data block access is a read or a write, is prevented.

8. The method recited in claim 1, further comprising storing data blocks temporarily in a cache on the client and later writing them to the server in a different order within an eviction process.

9. The method recited in claim 8, wherein said eviction process is performed at a fixed rate or an adjustable rate.

10. The method recited in claim 8:

wherein said eviction process comprises both foreground and background eviction; and

wherein foreground evictions are performed along with each data access whereas background evictions are performed in a separate background thread during regular data block access operations.

11. The method recited in claim 8, wherein said eviction process evicts dummy blocks when there are no real data blocks to evict.

12. The method recited in claim 1:

wherein each said partition has a plurality of levels between a bottom level and a top level; and

wherein said shuffling is simultaneously performed on multiple partition levels together such that all consecutively filled levels from the bottom level upwards in said partition are shuffled into a first unfilled level;

or if all levels are filled, then all levels are shuffled into the top level while removing duplicates during shuffling to ensure shuffled data can fit in the top level of said partition.

13. The method recited in claim 1, further comprising compressing data blocks during shuffling.

14. The method recited in claim 13, further comprising compressing dummy blocks together with data blocks containing real blocks of data.

15. The method recited in claim 1, further comprising recursively applying said method of concealing access patterns to electronic data storage on the client memory resulting in different levels of partitioning.

16. The method recited in claim 1:

wherein said method of concealing access patterns to electronic data storage comprises an O-RAM process; and

further comprising recursively applying said O-RAM process to client data of any O-RAM process.

17. The method recited in claim 1, wherein said shuffling is performed on multiple partitions concurrently.

18. The method recited in claim 1, wherein scheduling of operations between client and server is indistinguishable from a pattern of said data block accesses.

19. The method recited in claim 1, wherein said storage services comprise cloud storage services.

20. A method of concealing access patterns to electronic data storage, the method comprising:

(a) within at least one server device configured for providing storage services to at least one client, securely partitioning a electronic data storage having N data blocks, each having a size of B bytes;

(b) wherein said electronic data storage is partitioned within a partitioning framework into a plurality of P smaller electronic data storage partitions having a size of N/P, and in which P is equal to √

N data blocks; and

(c) performing electronic data storage access concealment, in which each block is randomly assigned to any of the P partitions, and whenever a data block is accessed during data accesses for reading a data block or writing a data block by the client, the data block is logically removed from its current partition and logically assigned to a fresh random partition selected from all P partitions, with the client tracking which partition each block is associated with at any point of time;

(d) wherein said electronic data storage access concealment performs downloading and decrypting data blocks from data blocks that are to be shuffled, shuffling said data blocks locally, then finally encrypting said data blocks and uploading them back to the server; and

(e) wherein the client repeatedly sorts and shuffles subsets of said data blocks in each partition during data accesses.

21. A system for concealing access patterns to electronic data storage, the system comprising:

(a) at least one server configured for servicing at least one client with data storage services;

(b) at least one client configured for accessing said server for performing write and read accesses of data blocks from said server;

(c) wherein said server and said client are configured with a computer for executing programming for carrying out steps of access concealment, comprising;

(i) securely partitioning electronic data storage in said at least one server to have N data blocks having a size of B bytes;

(ii) wherein said electronic data storage is partitioned within a partitioning framework into a plurality of P smaller electronic data storage partitions having a size of N/P, and in which P is equal to equal to √

N data blocks;

(iii) performing electronic data storage access concealment, in which each block is randomly assigned to any of the P partitions, and whenever a data block is accessed during data accesses for reading a data block or writing a data block by said client, the data block is logically removed from its current partition and logically assigned to a fresh random partition selected from all P partitions, with the client tracking which partition each block is associated with at any point of time; and

(iv) encrypting data by the client when data blocks are stored on the server;

(v) wherein the client repeatedly sorts and shuffles subsets of said data blocks in each partition during data accesses.