Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Private Information Retrieval with Preprocessing Based on the Approximate GCD Problem

Thomas Vannet, Noboru Kunihiro

Published Jan 1, 2016• 3 citations
Publisher
DOI
10.1007/978-3-319-31301-6_14

Related papers

Improvement of preprocessing complexity in private information retrieval

Gahangir Hossain

•Jan 1, 2008•0 citations

Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing

Amos Beimel, Yuval Ishai, Tal Malkin

Journal of Cryptology•Feb 26, 2004•89 citations

Robust Information-Theoretic Private Information Retrieval

Amos Beimel, Yoav Stahl

Lecture notes in computer science•Jan 1, 2003•59 citations

Robust Information-Theoretic Private Information Retrieval

Amos Beimel, Yoav Stahl

Journal of Cryptology•Jul 1, 2007•63 citations

Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)

Toshiya Itoh

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 25, 1999•0 citations

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 to answer queries in sublinear time. We prove computation lower bounds for PIR with preprocessing schemes making blackbox usage of any cryptography (such as random oracles or virtual blackbox obfuscation). If the client stores $s$ bits about an $n$-bit database, then answering $k = Ω(s)$ queries requires either $Ω(n/s)$ amortized online communication or $Ω(n/s)$ amortized server cryptographic operations. This is tight, as known constructions match either bound while outperforming the other. Our lower bound is unconditional and allows arbitrary query protocols, weakened privacy, and server-side database encodings (including doubly efficient PIR) whenever the encoding is independent of the blackbox cryptography. Previous bounds were only known conditionally and for restricted classes of preprocessing, e.g., under non-encoding assumptions. Our framework also yields $Ω(n/s)$ communication lower bounds for schemes with $o(n/s)$ server cryptographic operations, communication-determined server cryptography, or perfect privacy in the idealized model. Finally, we prove lower bounds for symmetric PIR with client preprocessing in the random oracle model and give a matching construction using only one-way functions in the online phase.

arXiv:2607.06451•Jul 7, 2026•0 citations
Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by leveraging preprocessing to answer queries in sublinear time. We prove computation lower bounds for PIR with preprocessing schemes making blackbox usage of any cryptography (such as random oracles or virtual blackbox obfuscation). If the client stores sss bits about an nnn-bit database, then answering k=Ω(s)k = Ω(s)k=Ω(s) queries requires either Ω(n/s)Ω(n/s)Ω(n/s) amortized online communication or Ω(n/s)Ω(n/s)Ω(n/s) amortized server cryptographic operations. This is tight, as known constructions match either bound while outperforming the other. Our lower bound is unconditional and allows arbitrary query protocols, weakened privacy, and server-side database encodings (including doubly efficient PIR) whenever the encoding is independent of the blackbox cryptography. Previous bounds were only known conditionally and for restricted classes of preprocessing, e.g., under non-encoding assumptions. Our framework also yields Ω(n/s)Ω(n/s)Ω(n/s) communication lower bounds for schemes with o(n/s)o(n/s)o(n/s) server cryptographic operations, communication-determined server cryptography, or perfect privacy in the idealized model. Finally, we prove lower bounds for symmetric PIR with client preprocessing in the random oracle model and give a matching construction using only one-way functions in the online phase.