Database outsourcing with access privacy

• US 8,458,451 B2
• Filed: 01/20/2009
• Issued: 06/04/2013
• Est. Priority Date: 01/20/2009
• Status: Active Grant

• Current Assignee: New York University, The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: New York University
• Inventors: Shasha, Dennis, Williams, Peter, Sion, Radu
• Primary Examiner(s): PEARSON, DAVID J
• Application Number:
  US12/321,326
• Publication Number:
  US 20100185847A1
• Time in Patent Office: 1,596 Days
• Field of Search: None
• US Class Current: 713/150
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 21/54 by adding security routines or objects to programs
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies
• CPC Class Codes: G06F 2221/2101 Auditing as a secondary aspect
• CPC Class Codes: G06F 2221/2151 Time stamp
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06

Abstract

This invention introduces a new paradigm for outsourcing the transaction processing backend of a multi-client database application to an untrusted service provider. Specifically, the invention enables untrusted service providers to support transaction serialization, backup and recovery for clients, with full data confidentiality and correctness. Moreover, providers learn nothing about transactions (except their size and timing), thus achieving read and write access pattern privacy.

Claims

1. A storage system comprising:

a network;

a server having a server memory, a server processing unit and a server network interface in communication with the network; and

a plurality of clients, each client having a client memory in which data is stored, a client processing unit and a client network interface in communication with the server through the network, each of the clients having an encryption portion that enables each of the clients to securely communicate and understand data with all other clients, the server memory being shared by the clients through the network to store copies of encrypted data in the server memory from the clients, the server unable to decrypt the encrypted data stored in the server memory, the server having a timing mechanism to ensure data that is shared is a desired copy, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from the client network interface to the server an encrypted description of a transaction, as encrypted by the encryption portion of the client.

2. The system as described in claim 1 wherein the timing mechanism includes an encrypted transaction log.

3. The system as described in claim 2 wherein the timing mechanism includes a serializability mechanism which makes it appear as if each transaction occurs one at a time and in an order consistent with the encrypted transaction log.

4. The system as described in claim 3 wherein the serializability mechanism utilizes a hash chain.

5. The system as described in claim 4 wherein when the client processing unit desires to perform a transaction entailing updates to data in the server memory, the client network interface sends an encoding of the transaction and the updates to the server;

the server then sends information about other transactions to the client which the client processing unit checks for a conflict between the transaction and the other transactions;

with the client network interface sending a commit message to the server regarding the transaction if there are no conflicts.

6. The system as described in claim 5 wherein the client processing unit detects conflicts by parsing and comparing SQL statements.

7. The system as described in claim 5 wherein the processing unit appends to the commit message a last value in the hash chain encoding all previous updates.

8. The system as described in claim 7 wherein the client processing unit verifies that a value of a hash chain received from other clients matches the other clients'"'"' own computation of the value of the clients'"'"' hash chain.

9. The system as described in claim 1 wherein the client processing unit recovers data in the client memory by obtaining and applying data from the server memory.

10. The system as described in claim 1 wherein the client network interface imports a large object which the client processing unit modifies, and the client network interface sends the hash value of the modified object in updates to the server.

11. A client of a storage system comprising:

a client memory in which data is stored;

an encryption portion which encrypts and decrypts the data;

a client processing unit in communication with the memory which stores the data in the client memory according to code the processing unit executes; and

a client network interface in communication with the client memory through which a request for a required slot in an encrypted transaction log of a server is sent to the server and through which an allocate transaction slot response from the server is received, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from the client network interface to the server an encrypted description of a transaction, as encrypted by the encryption portion of the client.

12. A server of a storage system comprising:

a server memory in which encrypted data from clients is stored and shared, said server memory having an encrypted transaction log, the encrypted data not able to be decrypted by the server, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from a client network interface to the server an encrypted description of a transaction, as encrypted by an encryption portion of the client;

a server processing unit in communication with the server memory; and

a server network interface which receives a request for required slot in the transaction log from a client through which an allocate transaction slot response is sent to the client.

13. A method for storing data comprising the steps of:

sending an encrypted encoding of a transaction entailing updates to data a client processing unit of a client desires to perform from a client network interface of the client through a network to a server, the server unable to decrypt the encoding, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from the client network interface to the server an encrypted description of a transaction, as encrypted by the encryption portion of the client;

sending information about other transactions to the client from a server network interface of the server through the network;

checking with the client processing unit for a conflict between the transaction and the other transactions;

sending a commit message from the client network interface to the server regarding the transaction if there are no conflicts; and

executing the transaction on each client.

