Ring-LWE with quasi-polynomial factors ⇒ Unkeyed DEPIR

Standard model · LMW23

Statement

If Ring-LWE with quasi-polynomial approximation factors is hard, then for every constant $\epsilon >0$ there is an unkeyed DEPIR in which the server deterministically preprocesses a database of size $N$ in time and space $O(N^{1+\epsilon })\cdot \mathrm{poly}(\lambda ,\log N)$, after which each query has query time and communication $\mathrm{poly}(\lambda ,\log N)$, and is perfectly correct (Definition 4.1, Theorem 4.4) — LMW23.

Notes

• Under Ring-LWE with sub-sub-exponential approximation factors, preprocessing time and storage drop to $N^{1+o(1)}\cdot \mathrm{poly}(\lambda )$ at query cost $N^{o(1)}\cdot \mathrm{poly}(\lambda )$ (Theorem 4.4), and an updatable variant updates the preprocessed database in time $O(N^{\epsilon })$ — LMW23.

• On top of this DEPIR, LMW23 construct fully homomorphic encryption for RAM programs under Ring-LWE with circular security, with homomorphic evaluation time $T^{1+\epsilon }\cdot \mathrm{polylog}(|x|+|y|)$ for a RAM program of worst-case run-time $T$ on client input $x$ and preprocessed server input $y$ — LMW23.