The present disclosure relates to processing data queries on a logically sharded data store. An example method generally includes receiving, from a client device, a query. The query generally comprises one or more data items and wherein at least one of the one or more data items comprises sensitive data. A query processor obtains, from a key management server, a cryptographic key to use to encrypt the record based on data derived from the one or more data items comprising sensitive data and a type of the sensitive data. The query processor generates an encrypted query based on the query and the obtained cryptographic key and executes the encrypted query against the logically sharded database.