Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions

• URL: http://arxiv.org/abs/2406.07011v4
• Date: Sun, 8 Sep 2024 09:07:43 GMT
• Title: Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions
• Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai,
• Abstract summary: Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets. We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. We show that our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $220$ items each.
• Score: 5.030459935922802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of multi-party private set union (MPSU) protocols: The first category builds on public-key techniques, where existing works require a super-linear number of public-key operations, resulting in their poor practical efficiency. The second category builds on oblivious transfer and symmetric-key techniques. The only work in this category, proposed by Liu and Gao (ASIACRYPT 2023), features the best concrete performance among all existing protocols, but still has super-linear computation and communication. Moreover, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice. There remains two significant open problems so far: no MPSU protocol achieves semi-honest security based on oblivious transfer and symmetric-key techniques, and no MPSU protocol achieves both linear computation and linear communication complexity. In this work, we resolve both of them. - We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $3.9-10.0 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $2^{20}$ items each. - We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao.

Related papers

• A Multiparty Quantum Private Equality Comparison scheme relying on $\ket{ GHZ_{ 3 } }$ states [0.0]
  This paper introduces an innovative entanglement-based protocol that accomplishes multiparty quantum private comparison. It is made possible because the protocol uses only GHZ3 triplets, irrespective of the number of millionaires. The protocol is information-theoretically secure, preventing outside parties from learning about fortunes or inside players from knowing each other's secret numbers.
  arXiv  Detail & Related papers  (2024-07-07T14:21:22Z)
• Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition [71.33787410075577]
  We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses. We propose a new algorithm that attains an $widetildeO(dsqrtHS3K + sqrtHSAK)$ regret with high probability.
  arXiv  Detail & Related papers  (2024-03-07T15:03:50Z)
• A General Framework for Sequential Decision-Making under Adaptivity Constraints [112.79808969568253]
  We study general sequential decision-making under two adaptivity constraints: rare policy switch and batch learning. For the rare policy switch constraint, we provide an algorithm to achieve a $widetildemathcalO(sqrtK+K/B)$ regret with the number of batches. For the batch learning constraint, we provide an algorithm that provides a $widetildemathcalO(sqrtK+K/B)$ regret with the number of batches.
  arXiv  Detail & Related papers  (2023-06-26T07:20:25Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Bicoptor: Two-round Secure Three-party Non-linear Computation without Preprocessing for Privacy-preserving Machine Learning [5.774912335678817]
  This work introduces a family of novel secure three-party protocols, Bicoptor, which improve the efficiency of evaluating non-linear functions. Our 3PC sign determination protocol only requires two communication rounds, and does not involve any preprocessing. We evaluate Bicoptor under a 3-party LAN network over a public cloud, and achieve more than 370,000 DReLU/ReLU or 41,000 Maxpool operations per second.
  arXiv  Detail & Related papers  (2022-10-05T02:33:53Z)
• Non-local computation of quantum circuits with small light cones [0.0]
  Port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. We give an explicit class of unitaries for which our protocol's entanglement cost scales better than any known protocol.
  arXiv  Detail & Related papers  (2022-03-18T18:00:06Z)
• Communication Complexity of Private Simultaneous Quantum Messages Protocols [0.609170287691728]
  We study the advantages of quantum communication and prior entanglement of the private simultaneous quantum messages model. We show that the privacy condition inevitably increases the communication cost in the two-party PSQM model. We also show an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings.
  arXiv  Detail & Related papers  (2021-05-15T03:08:01Z)
• Online Apprenticeship Learning [58.45089581278177]
  In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function. The goal is to find a policy that matches the expert's performance on some predefined set of cost functions. We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
  arXiv  Detail & Related papers  (2021-02-13T12:57:51Z)
• A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost [53.968049198926444]
  We present the first algorithm for linear MDP with a low switching cost. Our algorithm achieves an $widetildeOleft(sqrtd3H4Kright)$ regret bound with a near-optimal $Oleft(d Hlog Kright)$ global switching cost.
  arXiv  Detail & Related papers  (2021-01-02T18:41:27Z)

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.