Information-Theoretic Distributed Point Functions with Shorter Keys

• URL: http://arxiv.org/abs/2604.24385v1
• Date: Mon, 27 Apr 2026 12:17:05 GMT
• Title: Information-Theoretic Distributed Point Functions with Shorter Keys
• Abstract summary: A t-private n-server Information-Theoretic Distributed Point Function ((t,n)-ITDPF) allows one to convert any point function f_alpha,beta(x): [N] -> G into n shares (secret keys)<n>This paper constructs a novel share conversion based on the private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025)
• Score: 4.8986598953553555
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A t-private n-server Information-Theoretic Distributed Point Function ((t,n)-ITDPF) allows one to convert any point function f_{alpha,beta}(x): [N] -> G into n shares (secret keys), such that each server can compute an additive share of f_{alpha,beta}(x) with a key while any <= t servers learn absolutely no information about the function. This paper constructs a novel share conversion based on the private information retrieval (PIR) of Ghasemi, Kopparty, and Sudan (STOC 2025) and proposes a perfectly secure 1-private ITDPF with output group G = Z_p, where p can be any prime. Compared with the existing perfectly secure ITDPFs for the same output group, the proposed ITDPF is more efficient with asymptotically shorter secret keys.

Related papers

• Pivot: Proactive and Verifiable Threshold Oblivious Pseudorandom Functions From Isogeny Group Actions [2.7399382174132167]
  Oblivious pseudorandom functions (OPRFs) allow a client to evaluate a keyed pseudorandom function on a private input without revealing that input to the server.<n>Existing isogeny-based threshold OPRFs are primarily designed for static corruption models.<n>We introduce PIVOT, a dealerless threshold VOPRF framework based on effective isogeny group actions.
  arXiv  Detail & Related papers  (2026-08-02T17:11:35Z)
• 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)
• FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing [10.153726524753628]
  We present FuseFSS, a compiler that replaces per-operator protocol design with a single compilation pipeline.<n>Compared to the current state-of-the-art FSS-based GPU secure inference, FuseFSS preserves accuracy while achieving a $1.24times$--$1.50times$ end-to-end speedup.
  arXiv  Detail & Related papers  (2026-06-08T14:30:00Z)
• 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)
• One Model, Many Budgets: Elastic Latent Interfaces for Diffusion Transformers [80.19461768457622]
  Elastic Latent Interface Transformer (ELIT) is a drop-in, DiT-compatible mechanism that decouples input image size from compute.<n>Read and Write cross-attention layers move information between spatial tokens and latents and prioritize important input regions.<n>On ImageNet-1K 512px, ELIT delivers an average gain of $35.3%$ and $39.6%$ in FID and FDD scores.
  arXiv  Detail & Related papers  (2026-03-12T17:57:04Z)
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• 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)
• The Beginner's Textbook for Fully Homomorphic Encryption [1.6679662639178265]
  Fully Homomorphic Encryption (FHE) is a cryptographic scheme that enables computations to be performed directly on encrypted data.<n>FHE enables privacy-preserving machine learning by allowing a server to process the client's data in its encrypted form through an ML model.<n>Other applications of FHE include secure outsourcing of data analytics, encrypted database queries, privacy-preserving searches, efficient multi-party for digital signatures.
  arXiv  Detail & Related papers  (2025-03-07T04:29:11Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• THE-X: Privacy-Preserving Transformer Inference with Homomorphic Encryption [112.02441503951297]
  Privacy-preserving inference of transformer models is on the demand of cloud service users. We introduce $textitTHE-X$, an approximation approach for transformers, which enables privacy-preserving inference of pre-trained models.
  arXiv  Detail & Related papers  (2022-06-01T03:49:18Z)
• Two-Server Verifiable Homomorphic Secret Sharing for High-Degree Polynomials [3.419406971620478]
  Homomorphic secret sharing (HSS) allows multiple input clients to secret-share their data among multiple servers. Our scheme could be 3-10 times faster than the previously best construction.
  arXiv  Detail & Related papers  (2021-04-25T13:48:16Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  We present a new family of algorithms for learning Fourier-sparse set functions. In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms. We demonstrate effectiveness on several real-world applications.
  arXiv  Detail & Related papers  (2020-10-01T14:31:59Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

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.