arXiv:2607.06451

Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Published Jul 7, 2026• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.2607.06451

Related papers

Information-Theoretic Random-Index PIR

Kolby, Sebastian, Roy, Lawrence, Sternad, Jure +1 more

Jan 1, 20250 citations

Information-Theoretic Random-Index PIR

Sebastian Kolby, Lawrence Roy, Jure Sternad +1 more

Leibniz international proceedings in informaticsJan 1, 20250 citations

Two-Server Private Information Retrieval with Result Verification

Pengzhen Ke, Liang Feng Zhang

IEEE International Symposium on Information Theory (ISIT)Jun 26, 202211 citations

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval.

Iftach Haitner, Jonathan J. Hoch, Gil Segev

Jan 1, 20070 citations

An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval

Alexander Alexandrovich Razborov, Sergey Yekhanin

Annual Symposium on Foundations of Computer ScienceOct 1, 200618 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

quant-pharXiv:2610.02101Oct 2, 20260 citations

arXiv:2607.06451

Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Published Jul 7, 2026• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.2607.06451

Related papers

Information-Theoretic Random-Index PIR

Kolby, Sebastian, Roy, Lawrence, Sternad, Jure +1 more

A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).A Private Information Retrieval (PIR) protocol allows a client to learn the ith row of a database held by one or more servers, without revealing i to the servers. A Random-Index PIR (RPIR) protocol, introduced by Gentry et al. (TCC 2021), is a PIR protocol where, instead of being chosen by the client, i is random. This has applications in e.g. anonymous committee selection. Both PIR and RPIR protocols are interesting only if the communication complexity is smaller than the database size; otherwise, the trivial solution where the servers send the entire database suffices. Unlike PIR, where the client must send at least one message (to encode information about i), RPIR can be executed in a single round of server-to-client communication. In this paper, we study such one-round, information-theoretic RPIR protocols. The only known construction in this setting is SimpleMSRPIR (Gentry et al.), which requires the servers to communicate approximately N/2 bits, N being the database size. We show an Ω(√N) lower bound on communication complexity for one-round two-server information-theoretic RPIR, and a sublinear upper bound. Finally, we show how to use a sublinear amount of database-independent correlated randomness among multiple servers to get near-optimal online communication complexity (the size of one row plus the size of one index description per server).

Jan 1, 20250 citations

Information-Theoretic Random-Index PIR

Sebastian Kolby, Lawrence Roy, Jure Sternad +1 more

Leibniz international proceedings in informaticsJan 1, 20250 citations

Two-Server Private Information Retrieval with Result Verification

Pengzhen Ke, Liang Feng Zhang

Private information retrieval (PIR) allows a client to retrieve any block xifrom a database x = x1xnsuch that i remains hidden from the database servers. PIR •protocols with unconditional privacy and sublinear (in n) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers as database servers. In this paper, we consider an information-theoretic PIR with result verification (PIR-RV) model where the servers may be dishonest (i.e., cheating) and provide incorrect answers but the client can detect the existence of cheating servers. We construct a 2-server PIR-RV protocol with communication complexity ${\mathcal{O}}({n^{1/2}}{\text{log }}p)$ where p is a parameter and controls the probability that the client fails to detect. Our idea may be extended to construct k-server PIR-RV protocols for k ≥ 3.Private information retrieval (PIR) allows a client to retrieve any block xifrom a database x = x1xnsuch that i remains hidden from the database servers. PIR •protocols with unconditional privacy and sublinear (in n) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers as database servers. In this paper, we consider an information-theoretic PIR with result verification (PIR-RV) model where the servers may be dishonest (i.e., cheating) and provide incorrect answers but the client can detect the existence of cheating servers. We construct a 2-server PIR-RV protocol with communication complexity ${\mathcal{O}}({n^{1/2}}{\text{log }}p)$ where p is a parameter and controls the probability that the client fails to detect. Our idea may be extended to construct k-server PIR-RV protocols for k ≥ 3.

IEEE International Symposium on Information Theory (ISIT)Jun 26, 202211 citations

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval.

Iftach Haitner, Jonathan J. Hoch, Gil Segev

We study the communication complexity of single-server Private Information Retrieval (PIR) protocolsthat are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preservingconstruction that relies on trapdoor permutations. More specifically, our main result states that in such constructions \\Omega (n) bits must be communicated by the server, where n is the size of the server's database,and this improves the \\Omega (n / log n) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07).Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower boundwe establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender duringthe commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided bythe scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the e fficiencyof the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentiallypreserves the communication complexity of the underlying single-server PIR protocol.We study the communication complexity of single-server Private Information Retrieval (PIR) protocolsthat are based on fundamental cryptographic primitives in a black-box manner. In this setting, we establish a tight lower bound on the number of bits communicated by the server in any polynomially-preservingconstruction that relies on trapdoor permutations. More specifically, our main result states that in such constructions \\Omega (n) bits must be communicated by the server, where n is the size of the server's database,and this improves the \\Omega (n / log n) lower bound due to Haitner, Hoch, Reingold and Segev (FOCS '07).Therefore, in the setting under consideration, the naive solution in which the user downloads the entire database turns out to be optimal up to constant multiplicative factors. We note that the lower boundwe establish holds for the most generic form of trapdoor permutations, including in particular enhanced trapdoor permutations.Technically speaking, this paper consists of two main contributions from which our lower bound is obtained. First, we derive a tight lower bound on the number of bits communicated by the sender duringthe commit stage of any black-box construction of a statistically-hiding bit-commitment scheme from a family of trapdoor permutations. This lower bound asymptotically matches the upper bound provided bythe scheme of Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). Second, we improve the e fficiencyof the reduction of statistically-hiding commitment schemes to low-communication single-server PIR, due to Beimel, Ishai, Kushilevitz and Malkin (STOC '99). In particular, we present a reduction that essentiallypreserves the communication complexity of the underlying single-server PIR protocol.

