Privacy-preserving database system

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.

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.

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.