Ring-LWE ⇒ Unkeyed DEPIR

Standard model · LMW23

Statement

If Ring-LWE 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 })$, after which each query costs $\mathrm{polylog}(N)$ server time and communication, and updates to the preprocessed database cost $O(N^{\epsilon })$ — LMW23.

Notes

• 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.