💻 computer science

Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

This paper establishes optimal computation and communication lower bounds for single-server private information retrieval with client preprocessing that relies on blackbox cryptography, proving that such schemes must incur $\Omega(n/s)$ amortized online cost or server operations and ruling out the existence of doubly efficient PIR under these assumptions.

Original authors: Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library (a database) containing $n$ books, and you want to borrow just one specific book without the librarian (the server) knowing which one you picked. This is the problem of Private Information Retrieval (PIR).

Usually, to keep your secret, you have to ask the librarian to read the entire library catalog to you, which is slow and expensive. Recent breakthroughs found a way to make this faster by letting you do some "homework" beforehand (preprocessing). You could store a small cheat sheet (client storage) that helps you ask a very short question later.

This paper asks a fundamental question: How good can this cheat sheet actually make things? Can we make the librarian's job so easy that they barely have to think, while you only send a tiny message?

The authors say: "No, there are hard limits."

Here is the breakdown of their findings using simple analogies:

1. The "Cheat Sheet" Trade-off

Imagine you have a giant encyclopedia ( $n$ pages). You are allowed to memorize a small cheat sheet of size $s$ (your client storage).

The Old Rule: Without a cheat sheet, the librarian has to read the whole book to answer you.
The New Hope: With a cheat sheet, maybe the librarian can just glance at a few pages?
The Paper's Verdict: The authors prove a strict law of physics for this system. If your cheat sheet is size $s$ $s$ , the librarian must do at least $n/s$ $n / s$ amount of work.
- The Metaphor: Think of the database as a giant pizza with $n$ slices. Your cheat sheet is a small napkin ( $s$ ) where you can write down a few notes. The paper proves that no matter how clever your napkin is, the chef (librarian) still has to look at at least $n/s$ slices of the pizza to serve you. If your napkin is tiny, the chef has to look at almost the whole pizza. If your napkin is huge (almost the size of the pizza), the chef only has to look at a few slices. You can't have a tiny napkin and a chef who does almost no work.

2. The "Dual" Puzzle (The Magic Trick)

To prove this, the authors invented a new, strange game called "Dual PIR."

Normal PIR: You do homework first (offline), then ask a question (online).
Dual PIR: You write a note before you even know what question you will ask. Then, you get the question, and you are allowed to ask for a tiny "hint" to solve it.
The Proof: They showed that if a super-efficient PIR existed, you could use it to win this "Dual PIR" game. But they proved that winning the "Dual PIR" game is mathematically impossible if your hint is too small compared to the number of questions you have. It's like trying to guess 100 random numbers by only being allowed to write down 5 digits of a hint. It's simply not enough information.

3. The "Black Box" Rule

The paper assumes the librarian uses "Black Box" cryptography.

The Metaphor: Imagine the librarian has a magical, unbreakable black box that can do complex math. They can put numbers in and get answers out, but they don't know how the box works inside.
The Finding: Even with this magical box, the limits still hold. You can't cheat the system. If the librarian does very little work, the communication (the message you send) must be huge. If the message is tiny, the librarian must do a lot of work. You can't have both.

4. The "Symmetric" Problem (Keeping Secrets Both Ways)

There is a stricter version called Symmetric PIR (SPIR).

Normal PIR: The librarian doesn't know which book you took.
Symmetric PIR: The librarian doesn't know which book you took, AND you aren't allowed to peek at any other books in the library.
The Finding: The authors built a new system that achieves this Symmetric PIR using only simple math (One-Way Functions) during the online part.
The Catch: This system has a limit on how many times you can use it before you have to go back and do the heavy "homework" again. You can't use the same cheat sheet forever to ask infinite questions without the librarian eventually having to do more work or the system breaking.

Summary of the "Laws" Discovered

The paper establishes three main "laws" for these systems:

