Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
summary
Constructs the first unkeyed schemes that make single-server private reads and RAM-style FHE practical under Ring LWE, turning PIR into evaluation of a low‑degree multivariate polynomial and using Kedlaya–Umans preprocessing plus CRT to precompute that polynomial. Preprocessing runs in about N^{1+ε}, per-query communication and server work drop to polylog(N), updates cost ~N^{ε}, and the design stitches an algebraic somewhat‑homomorphic layer to a general FHE layer so encrypted CPU steps issue DEPIR queries and resume under FHE.
AI-written summary · about
chapters (7)
- 0:00Introduction to ram fhe
- 5:49Private information retrieval
- 11:50Double efficient PIR
- 18:20Construction and algorithms
- 31:48Algebraic encryption scheme
- 37:42Achieving ram fhe
- 43:59Conclusion and q&a
related talks
01h 04mDoubly Efficient Private Information Retrieval
43mSingle-Server Private Information Retrieval with Sublinear Amortized Time
58mPrivate information retrieval at 30: Achievements, disappointments, and open problems
01h 14mPrivate Information Retrieval and Oblivious RAM
35mLower-Bounds on Public-Key Operations in PIR
20mHEaaN.MLIR: An Optimizing Compiler for Fast Ring-Based Homomorphic Encryption
01h 01mCircularity Based IO, Part 1
01h 06mOblivious RAM II