A method comprising: initializing, by data processing hardware of a client device, a client state on the client device by executing a private batched sum retrieval instruction to compute c sums O of data blocks from an untrusted storage device, each computed sum O stored on memory hardware of the client device and comprising a sum of a corresponding subset S of exactly k data blocks; executing, by the data processing hardware, a query instruction to retrieve a query block B q stored on the untrusted storage device by: iterating through each of the c sums O of data blocks stored on the memory hardware to identify one of the c sums O that does not include the query block B q; instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into n k + 1 partitions each containing k+1 data blocks and summing the k+1 data blocks in each of the n k + 1 partitions to determine a corresponding encrypted data block sum for each of the n k + 1 partitions, one of the n k + 1 partitions comprising a fixed partition that includes the identified c sum O of data blocks that does not include the query block B q; retrieving the encrypted data block sum for the n k + 1 partition that comprises the fixed partition from the service managing the untrusted storage device; and decrypting and subtracting the encrypted data block sum from the identified c sum O of data blocks stored on the memory hardware of the client device to obtain the query block Bq; determining, by the data processing hardware, whether the number of queries (q) exceeds a query threshold; and re-initializing, by the data processing hardware, the client state when the number of queries (q) exceeds the query threshold. initializing, by data processing hardware of a client device, a client state on the client device by executing a private batched sum retrieval instruction to compute c sums O of data blocks from an untrusted storage device, each computed sum O stored on memory hardware of the client device and comprising a sum of a corresponding subset S of exactly k data blocks; executing, by the data processing hardware, a query instruction to retrieve a query block B q stored on the untrusted storage device by: iterating through each of the c sums O of data blocks stored on the memory hardware to identify one of the c sums O that does not include the query block B q; instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into n k + 1 partitions each containing k+1 data blocks and summing the k+1 data blocks in each of the n k + 1 partitions to determine a corresponding encrypted data block sum for each of the n k + 1 partitions, one of the n k + 1 partitions comprising a fixed partition that includes the identified c sum O of data blocks that does not include the query block B q; retrieving the encrypted data block sum for the n k + 1 partition that comprises the fixed partition from the service managing the untrusted storage device; and decrypting and subtracting the encrypted data block sum from the identified c sum O of data blocks stored on the memory hardware of the client device to obtain the query block Bq; iterating through each of the c sums O of data blocks stored on the memory hardware to identify one of the c sums O that does not include the query block B q; instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into n k + 1 partitions each containing k+1 data blocks and summing the k+1 data blocks in each of the n k + 1 partitions to determine a corresponding encrypted data block sum for each of the n k + 1 partitions, one of the n k + 1 partitions comprising a fixed partition that includes the identified c sum O of data blocks that does not include the query block B q; retrieving the encrypted data block sum for the n k + 1 partition that comprises the fixed partition from the service managing the untrusted storage device; and decrypting and subtracting the encrypted data block sum from the identified c sum O of data blocks stored on the memory hardware of the client device to obtain the query block Bq; determining, by the data processing hardware, whether the number of queries (q) exceeds a query threshold; and re-initializing, by the data processing hardware, the client state when the number of queries (q) exceeds the query threshold.