Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by leveraging preprocessing t…