Jan 1, 20070 citations

An \Omega(n^1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval

Alexander Alexandrovich Razborov, Sergey Yekhanin

A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user and the servers. A large amount of effort has been invested by researchers over the last decade in search for efficient PIR schemes. A number of different schemes ((B. Chor. O. Goldreich. E. Kushilevitz. and M. Sudan, 1998), (A. Beimel and Y. Ishai, 2001) ,(D. Woodruff and S. Yekhanin, 2005)) have been proposed, however all of them ended up with the same communication complexity of O(n1/3). The best known lower bound to date is 5 log n by (S. Wehner and R. de Wolf, 2005) . The tremendous gap between upper and lower bounds is the focus of our paper. We show an Omega(n1/3) lower bound in a restricted model that nevertheless captures all known upper bound techniques. Our lower bound applies to bilinear group based PIR schemes. A bilinear PIR scheme is a one round PIR scheme, where user computes the dot product of servers' responses to obtain the desired value of the i-th bit. Every linear scheme can be turned into a bilinear one with an asymptotically negligible communication overhead. A group based PIR scheme is a PIR scheme that involves servers representing database by a function on a certain finite group G, and allows user to retrieve the value of this function at any group element using the natural secret sharing scheme based on G. Our proof relies on representation theory of finite groupsA two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user and the servers. A large amount of effort has been invested by researchers over the last decade in search for efficient PIR schemes. A number of different schemes ((B. Chor. O. Goldreich. E. Kushilevitz. and M. Sudan, 1998), (A. Beimel and Y. Ishai, 2001) ,(D. Woodruff and S. Yekhanin, 2005)) have been proposed, however all of them ended up with the same communication complexity of O(n1/3). The best known lower bound to date is 5 log n by (S. Wehner and R. de Wolf, 2005) . The tremendous gap between upper and lower bounds is the focus of our paper. We show an Omega(n1/3) lower bound in a restricted model that nevertheless captures all known upper bound techniques. Our lower bound applies to bilinear group based PIR schemes. A bilinear PIR scheme is a one round PIR scheme, where user computes the dot product of servers' responses to obtain the desired value of the i-th bit. Every linear scheme can be turned into a bilinear one with an asymptotically negligible communication overhead. A group based PIR scheme is a PIR scheme that involves servers representing database by a function on a certain finite group G, and allows user to retrieve the value of this function at any group element using the natural secret sharing scheme based on G. Our proof relies on representation theory of finite groups

Annual Symposium on Foundations of Computer ScienceOct 1, 200618 citations

Lower Bounds for Preprocessing Attacks on Quantum Cryptography

Fangqi Dong, Alex Lombardi

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$ -query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$ -qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$ . In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$ , with a trivial attack at $S = N$ . This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$ . Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$ . (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$ qubits of non-uniform advice can recover a random key $k$ from the $n$-qubit binary phase state $|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of quantum cryptography over classical cryptography: $n$ qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.

quant-pharXiv:2610.02101Oct 2, 20260 citations

s

bits about an

n

-bit database, then answering

k = Ω(s)

queries requires either

Ω(n/s)

amortized online communication or

Ω(n/s)

Ω(n/s)

communication lower bounds for schemes with

o(n/s)

{\mathcal{O}}({n^{1/2}}{\text{log }}p)

where p is a parameter and controls the probability that the client fails to detect. Our idea may be extended to construct k-server PIR-RV protocols for k ≥ 3.

We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a

T

-query adversary with

S

qubits of non-uniform advice can recover a random key

k

from the

n

-qubit binary phase state

|ψ_k\rangle \propto \sum_{x} R(k,x) |x\rangle

with probability at most

O(\frac{T^2 + \sqrt{ST}}{N})

for

N=2^n

. In contrast, the best known bound for post-quantum one-way functions is

O(\frac{T^2 + ST}{N})

, with a trivial attack at

S = N

. This demonstrates a new advantage of quantum cryptography over classical cryptography:

n

qubits of communication suffice for security against preprocessing attacks with space up to

N^2

rather than

N

. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of

O(\frac{T^2}N + \sqrt{\frac{ST}N})

. (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight

O(\frac{\sqrt{S}}N)

bound for the pseudorandomness of random binary phase states against space

S

distinguishers.