The Work Law: If you store $s$ bits of data, the server must do at least $n/s$ work per query.
The Communication Law: If the server does very little work, you must send a lot of data.
The Symmetry Law: If you want to protect the database from the user (Symmetric PIR) without using heavy "public-key" magic during the query, you are limited in how many queries you can make before needing to refresh your data.

In short: The paper doesn't invent a new faster way to search; instead, it draws a map of the "impossible zone." It tells us that the current best methods are already hitting the theoretical ceiling. You can't make the librarian's job easier without making your message bigger, and you can't make your message smaller without making the librarian's job harder.

Technical Summary: Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

1. Problem Statement

The paper investigates the fundamental limits of Single-Server Private Information Retrieval (PIR) in the preprocessing model. In this setting, a client performs an offline phase to store a small amount of state ( $s$ bits) about an $n$ -bit database, enabling more efficient online queries. While recent breakthroughs have demonstrated single-server PIR schemes with sublinear query computation and communication by leveraging preprocessing (e.g., [CHK22, ZPZS24, LMW23]), the theoretical boundaries of these constructions remain unclear.

Specifically, the authors address whether it is possible to construct single-server PIR schemes that:

Achieve sublinear amortized online computation (specifically $o(n/s)$ ).
Rely on blackbox cryptography (modeled via crypto oracles, including random oracles, virtual blackbox obfuscation, and generic multilinear groups).
Support Symmetric PIR (SPIR) (where the client learns only the queried entry) using only one-way functions (OWFs) during the online phase.

Prior lower bounds for PIR with preprocessing were limited to restricted classes of schemes (e.g., requiring non-encoding servers, database-oblivious queries, or single-roundtrip interactions) or relied on unproven complexity assumptions. This work aims to provide unconditional lower bounds for a broader class of schemes making blackbox usage of cryptography.

2. Methodology

The core of the paper's methodology is the introduction of a new primitive called Dual PIR and a reduction from standard PIR with preprocessing to this primitive.

2.1 Dual Private Information Retrieval (Dual PIR)

The authors define Dual PIR as an inversion of the standard PIR preprocessing model:

Advice Phase: Before any queries are known, the client generates a $t$ -bit advice string (transcript) based on the database.
Hint Phase: Given the database, a batch of $k$ query indices, and the advice, the client generates an $s$ -bit hint.
Reconstruction: Using only the query indices, the advice, and the hint (but without access to the database), the client must reconstruct the queried database entries.

This formulation transforms the PIR efficiency problem into a compression problem. If a PIR scheme is too efficient (i.e., $t = o(n)$ and $s < k$ ), it implies the existence of a Dual PIR that compresses $k$ bits of information into $s$ bits using only $t$ bits of pre-shared advice, which is information-theoretically impossible under certain conditions.

2.2 Reduction from PIR to Dual PIR

The authors construct a reduction showing that any secure PIR scheme with preprocessing can be transformed into a Dual PIR scheme.

Advice: Simulates the PIR execution for a fixed query to generate a communication transcript and a set of server crypto-oracle queries.
Hint: Re-randomizes the client's state to match the fixed transcript for a different query. Crucially, to handle the blackbox nature of cryptography, the Hint algorithm samples new crypto oracles that are consistent with the server's previous queries (using a shared random oracle to ensure consistency).
Reconstruction: Simulates the client-side of the PIR query using the sampled state and the fixed transcript.

2.3 Connection to Subkey Prediction

To prove the impossibility of efficient Dual PIR, the authors connect the problem to subkey prediction in leakage-resilient cryptography ([BKR16]). They show that a correct and efficient Dual PIR would allow an adversary to predict $k$ random bits of an $n$ -bit key given $t$ bits of leakage, with success probability exceeding known information-theoretic bounds. Specifically, if $t < n/2$ and $k = \Omega(s)$ , the probability of correct reconstruction is bounded by $2^{s - \Omega(k)}$ .

3. Key Contributions and Results

3.1 Computation Lower Bounds

The paper establishes that for any single-server PIR with client preprocessing making blackbox usage of cryptography:

