Scalable precomputation system for host-opaque processing of encrypted databases

A system to generate results for a query to an encrypted database, the system comprising:

• a host comprising a storage device to store the encrypted database;
• a secure processor to generate indexes and index metadata from the encrypted database, each index identifying records of the encrypted database associated with a range of data for at least one field stored in the records of the encrypted database and the metadata indicating the range of data identified by the associated index;
• an interface of the host configured to receive the query;
• and
• a host processor configured to generate a sub-query form the query for each field associated with the query, wherein
• based on sub-query results obtained through the index metadata, the secure processor searches a subspace of the encrypted database to generate the results of the query.

A computer program product storing computer-readable instructions which, when processed by a first processor, causes the first processor to implement a method of generating results of a query to an encrypted database stored on a host, the method comprising:

• generating indexes from the encrypted database, each index identifying records of the encrypted database associated with a range of data for at least one field stored in the records of the encrypted database;
• generating index metadata associated with each index, the index metadata indicating the range of data identified by the associated index;
• determining a subspace of search within the encrypted database based on sub-query results obtained through the index metadata;
• and
• searching the subspace of the encrypted database to generate the results of the query.