Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings

• URL: http://arxiv.org/abs/2604.00411v1
• Date: Wed, 01 Apr 2026 02:51:51 GMT
• Title: Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings
• Abstract summary: Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR)<n>Its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings.<n>This paper proposes a novel ring-based information-theoretic ED-PIR scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs.
• Score: 9.893133639294563
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Authenticated private information retrieval (APIR) is the state-of-the-art error-detecting private information retrieval (ED-PIR), using Distributed Point Functions (DPFs) for subpolynomial complexity and privacy. However, its finite field structure restricts it to prime-order DPFs, leading to prohibitively large key sizes under information-theoretic settings, while its dual-DPF-key design introduces unnecessary communication overhead, limiting its practicality for large-scale deployments. This paper proposes a novel ring-based information-theoretic ED-PIR (itED-PIR) scheme that overcomes these limitations by leveraging prime-power-order information-theoretic DPFs (itDPFs). Built over a prime-power ring, the proposed scheme breaks APIR's field-induced constraint to enable more efficient DPF utilization, significantly reducing key size growth and rendering the scheme feasible for high-security scenarios. Additionally, a single-itDPF-key design halves query-side communication overhead by eliminating APIR's redundant dual-key setup, without compromising privacy or verifiability. Beyond immediate efficiency gains, this work establishes a lightweight, flexible framework for constructing DPF-based malicious-resilient private information retrieval, opening new avenues for privacy-preserving data retrieval in distributed storage systems and post-quantum privacy protocols.

Related papers

• Trusted Hardware Acceleration for Function Secret Sharing [13.229663073793867]
  We present the distributed function accelerator (DFA), a hardware accelerator that targets the dominant primitive in FSS: distributed point function (DPF) generation and evaluation.<n>In untrusted mode, DFA serves as a pure accelerator for DPF evaluation, improving throughput and energy efficiency without changing the protocol.<n>In trusted mode, it further enables local, on-the-fly key generation, eliminating key distribution, and reducing storage and data movement overheads.
  arXiv  Detail & Related papers  (2026-08-17T07:58:46Z)
• Distributed Point Functions and Function Secret Sharing [27.58220080323485]
  A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret weight-1 vector.<n>The appealing lightweight structure of DPF constructions has enabled a wide range of applications.<n>These include private information retrieval, anonymous messaging, secure computation with preprocessing, and pseudorandom correlation generators.
  arXiv  Detail & Related papers  (2026-07-30T05:27:27Z)
• Subgraph Federated Learning via Spectral Methods [52.40322201034717]
  FedLap is a novel framework that captures inter-node dependencies while ensuring privacy and scalability.<n>We provide a formal analysis of the privacy of FedLap, demonstrating that it preserves privacy.
  arXiv  Detail & Related papers  (2025-10-29T16:22:32Z)
• Eliminating Exponential Key Growth in PRG-Based Distributed Point Functions [3.0966075492209715]
  PRG-based multi-party DPFs have struggled with practicality due to key sizes growing exponentially with the number of parties and the field size.<n>Our work addresses this bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al.<n>Our construction is the first PRG-based multi-party DPF scheme with practical key sizes, and provides key up to 3x smaller than the best known multi-party DPF.
  arXiv  Detail & Related papers  (2025-09-26T07:57:24Z)
• PAnDA: Rethinking Metric Differential Privacy Optimization at Scale with Anchor-Based Approximation [7.889420673572309]
  We propose Perturbation via Anchor-based Distributed Approximation (PAnDA) as a scalable framework for metric differential privacy (mDP)<n>Experiments on real-world geo-location datasets demonstrate that PAnDA scales to secret domains with up to 5,000 records, two times larger than prior LP-based methods.
  arXiv  Detail & Related papers  (2025-09-10T16:14:08Z)
• Improving Noise Efficiency in Privacy-preserving Dataset Distillation [59.57846442477106]
  We introduce a novel framework that decouples sampling from optimization for better convergence and improves signal quality.<n>On CIFAR-10, our method achieves a textbf10.0% improvement with 50 images per class and textbf8.3% increase with just textbfone-fifth the distilled set size of previous state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-08-03T13:15:52Z)
• IDPFilter: Mitigating Interdependent Privacy Issues in Third-Party Apps [0.30693357740321775]
  Third-party apps have increased concerns about interdependent privacy (IDP) This paper provides a comprehensive investigation into the previously underinvestigated IDP issues of third-party apps. We propose IDPFilter, a platform-agnostic API that enables application providers to minimize collateral information collection.
  arXiv  Detail & Related papers  (2024-05-02T16:02:13Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Differential Privacy with Random Projections and Sign Random Projections [37.6593006747285]
  iDP-SignRP is remarkably effective under the setting of individual differential privacy'' (iDP) DP-SignOPORP considerably improves existing algorithms under the standard DP setting.
  arXiv  Detail & Related papers  (2023-05-22T16:33:23Z)
• Is Vertical Logistic Regression Privacy-Preserving? A Comprehensive Privacy Analysis and Beyond [57.10914865054868]
  We consider vertical logistic regression (VLR) trained with mini-batch descent gradient. We provide a comprehensive and rigorous privacy analysis of VLR in a class of open-source Federated Learning frameworks.
  arXiv  Detail & Related papers  (2022-07-19T05:47:30Z)
• Differentially Private Federated Bayesian Optimization with Distributed Exploration [48.9049546219643]
  We introduce differential privacy (DP) into the training of deep neural networks through a general framework for adding DP to iterative algorithms. We show that DP-FTS-DE achieves high utility (competitive performance) with a strong privacy guarantee. We also use real-world experiments to show that DP-FTS-DE induces a trade-off between privacy and utility.
  arXiv  Detail & Related papers  (2021-10-27T04:11:06Z)
• Privacy Amplification via Random Check-Ins [38.72327434015975]
  Differentially Private Gradient Descent (DP-SGD) forms a fundamental building block in many applications for learning over sensitive data. In this paper, we focus on conducting iterative methods like DP-SGD in the setting of federated learning (FL) wherein the data is distributed among many devices (clients) Our main contribution is the emphrandom check-in distributed protocol, which crucially relies only on randomized participation decisions made locally and independently by each client.
  arXiv  Detail & Related papers  (2020-07-13T18:14:09Z)

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.