A proxy server creates an index of keywords, receives an encrypted record, decrypts the received encrypted record as decrypted data and, when a keyword in the index is encountered in the decrypted data, associates in the index an encrypted record location identifier with the encountered keyword. The proxy server receives a search query and uses the keyword index to retrieve encrypted records from the server. The encrypted records are decrypted and sent as search results in response to the search query.