14. The method as described in claim 13 including the steps of sharing a server memory of the server by other clients through the network to store copies of encrypted data in the server memory from the clients, the server unable to decrypt the encrypted data stored in the server memory;

and ensuring data that is shared is a desired copy with a timing mechanism of the server.

15. A method as described in claim 14 wherein the ensuring step includes the steps of sending a request from the client network interface through the network to the server for a required slot in an encrypted transaction log of the server;

and receiving at the client network interface an allocate transaction slot response from the server.

16. The method as described in claim 15 wherein the ensuring step includes the step of causing the transactions to have the effect of occurring in an order consistent with the order of the log.

17. The method as described in claim 16 wherein the checking step includes the step of detecting with the client processing unit conflicts by parsing and comparing SQL statements.

18. The method described in claim 14 including the step of the client processing unit appending to the commit message a last value in a hash chain encoding all previous updates.

19. The method as described in claim 18 including the step of the client processing unit verifying that a value of a hash chain received from other clients matches the other clients'"'"' own computation of the value of the clients'"'"' hash chain.

21. The method as described in claim 13 including the steps of the client network interface importing a large object which the client processing unit modifies, and the client network interface sending the hash value of the modified object in updates to the server.

22. The method as described in claim 13 wherein the server cannot determine whether more than one client is accessing data which is the same or a single client accesses data which is the same at different times.

23. The method as described in claim 13 including the step of the clients sending timestamps of a last update to ensure the server has not been withholding updates.

20. The method as described in 13 including the step of the processing unit recovering data in the client memory by obtaining and reading and decrypting data from the server memory.

24. A method of a client of a storage system comprising the steps of:

storing data in a client memory according to code a client processing unit executes;

forming a request for a required slot in an encrypted transaction log of a server with an encryption portion;

sending the request to the server through a client network interface, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from the client network interface to the server an encrypted description of a transaction, as encrypted by the encryption portion of the client; and

receiving an allocate transaction slot response from the server.

25. A method of a server of a storage system comprising the steps of:

storing encrypted data from clients in a server memory which a server processing unit cannot decrypt, each client sends from a client network interface to the server an encrypted description of a transaction, as encrypted by an encryption portion of the client, the server memory having an encrypted transaction log, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory;

receiving at a server network interface a request for required slot in the transaction log from a client; and

sending an allocate transaction slot response to the client through the server network interface.

26. A storage system comprising:

a network;

a server having a server network interface in communication with the network, a server processing unit and a server memory for storing data; and

a first client and at least a second client, each client having a client processing unit, a client memory, encryption portion and a client network interface in communication with the network;

when the first client desires to perform a deterministic transaction T1 to the server, client sends from the client network interface to the server an encrypted executable description of T1, as encrypted by the encryption portion of the first client, the server network interface sending information about an ordered sequence of deterministic transactions X to the second client, the client processing unit of the second client executing transactions X in the order they were sent to the server from at least the first client, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions.

27. The system as described in claim 26 wherein the processing unit of the first client appends to the commit message a last value in a hash chain encoding all previous updates.

28. The system as described in claim 27 wherein the client processing unit of the first client verifies that a value of a hash chain received from other clients matches the other clients'"'"' own computation of the value of the clients'"'"' hash chain.

29. The system as described in claim 28 wherein the client processing unit of the first client recovers data in the client memory by obtaining and applying data from the server memory.

30. The system as described in claim 29 wherein the client network interface of the first and second clients sends timestamps of a last update to ensure the sever has not been withholding updates.

31. A non-transitory computer readable medium storing a computer program which when executed by at least one client processing unit of a client of a storage system communicates with a server, the computer program comprising instructions for the client processing unit generated steps of:

storing data in a client memory;

encrypting a request for a required slot in an encrypted transaction log of the server; and

sending the encrypted request to the server through a client network interface, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from the client network interface to the server an encrypted description of a transaction, as encrypted by the encryption portion of the client.

32. A non-transitory computer readable medium storing a computer program which when executed by at least one server processing unit of a server of a storage system communicates with a client, the computer program comprising instructions for the server processing unit generated steps of:

storing encrypted data from clients in a server memory which the server processing unit cannot decrypt, the server memory having an encrypted transaction log, the server cannot infer which data is accessed by the clients because clients perform read transactions only locally in the client'"'"'s client memory and cannot infer whether two transactions from the clients access a same portion of the encrypted data in the client memory and the server provides single-copy serializable transaction semantics for distributed transactions, each client sends from a client network interface to the server an encrypted description of a transaction, as encrypted by an encryption portion of the client;

receiving at a server network interface a request for a required slot in the transaction log from the client; and

sending an allocate transaction slot response to the client through the server network interface.