Theorem 1.1: It is impossible to achieve both $o(n/s)$ amortized online communication and $o(n/s)$ amortized server cryptographic operations.
Implication: Any such scheme must satisfy at least one of the following:
1. Amortized online communication is $\Omega(n/s)$ bits.
2. The server performs $\Omega(n/s)$ cryptographic bit operations.
Tightness: This bound is optimal. Existing schemes (e.g., [WR25]) achieve $O(n/s)$ communication with no server crypto operations, while others (e.g., [ZPZS24]) achieve $O(n/s)$ communication with no server crypto operations but require refreshing client state. The lower bound confirms that one cannot bypass both bottlenecks simultaneously.

3.2 Doubly Efficient PIR (DEPIR)

The authors rule out the existence of Doubly Efficient PIR (where both client and server have sublinear time) built from blackbox cryptography.

Theorem 1.2: There is no single-server DEPIR with sublinear query computation ( $t = o(n)$ ) for a single query, even if the server performs arbitrary encoding.
This result applies to public-key DEPIR and improves upon prior impossibility results that were restricted to single-roundtrip queries with passive servers.

3.3 Communication Lower Bounds

The paper derives specific communication lower bounds for restricted classes of PIR:

Theorem 1.4: If a PIR scheme satisfies any of the following, it requires $\Omega(n/s)$ $Ω (n / s)$ amortized communication:
1. The server performs $o(n/s)$ cryptographic operations.
2. Server cryptographic operations depend only on the communication transcript (database-oblivious crypto usage).
3. The scheme offers perfect privacy in an idealized model.

3.4 Symmetric PIR (SPIR)

The paper addresses the construction of Symmetric PIR (SPIR) with client preprocessing, where the client learns only the queried entry.

Construction (Theorem 1.5): The authors present a construction of SPIR with client preprocessing that relies only on One-Way Functions (OWFs) during the online query phase. The scheme achieves $\tilde{O}(n/s)$ communication and computation, supporting $\tilde{O}(s)$ queries per offline phase.
Limitation (Theorem 1.6): In the random oracle model, no such SPIR scheme can support more than $k > s$ queries per offline phase. This contrasts with non-symmetric PIR, which can support unbounded queries by refreshing state. The authors prove that supporting $k > s$ queries requires public-key cryptography or linear communication.

3.5 Weak PIR

The lower bounds extend to "weak" PIR schemes that provide privacy only against adversaries making a polynomial number of crypto oracle queries (similar to Merkle puzzles).

Theorem 1.3 & 1.5: Even for weak adversaries, sublinear online query time is impossible for single-server PIR with preprocessing if the honest parties and the adversary make comparable numbers of oracle queries.

4. Significance and Claims

The paper claims to resolve the open question of the best possible efficiency for single-server PIR with preprocessing under blackbox cryptography assumptions.

Unconditional Results: Unlike prior work (e.g., [ISW24]) that relied on complexity assumptions (like the separation of SZK and BPP) or restricted the query model (database-oblivious, single-roundtrip), these lower bounds are unconditional and apply to a much broader class of schemes, including those with multiple rounds and database-dependent queries.
Optimality of Current Constructions: The results validate that recent constructions achieving $\tilde{O}(n/s)$ communication or computation are essentially optimal; one cannot simultaneously minimize both communication and server computation below this threshold without breaking blackbox cryptography assumptions.
SPIR Feasibility: The work demonstrates that Symmetric PIR is achievable with only OWFs in the online phase, provided the number of queries is limited to the size of the client's stored state ( $s$ ). This clarifies the trade-off between symmetry (data privacy) and query capacity in the preprocessing model.
DEPIR Impossibility: The paper definitively rules out the existence of public-key DEPIR with sublinear query computation from blackbox cryptography, settling a significant open problem in the field.

In summary, the paper establishes that the "bottlenecks" identified in recent PIR constructions (either high communication or high server computation) are fundamental limitations inherent to blackbox cryptography, not merely artifacts of current construction techniques.