Paper 2026/2412

Barely Sublinear RAM-FHE from Plain LWE

Abstract

Fully Homomorphic Encryption for RAM programs (RAM-FHE), introduced by Hamlin, Holmgren, Weiss, and Wichs (Crypto 2019), allows a server to evaluate a RAM program on encrypted data at a per-step cost sublinear in the memory size $N$, whereas standard FHE must read the entire memory for every memory access. In a celebrated work, Lin, Mook, and Wichs (STOC 2023) gave the first, and to date the only, construction from a concrete assumption, namely Ring-LWE. In this work, we construct a RAM-FHE scheme from plain LWE that evaluates each step of a RAM program in $o(N/\log N)$ time. While the scheme is barely sublinear, even such a slight saving over the linear cost of standard FHE was not known to be achievable from unstructured, plain LWE. As Lin, Mook, and Wichs did, we build RAM-FHE by extending a Doubly-Efficient Private Information Retrieval (DEPIR) scheme. Since the only DEPIR from plain LWE, due to Lee (Crypto 2026), relies on a Common Reference String (CRS) that is incompatible with the extension, we show how to remove the CRS and obtain a DEPIR from plain LWE in the standard model, which may be of independent interest.