DDH-based schemes for multi-party Function Secret Sharing

• URL: http://arxiv.org/abs/2603.17453v1
• Date: Wed, 18 Mar 2026 07:48:19 GMT
• Title: DDH-based schemes for multi-party Function Secret Sharing
• Abstract summary: 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.
• Score: 3.0966075492209715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size. We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.

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)
• Information-Theoretic Distributed Point Functions with Shorter Keys [4.8986598953553555]
  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)
  arXiv  Detail & Related papers  (2026-04-27T12:17:05Z)
• 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)
• Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval [0.30586855806896035]
  Private Set Union (PSU), resp. Intersection (PSI), is a protocol that allows parties to compute the union, resp. the intersection, between their private sets.<n>We present in this paper, Fuzzy PSU protocols (FPSU), able to efficiently take into account approximations in the union.
  arXiv  Detail & Related papers  (2026-01-28T09:05:35Z)
• Redundancy-Driven Top-$k$ Functional Dependency Discovery [5.126404609788543]
  Functional dependencies (FDs) are basic constraints in relational databases and are used for many data management tasks.<n>Most FD discovery algorithms find all valid dependencies, but this causes two problems.<n>We propose SDP (Selective-Discovery-and-Prune), which discovers the top-$k$ FDs ranked by redundancy count.
  arXiv  Detail & Related papers  (2026-01-15T07:16:01Z)
• 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)
• Recurrent Feature Mining and Keypoint Mixup Padding for Category-Agnostic Pose Estimation [33.204232825380394]
  Category-agnostic pose estimation aims to locate keypoints on query images according to a few annotated support images for arbitrary novel classes.<n>We propose a novel yet concise framework, which recurrently mines FGSA features from both support and query images.
  arXiv  Detail & Related papers  (2025-03-27T04:09:13Z)
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization [51.19403058739522]
  Differentially private gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner.<n>We introduce DP-ZO, a private fine-tuning framework for large language models by privatizing zeroth order optimization methods.
  arXiv  Detail & Related papers  (2024-01-09T03:53:59Z)
• PartialFormer: Modeling Part Instead of Whole for Machine Translation [40.67489864907433]
  We introduce PartialFormer, a parameter-efficient Transformer architecture utilizing multiple smaller FFNs. These smaller FFNs are integrated into a multi-head attention mechanism for effective collaboration. Experiments on 9 translation tasks and 1 abstractive summarization task validate the effectiveness of our PartialFormer approach.
  arXiv  Detail & Related papers  (2023-10-23T13:25:54Z)
• Efficient Human Pose Estimation by Learning Deeply Aggregated Representations [67.24496300046255]
  We propose an efficient human pose estimation network (DANet) by learning deeply aggregated representations. Our networks could achieve comparable or even better accuracy with much smaller model complexity.
  arXiv  Detail & Related papers  (2020-12-13T10:58:07Z)
• Lightweight Single-Image Super-Resolution Network with Attentive Auxiliary Feature Learning [73.75457731689858]
  We develop a computation efficient yet accurate network based on the proposed attentive auxiliary features (A$2$F) for SISR. Experimental results on large-scale dataset demonstrate the effectiveness of the proposed model against the state-of-the-art (SOTA) SR methods.
  arXiv  Detail & Related papers  (2020-11-13T06:01:46Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  In this paper, we study reinforcement learning for discounted Decision (MDP) We propose a novel algorithm that makes use of the feature mapping and obtains a $tilde O(dsqrtT/ (1-gamma)2)$ regret. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $ (1-gamma)-0.5$ factor.
  arXiv  Detail & Related papers  (2020-06-23T17:08:54Z)
• LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
  All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. We present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. We show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets.
  arXiv  Detail & Related papers  (2020-03-06T00:06:20Z)

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.