Privacy-preserving database system
View Patent ↗A database system includes a server, index server and client. In one embodiment the server randomly permutes the order of database records. The server provides to the index server an array of encryption keys by generating a random encryption key corresponding to each permuted database record. The server encrypts each permuted database record with its corresponding encryption key. The index server computes and encrypts a sum of each encryption key and a corresponding random mask and sends a permuted array of masked keys to the server. The index server provides to the client an encrypted database record, and the mask and key corresponding to the encrypted record. The client sends the encrypted sum of the mask and key to the server. The server decrypts the masked key with a public key and sends the decrypted key to the client. The client then recovers the record key and decrypts the record.
1. A database server, comprising:
a processor;
a memory accessible by the processor and including a plurality of database records,
wherein the processor is configured to:
at least pseudorandomly permute the order of the database records, thereby producing a permuted database;
generate an at least pseudorandom encryption key corresponding to each permuted database record, thereby producing an encryption key array;
encrypt each permuted database record using a corresponding encryption key of the encryption key array, thereby producing an encrypted database array;
encrypt each encryption key of the encryption key array, thereby producing an encrypted encryption key array;
direct the encrypted database array and the encrypted encryption key array toward an index server;
decrypt and store a masked encryption key array received from the index server, the masked encryption key array being derived from the encrypted encryption key array; and
use a public-private key pair to decrypt a specified encrypted masked encryption key of the masked encryption key array in response to receiving the specified encrypted masked encryption key from a client server, and to direct a resulting decrypted masked key toward the client server.
2. The server of claim 1 , further comprising a network interface configured to provide communication over a network between the processor, the index server and a client server.
3. The server of claim 1 , wherein the processor is further configured to generate a public-private key pair, and to homomorphically encrypt each of the pseudorandom encryption keys of the encryption key array using the public-private key pair.
4. A database index server, comprising:
a processor;
a memory accessible by the processor and including program instructions executable by the processor to:
receive a key array of encrypted encryption keys;
generate a mask array including at least pseudorandom masks, each pseudorandom mask corresponding to a member of the key array; and
compute for each encryption key of the key array a sum of that encryption key and the corresponding mask;
homomorphically encrypt each sum, thereby producing an array of encrypted masked keys; and
at least pseudorandomly permute the order of the encrypted sums to produce a permuted array of masked encrypted keys, and to direct the permuted array of masked encrypted keys toward the database server.
5. The index server of claim 4 , wherein the processor is further configured to receive an array of data records from a database server and a record number from a client server, and in response to return to the client server a data record and a mask corresponding to the record number.
6. The index server of claim 4 , wherein the processor is further configured to direct a permuted database index toward the server to access a corresponding member of the permuted array of masked encrypted keys.
7. The index server of claim 6 , wherein each record of the array of data records is encrypted.
8. A method of operating a database server, comprising:
at least pseudorandomly permuting the order of database records stored by the server;
generating an at least pseudorandom encryption key corresponding to each permuted database record, thereby producing an encryption key array;
encrypting each permuted database record using a corresponding encryption key of the encryption key array, thereby producing an encrypted database array;
encrypting each encryption key of the encryption key array, thereby producing an encrypted encryption key array;
directing the encrypted database array and the encrypted encryption key array toward an index server;
decrypting and storing a masked encryption key array received from the index server, the masked encryption key array being derived from the encrypted encryption key array;
using a public-private key pair to decrypt a specified encrypted masked encryption key of the masked encryption key array in response to receiving the specified encrypted masked encryption key from the client server, and directing a resulting decrypted masked key toward the client server.
9. The method of claim 8 , further comprising generating a public-private key pair and homomorphically encrypting each of the pseudorandom encryption keys using the public-private key pair.
10. A method of operating a database index server, comprising:
receiving an array of encryption keys;
generating a mask array including a plurality of at least pseudorandom masks, each at least pseudorandom mask corresponding to a member of the key array;
computing and homomorphically encrypting a sum of each encryption key and the at least pseudorandom mask corresponding to that key;
encrypting each sum, thereby producing an array of encrypted masked keys; and
at least pseudorandomly permuting the order of the encrypted sums to produce a permuted array of masked encrypted keys, and directing the permuted array of masked encrypted keys toward the database server.
11. The method of claim 10 , further comprising receiving an array of data records from a database server and a record number from a client server, and in response returning to the client server a data record and a mask corresponding to the record number.
12. The method of claim 11 , wherein each record of the array of data records is encrypted.
13. The method of claim 10 , further comprising directing a permuted database index toward the server to access a corresponding member of the permuted array of masked encrypted keys.