What a lovely hat

Paper 2025/1305

Barely Doubly-Efficient SimplePIR

Abstract

A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $N$. The breakthrough work of Lin-Mook-Wichs (STOC’23) presented the first DEPIR construction from the Ring-LWE assumption. This remains essentially the only known construction to date, and realizing DEPIR from alternative foundations is an open problem. In particular, constructing DEPIR from plain LWE is still open. In this work, we present a simple LWE-based construction of DEPIR in the CRS model. Our construction is inspired by SimplePIR (USENIX’23) and leverages the matrix–vector multiplication preprocessing of Williams (SODA’07). By applying the compiler of Lin–Mook–Wichs (Eurocrypt’25), we also obtain an sk-DEPIR scheme, a keyed variant of DEPIR, based on LWE in the standard model. All existing sk-DEPIR constructions, except the one implied by LMW23 based on Ring-LWE, rely on non-standard code-based assumptions. While our constructions are only barely doubly-efficient, with server computation of $O(N / \log{N})$, it was previously unknown whether even such modest sublinear efficiency could be achieved from unstructured, plain LWE.