Abstract

We revisit the question of computing on encrypted data, in the following secret-key setting. A client uploads an encryption of a big input X to an untrusted server, and then wishes to make an unbounded number of queries q(X) while hiding q and X from the server and using only its secret key. How efficiently can this be done and under what assumptions?

We present efficient solutions for useful special cases, including matrix-vector products and private information retrieval (PIR), under either the standard Learning Parity with Noise assumption, in a parameter regime not known to imply public-key encryption, or new assumptions related to the hardness of learning a secret linear subspace from noisy samples. The latter assumptions yield efficiency features that are not met by any existing solutions.

Our core idea, inspired by prior works on PIR with preprocessing, is to encode the input X and the queries q using a pair of secret dual codes, while avoiding linear algebra attacks by adding noise.

Based on joint works with Fabrice Benhamouda, Caicai Chen, Shai Halevi, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen