Lower Bounds for PIR with Preprocessing from Blackbox Cryptography

• URL: http://arxiv.org/abs/2607.06451v2
• Date: Wed, 08 Jul 2026 18:48:30 GMT
• Title: Lower Bounds for PIR with Preprocessing from Blackbox Cryptography
• Abstract summary: We study the limits of single-server private information retrieval (PIR) with preprocessing.<n>Our work presents computation lower bounds for any single-server PIR with preprocessing.
• Score: 57.20693707878285
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: (shortened for arXiv metadata) We study the limits of single-server private information retrieval (PIR) with preprocessing. Prior work has shown that single-server PIR with sublinear communication requires a linear number of (public-key) server operations per query [DMO00, DH24]. Recent breakthrough works, including [CHK22, ZPZS24, LMW23], circumvent these lower bounds by critically leveraging preprocessing to construct single-server PIR with sublinear query computation. Our work presents computation lower bounds for any single-server PIR with preprocessing that makes blackbox usage of {\em any} cryptography (such as random oracles and virtual blackbox obfuscation). For any client preprocessing scheme where the client stores $s$ bits about an $n$-bit database, we prove the online amortized computation must be $Ω(n/s)$ across $k = Ω(s)$ queries (even if performed in a single batch query). In more detail, we prove that they must have either $Ω(n/s)$ amortized online communication or the server must perform $Ω(n/s)$ cryptographic operations. Our lower bounds are optimal as there exist PIRs with client preprocessing matching exactly one of the above requirements while outperforming the other. Furthermore, our lower bounds also rule out the existence of doubly efficient PIR from blackbox cryptography with sublinear query computation. Our proof framework also supports $Ω(n/s)$ communication lower bounds for three mildly restricted classes of single-server PIR. We also prove lower bounds for symmetric private information retrieval (SPIR) with client preprocessing in the random oracle model and present a matching SPIR construction with client preprocessing using only OWFs during queries.

Related papers

• LAPRAS : Learning-Augmented PRivate Answering for linear query Streams [9.706153384025809]
  We present LAPRAS, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream.<n>LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget.<n> Empirically, over two real datasets, we validate the intended consistency--robustness trade-off.
  arXiv  Detail & Related papers  (2026-05-03T16:46:53Z)
• On the Gradient Complexity of Private Optimization with Private Oracles [51.044364532408345]
  We study running time, in terms of first order oracle queries, of differentially private empirical/population risk of Lipschitz losses.<n>We show that expected running time $(minfracsqrtd2, fracdlog(1/))$ is necessary to achieve $$ excess risk on problems of dimension $d when $dgeq 1/2$.
  arXiv  Detail & Related papers  (2025-11-17T23:58:11Z)
• Enhancing TreePIR for a Single-Server Setting via Resampling [0.0]
  Private Information Retrieval allows a client to retrieve an entry from a public database without revealing the queried index.<n>Traditional PIR schemes achieve sublinear server computation only under strong assumptions.<n>We propose an adaptation of TreePIR to the single-server setting by introducing a dual-table hint structure.
  arXiv  Detail & Related papers  (2025-10-06T15:03:05Z)
• ProofWala: Multilingual Proof Data Synthesis and Theorem-Proving [53.67926215943612]
  $rm Psmall ROOFWsmall ALA$ allows interaction between neural theorem-provers and two established interactive proof assistants (ITPs)<n>We show that a model trained on a mix of $rm Psmall ROOFWsmall ALA$-generated Coq and Lean data outperforms Lean-only and Coq-only models on the standard prove-at-$k$ metric.
  arXiv  Detail & Related papers  (2025-02-07T05:35:46Z)
• $\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning [7.713377215066152]
  We introduce One-shot Private Aggregation ($mathsfOPA$) where clients speak only once (or even choose not to speak) per aggregation evaluation.<n>Since each client communicates only once per aggregation, this simplifies managing dropouts and dynamic participation.<n>$mathsfOPA$ is practical, outperforming state-of-the-art solutions.
  arXiv  Detail & Related papers  (2024-10-29T17:50:11Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM Inference [68.59839755875252]
  HiRE comprises of two novel components: (i) a compression scheme to cheaply predict top-$k$ rows/columns with high recall, followed by full computation restricted to the predicted subset, and (ii) DA-TOP-$k$: an efficient multi-device approximate top-$k$ operator. We demonstrate that on a one billion parameter model, HiRE applied to both the softmax as well as feedforward layers, achieves almost matching pretraining and downstream accuracy, and speeds up inference latency by $1.47times$ on a single TPUv5e device.
  arXiv  Detail & Related papers  (2024-02-14T18:04:36Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  We provide the first differentially private algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream with length at most $T$.<n>Our main technical contribution is a differentially private clustering framework for data streams which only requires an offline DP coreset or clustering algorithm as a blackbox.
  arXiv  Detail & Related papers  (2023-07-14T16:11:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.