Eliminating Exponential Key Growth in PRG-Based Distributed Point Functions

• URL: http://arxiv.org/abs/2509.22022v1
• Date: Fri, 26 Sep 2025 07:57:24 GMT
• Title: Eliminating Exponential Key Growth in PRG-Based Distributed Point Functions
• Abstract summary: 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.
• Score: 3.0966075492209715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed Point Functions (DPFs) enable sharing secret point functions across multiple parties, supporting privacy-preserving technologies such as Private Information Retrieval, and anonymous communications. While 2-party PRG-based schemes with logarithmic key sizes have been known for a decade, extending these solutions to multi-party settings has proven challenging. In particular, PRG-based multi-party DPFs have historically struggled with practicality due to key sizes growing exponentially with the number of parties and the field size. Our work addresses this efficiency bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al. (EUROCRYPT'15). By leveraging the honest-majority assumption, we eliminate the exponential factor present in this scheme. 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. This work demonstrates that with careful optimization, PRG-based multi-party DPFs can achieve practical performances, and even obtain top performances.

Related papers

• 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)
• State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives [10.565834218166524]
  We contribute to the programme of establishing DPPs as a subsampling toolbox for ML by advancing on two fronts.<n>First, we propose new DPPs on the Euclidean space based on wavelets, with provably better accuracy guarantees than the best known rates.<n>Second, we introduce a general method to convert continuous DPPs, which are more amenable to proving analytical statements, into discrete kernels.
  arXiv  Detail & Related papers  (2026-05-13T07:54:37Z)
• Efficient DPF-based Error-Detecting Information-Theoretic Private Information Retrieval Over Rings [9.893133639294563]
  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.
  arXiv  Detail & Related papers  (2026-04-01T02:51:51Z)
• DDH-based schemes for multi-party Function Secret Sharing [3.0966075492209715]
  We propose a DDH-based technique reducing the key size of existing multi-party schemes.<n>Our benchmark highlights key sizes up to $10times$ smaller than state-of-the-art schemes.
  arXiv  Detail & Related papers  (2026-03-18T07:48:19Z)
• 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)
• Prior-Fitted Networks Scale to Larger Datasets When Treated as Weak Learners [82.72552644267724]
  BoostPFN can outperform standard PFNs with the same size of training samples in large datasets.<n>High performance is maintained for up to 50x of the pre-training size of PFNs.
  arXiv  Detail & Related papers  (2025-03-03T07:31:40Z)
• A New Non-Binary Response Generation Scheme from Physical Unclonable Functions [2.142505989409247]
  A new non-binary response generation scheme based on the one-probability of PUF bits is proposed. Our FPGA implementation results demonstrate a significant increase in effective key length as opposed to previous works.
  arXiv  Detail & Related papers  (2024-10-27T03:24:17Z)
• A-FedPD: Aligning Dual-Drift is All Federated Primal-Dual Learning Needs [57.35402286842029]
  We propose a novel Aligned Dual Dual (A-FedPD) method, which constructs virtual dual align global and local clients.<n>We provide a comprehensive analysis of the A-FedPD method's efficiency for those protracted unicipated security consensus.
  arXiv  Detail & Related papers  (2024-09-27T17:00:32Z)
• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications.<n>We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately.<n> Experiments on various synthetic TPP instances and the TPPLIB benchmark demonstrate that our DRL-based approach can significantly outperform well-established TPPs.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• Fine-Grained Pillar Feature Encoding Via Spatio-Temporal Virtual Grid for 3D Object Detection [11.798670216671631]
  Fine-Grained Pillar Feature (FG-PFE) is a novel encoding architecture for LiDAR-based 3D object detectors. FG-PFE achieves significant performance improvements over baseline models such as PointPillar, CenterPoint-Pillar, and PillarNet.
  arXiv  Detail & Related papers  (2024-03-11T04:58:36Z)
• FP3O: Enabling Proximal Policy Optimization in Multi-Agent Cooperation with Parameter-Sharing Versatility [13.882557160892686]
  Existing multi-agent PPO algorithms lack compatibility with different types of parameter sharing. We develop a practical algorithm called Full-Pipeline PPO (FP3O) by several approximations.
  arXiv  Detail & Related papers  (2023-10-08T07:26:35Z)
• Tuning Pre-trained Model via Moment Probing [62.445281364055795]
  We propose a novel Moment Probing (MP) method to explore the potential of LP. MP performs a linear classification head based on the mean of final features. Our MP significantly outperforms LP and is competitive with counterparts at less training cost.
  arXiv  Detail & Related papers  (2023-07-21T04:15:02Z)
• 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)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• 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)

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.