A method, comprising: generating a partitioned database in which a database is partitioned into shards each having a shard identifier that logically distinguishes each shard from other shards, and database entries in each shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard; receiving, by a server including one or more processors and from a client device, a batch of client-encrypted queries, wherein the batch of client-encrypted queries includes two or more queries that have each been encrypted by the client device and specify a shard identifier for the client-encrypted query; processing, by the server, the batch of client-encrypted queries using a set of server-encrypted data stored in a database, wherein each database entry is server-encrypted and is capable of being decrypted by a corresponding decryption key, wherein the processing includes: grouping, by the server, the client-encrypted queries according to shard identifiers of the client-encrypted queries, wherein each group of client-encrypted queries includes multiple queries; executing, by the sever and for each shard, the multiple queries in the group of client-encrypted queries for the shard together in a batch execution process; and generating, by the server and for each shard, multiple server-encrypted results to the multiple queries in the group of client-encrypted queries; and transmitting, by the server, the multiple server-encrypted results for each shard to the client device. generating a partitioned database in which a database is partitioned into shards each having a shard identifier that logically distinguishes each shard from other shards, and database entries in each shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard; receiving, by a server including one or more processors and from a client device, a batch of client-encrypted queries, wherein the batch of client-encrypted queries includes two or more queries that have each been encrypted by the client device and specify a shard identifier for the client-encrypted query; processing, by the server, the batch of client-encrypted queries using a set of server-encrypted data stored in a database, wherein each database entry is server-encrypted and is capable of being decrypted by a corresponding decryption key, wherein the processing includes: grouping, by the server, the client-encrypted queries according to shard identifiers of the client-encrypted queries, wherein each group of client-encrypted queries includes multiple queries; executing, by the sever and for each shard, the multiple queries in the group of client-encrypted queries for the shard together in a batch execution process; and generating, by the server and for each shard, multiple server-encrypted results to the multiple queries in the group of client-encrypted queries; and grouping, by the server, the client-encrypted queries according to shard identifiers of the client-encrypted queries, wherein each group of client-encrypted queries includes multiple queries; executing, by the sever and for each shard, the multiple queries in the group of client-encrypted queries for the shard together in a batch execution process; and generating, by the server and for each shard, multiple server-encrypted results to the multiple queries in the group of client-encrypted queries; and transmitting, by the server, the multiple server-encrypted results for each shard to the client device.