Multi-Party Private Set Operations from Predicative Zero-Sharing

• URL: http://arxiv.org/abs/2504.20050v1
• Date: Thu, 10 Apr 2025 16:38:10 GMT
• Title: Multi-Party Private Set Operations from Predicative Zero-Sharing
• Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai, Yang Cao,
• Abstract summary: We present an MPSO framework, which allows m parties, each holding a set, to securely compute any set formulas on their private sets.<n>Our framework is highly versatile and can be instantiated to accommodate a broad spectrum of MPSO functionalities.
• Score: 8.27056097136535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Typical protocols in the multi-party private set operations (MPSO) setting enable m > 2 parties to perform certain secure computation on the intersection or union of their private sets, realizing a very limited range of MPSO functionalities. Most works in this field focus on just one or two specific functionalities, resulting in a large variety of isolated schemes and a lack of a unified framework in MPSO research. In this work, we present an MPSO framework, which allows m parties, each holding a set, to securely compute any set formulas (arbitrary compositions of a finite number of binary set operations, including intersection, union and difference) on their private sets. Our framework is highly versatile and can be instantiated to accommodate a broad spectrum of MPSO functionalities. To the best of our knowledge, this is the first framework to achieve such a level of flexibility and generality in MPSO, without relying on generic secure multi-party computation (MPC) techniques. Our framework exhibits favorable theoretical and practical performance. The computation and communication complexity scale linearly with the set size n, and it achieves optimal complexity that is on par with the naive solution for widely used functionalities, such as multi-party private set intersection (MPSI), MPSI with cardinality output (MPSI-card), and MPSI with cardinality and sum (MPSI-card-sum), in the standard semi-honest model. Furthermore, the instantiations of our framework mainly from symmetric-key techniques yield efficient protocols for MPSI, MPSI-card, MPSI-card-sum, and multi-party private set union (MPSU), with online performance surpassing or matching the state of the art.

Related papers

• Token-Level LLM Collaboration via FusionRoute [60.72307345997823]
  FusionRoute is a token-level multi-LLM collaboration framework.<n>It selects the most suitable expert at each decoding step and contributes a complementary logit that refines or corrects the selected expert's next-token distribution.<n>It outperforms both sequence- and token-level collaboration, model merging, and direct fine-tuning.
  arXiv  Detail & Related papers  (2026-01-08T16:53:16Z)
• Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP [57.28979643999352]
  We propose a framework that enables unified solvers to perceive the shared-component nature across VRP variants.<n>We introduce a State-Decomposable MDP (SDMDP) that reformulates VRPs by expressing the state space as the Cartesian product of basis state spaces.<n>A Latent Space-based SDMDP extension is developed by incorporating both the optimal basis policies and a learnable mixture function.
  arXiv  Detail & Related papers  (2025-10-24T13:31:31Z)
• Efficient and Privacy-Preserving Binary Dot Product via Multi-Party Computation [4.336006969179338]
  This paper proposes a novel binary multi-party computation (BiMPC) framework for bitwise operations.<n>The core of BiMPC is a novel approach called Dot Product via Modular Addition (DoMA), which uses regular and modular additions for efficient binary dot product calculation.<n>The privacy guarantees of the BiMPC framework are rigorously analyzed, demonstrating its efficiency and scalability in distributed settings.
  arXiv  Detail & Related papers  (2025-10-18T03:35:42Z)
• Collab-Solver: Collaborative Solving Policy Learning for Mixed-Integer Linear Programming [57.44900640134789]
  We propose a novel multi-agent-based policy learning framework for MILP solving as a Stackelberg game.<n>Specifically, we formulate the collaboration of cut selection and branching in MILP solving as a Stackelberg game.<n>The jointly learned policy significantly improves the solving performance on both synthetic and large-scale real-world MILP datasets.
  arXiv  Detail & Related papers  (2025-08-05T03:16:04Z)
• Graft: Integrating the Domain Knowledge via Efficient Parameter Synergy for MLLMs [56.76586846269894]
  Multimodal Large Language Models (MLLMs) have achieved success across various domains.<n>Despite its importance, the study of knowledge sharing among domain-specific MLLMs remains largely underexplored.<n>We propose a unified parameter integration framework that enables modular composition of expert capabilities.
  arXiv  Detail & Related papers  (2025-06-30T15:07:41Z)
• BiXFormer: A Robust Framework for Maximizing Modality Effectiveness in Multi-Modal Semantic Segmentation [55.486872677160015]
  We reformulate multi-modal semantic segmentation as a mask-level classification task.<n>We propose BiXFormer, which integrates Unified Modality Matching (UMM) and Cross Modality Alignment (CMA)<n> Experiments on both synthetic and real-world multi-modal benchmarks demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2025-06-04T08:04:58Z)
• Multi Activity Sequence Alignment via Implicit Clustering [50.3168866743067]
  We propose a novel framework that overcomes limitations using sequence alignment via implicit clustering.<n>Specifically, our key idea is to perform implicit clip-level clustering while aligning frames in sequences.<n>Our experiments show that our proposed method outperforms state-of-the-art results.
  arXiv  Detail & Related papers  (2025-03-16T14:28:46Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  We introduce a novel framework of multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT)<n>Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables.<n>Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution.
  arXiv  Detail & Related papers  (2024-06-03T14:48:53Z)
• Secure and Scalable Circuit-based Protocol for Multi-Party Private Set Intersection [4.946124980718068]
  Circuit-based approach has advantages over using custom protocols to achieve this task. By using secure computation between two parties, our protocol sidesteps the complexities associated with multi-party interactions. In order to mitigate the high overhead associated with circuit-based constructions, we have further enhanced our protocol by utilizing simple hashing scheme and permutation-based hash functions.
  arXiv  Detail & Related papers  (2023-09-14T03:20:33Z)
• Advancement on Security Applications of Private Intersection Sum Protocol [1.0485739694839666]
  Secure computation protocols combine inputs from involved parties to generate an output while keeping their inputs private. Private Set Intersection (PSI) is a secure computation protocol that allows two parties to learn the intersection of their sets without revealing anything else. Private Intersection Sum (PIS) extends PSI when the two parties want to learn the cardinality of the intersection. Private Join and Compute (PJC) is a scalable extension of PIS protocol to help organizations work together with confidential data sets.
  arXiv  Detail & Related papers  (2023-08-28T17:42:53Z)
• (Amplified) Banded Matrix Factorization: A unified approach to private training [15.922315074913255]
  Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications. We show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings.
  arXiv  Detail & Related papers  (2023-06-13T21:53:17Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• Strengthening Deterministic Policies for POMDPs [5.092711491848192]
  We provide a novel MILP encoding that supports sophisticated specifications in the form of temporal logic constraints. We employ a preprocessing of the POMDP to encompass memory-based decisions. The advantages of our approach lie (1) in the flexibility to strengthen simple deterministic policies without losing computational tractability and (2) in the ability to enforce the provable satisfaction of arbitrarily many specifications.
  arXiv  Detail & Related papers  (2020-07-16T14:22:55Z)

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.