PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting

• URL: http://arxiv.org/abs/2310.14565v2
• Date: Sun, 18 Aug 2024 22:37:10 GMT
• Title: PEPSI: Practically Efficient Private Set Intersection in the Unbalanced Setting
• Authors: Rasoul Akhavan Mahdavi, Nils Lukas, Faezeh Ebrahimianghazani, Thomas Humphries, Bailey Kacsmar, John Premkumar, Xinda Li, Simon Oya, Ehsan Amjadian, Florian Kerschbaum,
• Abstract summary: 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.
• Score: 27.625750404980597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two parties with private data sets can find shared elements using a Private Set Intersection (PSI) protocol without revealing any information beyond the intersection. Circuit PSI protocols privately compute an arbitrary function of the intersection - such as its cardinality, and are often employed in an unbalanced setting where one party has more data than the other. 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. PEPSI can process an intersection of 1024 client items with a million server items in under a second, using less than 5 MB of communication. Our work is over 4 orders of magnitude faster than an existing non-interactive circuit PSI protocol and requires only 10% of the communication. It is also up to 20 times faster than the work of Ion et al., which computes a limited set of functions and has communication costs proportional to the larger set. Our work is the first to demonstrate that non-interactive circuit PSI can be practically applied in an unbalanced setting.

Related papers

• BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training [50.334494587223304]
  BiCoLoR is a communication-efficient optimization algorithm that combines two widely used strategies: local training and compression.<n>We show BiCoLoR outperforms existing algorithms and establishes a new standard in communication efficiency.
  arXiv  Detail & Related papers  (2026-01-18T13:23:27Z)
• 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)
• Multi-Party Private Set Operations from Predicative Zero-Sharing [8.27056097136535]
  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.
  arXiv  Detail & Related papers  (2025-04-10T16:38:10Z)
• Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity [92.1840862558718]
  We introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. We show that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers. We introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases.
  arXiv  Detail & Related papers  (2024-02-09T13:58:33Z)
• Multi-Party Private Set Intersection: A Circuit-Based Protocol with Jaccard Similarity for Secure and Efficient Anomaly Detection in Network Traffic [10.775721991076793]
  We present a new circuit-based protocol for multi-party private set intersection (PSI) With 7 parties, each possessing a set size of 212, our protocol completes in just 19 seconds.
  arXiv  Detail & Related papers  (2024-01-23T07:59:04Z)
• 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)
• Physics-informed PointNet: On how many irregular geometries can it solve an inverse problem simultaneously? Application to linear elasticity [58.44709568277582]
  Physics-informed PointNet (PIPN) is designed to fill this gap between PINNs and fully supervised learning models. We show that PIPN predicts the solution of desired partial differential equations over a few hundred domains simultaneously. Specifically, we show that PIPN predicts the solution of a plane stress problem over more than 500 domains with different geometries, simultaneously.
  arXiv  Detail & Related papers  (2023-03-22T06:49:34Z)
• 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)
• Conference key agreement in a quantum network [67.410870290301]
  Quantum conference key agreement (QCKA) allows multiple users to establish a secure key from a shared multi-partite entangled state. In a quantum network, this protocol can be efficiently implemented using a single copy of a N-qubit Greenberger-Horne-Zeilinger (GHZ) state to distil a secure N-user conference key bit.
  arXiv  Detail & Related papers  (2022-07-04T18:00:07Z)
• More is Merrier: Relax the Non-Collusion Assumption in Multi-Server PIR [61.13962963550403]
  A long line of research on secure computation has confirmed that anything that can be computed, can be computed securely using a set of non-colluding parties.<n>However, it remains highly susceptible to covert, undetectable collusion among computing parties.<n>This work stems from an observation that if the number of available computing parties is much higher than the number of parties required to perform a secure computation task, collusion attempts in privacy-preserving computations could be deterred.
  arXiv  Detail & Related papers  (2022-01-19T17:29:39Z)
• Private Set Intersection with Delegated Blind Quantum Computing [0.0]
  We propose a protocol that solves the server-aided PSI problem using delegated blind quantum computing. The proposed protocol is correct, secure and blind against a malicious server.
  arXiv  Detail & Related papers  (2022-01-10T17:53:41Z)
• An Adaptive Device-Edge Co-Inference Framework Based on Soft Actor-Critic [72.35307086274912]
  High-dimension parameter model and large-scale mathematical calculation restrict execution efficiency, especially for Internet of Things (IoT) devices. We propose a new Deep Reinforcement Learning (DRL)-Soft Actor Critic for discrete (SAC-d), which generates the emphexit point, emphexit point, and emphcompressing bits by soft policy iterations. Based on the latency and accuracy aware reward design, such an computation can well adapt to the complex environment like dynamic wireless channel and arbitrary processing, and is capable of supporting the 5G URL
  arXiv  Detail & Related papers  (2022-01-09T09:31:50Z)
• Asymmetric Private Set Intersection with Applications to Contact Tracing and Private Vertical Federated Machine Learning [7.443117783492293]
  We present a cross-platform library for asymmetric private set intersection (PSI) and PSI-Cardinality (PSI-C) Our protocol combines traditional DDH-based PSI and PSI-C protocols with compression based on Bloom filters that helps reduce communication in the asymmetric setting. Our library supports C++, C, Go, WebAssembly, JavaScript, Python, and Rust, and runs on both traditional hardware (x86) and browser targets.
  arXiv  Detail & Related papers  (2020-11-18T15:38:59Z)
• Experimental quantum conference key agreement [55.41644538483948]
  Quantum networks will provide multi-node entanglement over long distances to enable secure communication on a global scale. Here we demonstrate quantum conference key agreement, a quantum communication protocol that exploits multi-partite entanglement. We distribute four-photon Greenberger-Horne-Zeilinger (GHZ) states generated by high-brightness, telecom photon-pair sources across up to 50 km of fibre.
  arXiv  Detail & Related papers  (2020-02-04T19:00:31Z)

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.