A (single server) private information retrieval (PIR) allows a client to read data from a public database held on a remote server, without revealing to the server which locations she is reading. In a doubly efficient PIR (DEPIR), the database is first preprocessed, but the server can subsequently answer any client’s query in time that is sub-linear in the database size. Prior work gave a plausible candidate for a public-key variant of DEPIR, where a trusted party is needed to securely preprocess the database and generate a corresponding public key for the clients; security relied on a new non-standard code-based assumption and a heuristic use of ideal obfuscation. In this work we construct the stronger unkeyed notion of DEPIR, where the preprocessing is a deterministic procedure that the server can execute on its own. Moreover, we prove security under just the standard ring learning-with-errors (RingLWE) assumption. For a database of size N and any constant ε>0, the preprocessing run-time and size is O(N1+ε), while the run-time and communication-complexity of each PIR query is polylog(N). We also show how to update the preprocessed database in time O(Nε). Our approach is to first construct a standard PIR where the server’s computation consists of evaluating a multivariate polynomial; we then convert it to a DEPIR by preprocessing the polynomial to allow for fast evaluation, using the techniques of Kedlaya and Umans (STOC ’08).

Minkowski proved that any$n$-dimensional lattice of unit determinant has a nonzero vector of Euclidean norm at most$\sqrt {n}$; in fact, there are$2^{\Omega (n)}$such lattice vectors. Lattices whose minimum distances come close to Minkowski’s bound provide excellent sphere packings and error-correcting codes in${\mathbb {R}}^{n}$. The focus of this work is a certain family of efficiently constructible$n$-dimensional lattices due to Barnes and Sloane, whose minimum distances are within an$O(\sqrt {\log n})$factor of Minkowski’s bound. Our primary contribution is a polynomial-time algorithm thatlist decodesthis family to distances approaching$1/\sqrt {2}$of the minimum distance. The main technique is to decode Reed-Solomon codes under error measured in the Euclidean norm, using the Koetter-Vardy “soft decision” variant of the Guruswami-Sudan list-decoding algorithm.