Compression and oblivious expansion of RLWE ciphertexts

A method comprising:

• obtaining, at data processing hardware of a user device, a plaintext query by generating a randomized query comprising a sequence of plaintext integers;
• generating, by the data processing hardware, a polynomial having coefficients, the coefficients comprising the sequence of plaintext integers of the plaintext query;
• encrypting, by the data processing hardware, the polynomial using a secret encryption key, the secret encryption key randomly sampled by the data processing hardware from a ciphertext space;
• transmitting, by the data processing hardware, the encrypted polynomial to a server in communication with the data processing hardware, the server configured to expand the encrypted polynomial using a public encryption key to obtain a sequence of encrypted integers, the sequence of encrypted integers corresponding to the sequence of plaintext integers of the plaintext query;
• receiving, at the data processing hardware, an encrypted result from the server, the encrypted result based on the sequence of encrypted integers;
• inverting, by the data processing hardware, a selected plaintext integer from the sequence of plaintext integers of the randomized query to form a modified query, the selected plaintext integer associated with a respective data block of an untrusted data store of the server;
• transmitting, by the data processing hardware, the modified query to the server, the server configured to:
• calculate an unencrypted result based on the untrusted data store the server and the modified query;
• and
• return the unencrypted result to the user device;
• and
• after receiving the encrypted result and the unencrypted result from the server, calculating, by the data processing hardware, a difference between the encrypted result and the unencrypted result to obtain a value for the respective data block of the untrusted data store that is associated with the selected plaintext integer from the sequence of plaintext integers of the randomized query.