Practical Traceable Over-Threshold Multi-Party Private Set Intersection

• URL: http://arxiv.org/abs/2512.24652v1
• Date: Wed, 31 Dec 2025 05:59:14 GMT
• Title: Practical Traceable Over-Threshold Multi-Party Private Set Intersection
• Authors: Le Yang, Weijing You, Huiyang He, Kailiang Ji, Jingqiang Lin,
• Abstract summary: We propose two novel Traceable OT-MP-PSI protocols.<n>The first, Efficient Traceable OT-MP-PSI (ET-OT-MP-PSI), combines Shamir's secret sharing with an oblivious programmable pseudorandom function.<n>The second, Security-enhanced Traceable OT-MP-PSI (ST-OT-MP-PSI), achieves security against up to $n-1$ semi-honest participants.
• Score: 6.760685964076004
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Party Private Set Intersection (MP-PSI) with threshold enhances the flexibility of MP-PSI by disclosing elements present in at least $t$ participants' sets, rather than requiring elements to appear in all $n$ sets. In scenarios where each participant is responsible for its dataset, e.g., digital forensics, MP-PSI with threshold should disclose both intersection elements and corresponding holders such that elements are traceable and the reliability of intersection is guaranteed. We refer to MP-PSI with threshold supporting traceability as Traceable Over-Threshold MP-PSI (T-OT-MP-PSI). However, research on such protocols remains limited, and existing work tolerates at most $t-2$ semi-honest participants at considerable computational cost. We propose two novel Traceable OT-MP-PSI protocols. The first, Efficient Traceable OT-MP-PSI (ET-OT-MP-PSI), combines Shamir's secret sharing with an oblivious programmable pseudorandom function, achieving significantly improved efficiency with resistance to at most $t-2$ semi-honest participants. The second, Security-enhanced Traceable OT-MP-PSI (ST-OT-MP-PSI), achieves security against up to $n-1$ semi-honest participants by further leveraging the oblivious linear evaluation protocol. Compared to Mahdavi et al.'s protocol, ours eliminate the assumption that certain special parties do not collude. Experimental results demonstrate significant improvements: for $n=5$, $t=3$, and sets of size $2^{14}$, ET-OT-MP-PSI achieves $15056\times$ speedup and ST-OT-MP-PSI achieves $505\times$ speedup over Mahdavi et al.'s protocol.

Related papers

• Privacy-Preserving Inference for Quantized BERT Models [13.36359444231145]
  Quantization offers a promising solution by converting floating-point operations into lower-precision integer computations.<n>We propose a fine-grained, layer-wise quantization scheme and support 1-bit weight fully connected layers in a secure setting.
  arXiv  Detail & Related papers  (2025-08-03T07:52:08Z)
• MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
  Semi-structured sparsity offers a promising solution by strategically retaining $N$ elements out of every $M$ weights.<n>Existing (N:M)-compatible approaches typically fall into two categories: rule-based layerwise greedy search, which suffers from considerable errors, and gradient-driven learning, which incurs prohibitive training costs.<n>We propose a novel linear-space probabilistic framework named MaskPro, which aims to learn a prior categorical distribution for every $M$ consecutive weights and subsequently leverages this distribution to generate the (N:M)-sparsity throughout an $N$-way sampling
  arXiv  Detail & Related papers  (2025-06-15T15:02:59Z)
• Authenticated Private Set Intersection: A Merkle Tree-Based Approach for Enhancing Data Integrity [14.198268829996259]
  Private Set Intersection (PSI) enables secure computation of set intersections while preserving participant privacy.<n>Standard PSI existing protocols remain vulnerable to data integrity attacks allowing malicious participants to extract additional intersection information.<n>We propose the definition of data integrity in PSI and construct two authenticated PSI schemes by integrating Merkle Trees with state-of-the-art two-party volePSI and multi-party mPSI protocols.
  arXiv  Detail & Related papers  (2025-06-05T05:28:59Z)
• Communication Efficient Multiparty Private Set Intersection from Multi-Point Sequential OPRF [11.846509777720415]
  Multiparty private set intersection (MPSI) allows multiple participants to compute the intersection of their locally owned data sets without revealing them.<n>Most existing MPSI protocols are based on the star, mesh, and ring topologies.<n>We develop an MPSI protocol with a ring topology, addressing the challenges of communication and computational overhead.
  arXiv  Detail & Related papers  (2025-05-31T13:50:40Z)
• Quantum Secure Protocols for Multiparty Computations [2.9561405287476177]
  We present secure multiparty computation (MPC) protocols that can withstand quantum attacks. We first present the design and analysis of an information-theoretic secure oblivious linear evaluation (OLE), namely $sf qOLE$ in the quantum domain. We further utilize $sf qOLE$ as a building block to construct a quantum-safe multiparty private set intersection (MPSI) protocol.
  arXiv  Detail & Related papers  (2023-12-26T19:53:29Z)
• PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting [27.625750404980597]
  Two parties with private data sets can find shared elements using a Private Set Intersection (PSI) protocol without revealing any information beyond the intersection. Existing protocols are either computationally inefficient or require extensive server-client communication on the order of the larger set. We introduce Practically Efficient PSI or PEPSI, a non-interactive solution where only the client sends its encrypted data.
  arXiv  Detail & Related papers  (2023-10-23T04:44:13Z)
• When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
  A new complexity measure, called the emphspanning capacity, depends solely on the set $Pi$ and is independent of the MDP dynamics. We show there exists a policy class $Pi$ with a bounded spanning capacity that requires a superpolynomial number of samples to learn. This reveals a surprising separation for learnability between generative access and online access models.
  arXiv  Detail & Related papers  (2023-10-09T19:40:54Z)
• Parameterization of Cross-Token Relations with Relative Positional Encoding for Vision MLP [52.25478388220691]
  Vision multi-layer perceptrons (MLPs) have shown promising performance in computer vision tasks. They use token-mixing layers to capture cross-token interactions, as opposed to the multi-head self-attention mechanism used by Transformers. We propose a new positional spacial gating unit (PoSGU) to efficiently encode the cross-token relations for token mixing.
  arXiv  Detail & Related papers  (2022-07-15T04:18:06Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  We consider the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well.
  arXiv  Detail & Related papers  (2022-01-21T16:43:03Z)
• 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.