A method, system, and computer program product to generate results for a query to an encrypted database stored on a host are described. The system includes a host comprising a storage device to store the encrypted database, and a 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. The system also includes an interface of the host to receive the query, and a host processor to generate a sub-query form the query for each field associated with the query. 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.