Enhancing TreePIR for a Single-Server Setting via Resampling

• URL: http://arxiv.org/abs/2510.04882v1
• Date: Mon, 06 Oct 2025 15:03:05 GMT
• Title: Enhancing TreePIR for a Single-Server Setting via Resampling
• Authors: Elian Morel,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Private Information Retrieval (PIR) allows a client to retrieve an entry $\text{DB}[i]$ from a public database $\text{DB}$ held by one or more servers, without revealing the queried index $i$. Traditional PIR schemes achieve sublinear server computation only under strong assumptions, such as the presence of multiple non-colluding servers or the use of public-key cryptography. To overcome these limitations, \textit{preprocessing PIR} schemes introduce a query-independent offline phase where the client collects \textit{hints} that enable efficient private queries during the online phase. In this work, we focus on preprocessing PIR schemes relying solely on \textit{One-Way Functions} (OWFs), which provide minimal cryptographic assumptions and practical implementability. We study three main constructions -- TreePIR, PIANO, and PPPS -- that explore different trade-offs between communication, storage, and server trust assumptions. Building upon the mechanisms introduced in PIANO and PPPS, we propose an adaptation of TreePIR to the single-server setting by introducing a dual-table hint structure (primary and backup tables) and a \textit{resampling} technique to refresh hints efficiently. Our proposed scheme achieves logarithmic upload bandwidth and $O(\sqrt{n}\log n)$ download complexity while requiring $O(\sqrt{n}\log n)$ client storage. This represents a significant improvement over prior single-server preprocessing PIR schemes such as PIANO ($O(\sqrt{n})$ bandwidth) and PPPS ($O(n^{1/4})$ bandwidth), while maintaining the simplicity and minimal assumptions of the OWF-based setting.

Related papers

• Relational In-Context Learning via Synthetic Pre-training with Structural Prior [60.404256960057545]
  RDB-PFN is the first relational foundation model trained purely via $textbfsynthetic$.<n>Inspired by Prior-Data Fitted Networks (PFNs) where synthetic data generated from Structural Causal Models (SCMs) enables reasoning on single tables.<n>Experiments verify RDB-PFN achieves strong few-shot performance on 19 real-world prediction tasks.
  arXiv  Detail & Related papers  (2026-03-04T07:30:54Z)
• IVE: An Accelerator for Single-Server Private Information Retrieval Using Versatile Processing Elements [4.085063539485129]
  IVE is an accelerator for single-server PIR with a systematic extension that enables retrieval from large databases using DRAM.<n>IVE achieves up to 1,275x higher throughput compared to prior PIR hardware solutions.
  arXiv  Detail & Related papers  (2025-12-01T11:47:26Z)
• Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [43.914623898157856]
  symmetric private information retrieval on replicated databases modeled by a simple graph.<n>We consider the setting where the server-side common randomness necessary to accomplish SPIR is also replicated at the servers according to the graph.
  arXiv  Detail & Related papers  (2025-07-23T17:51:08Z)
• 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)
• Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
  We consider the private information retrieval problem for a multigraph-based replication system.<n>Our goal is to establish upper and lower bounds on the PIR capacity of the $r$-multigraph.
  arXiv  Detail & Related papers  (2025-01-29T18:48:22Z)
• 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)
• Private Aggregate Queries to Untrusted Databases [3.6209090009720155]
  Private information retrieval (PIR) is a privacy-preserving cryptographic tool. Most PIR protocols require the client to know the exact row index of the intended database item. We build a novel information-theoretic PIR framework that permits a user to fetch the aggregated result.
  arXiv  Detail & Related papers  (2024-03-20T04:35:21Z)
• SpotServe: Serving Generative Large Language Models on Preemptible Instances [64.18638174004151]
  SpotServe is the first distributed large language models serving system on preemptible instances. We show that SpotServe can reduce the P99 tail latency by 2.4 - 9.1x compared with the best existing LLM serving systems. We also show that SpotServe can leverage the price advantage of preemptive instances, saving 54% monetary cost compared with only using on-demand instances.
  arXiv  Detail & Related papers  (2023-11-27T06:31:17Z)
• RAMP: A Flat Nanosecond Optical Network and MPI Operations for Distributed Deep Learning Systems [68.8204255655161]
  We introduce a near-exascale, full-bisection bandwidth, all-to-all, single-hop, all-optical network architecture with nanosecond reconfiguration called RAMP. RAMP supports large-scale distributed and parallel computing systems (12.8Tbps per node for up to 65,536 nodes.
  arXiv  Detail & Related papers  (2022-11-28T11:24:51Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• Quantum Private Information Retrieval for Quantum Messages [71.78056556634196]
  Quantum private information retrieval (QPIR) for quantum messages is the protocol in which a user retrieves one of the multiple quantum states from one or multiple servers without revealing which state is retrieved. We consider QPIR in two different settings: the blind setting, in which the servers contain one copy of the message states, and the visible setting, in which the servers contain the description of the message states.
  arXiv  Detail & Related papers  (2021-01-22T10:28:32Z)
• Towards Differentially Private Text Representations [52.64048365919954]
  We develop a new deep learning framework under an untrusted server setting. For the randomization module, we propose a novel local differentially private (LDP) protocol to reduce the impact of privacy parameter $epsilon$ on accuracy. Analysis and experiments show that our framework delivers comparable or even better performance than the non-private framework and existing LDP protocols.
  arXiv  Detail & Related papers  (2020-06-25T04:42:18Z)

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.