Results 1491 - 1500 of 23856

Private set intersection (PSI) enables two parties, each holding a private set of elements, to compute the intersection of their sets without revealing anything beyond the intersection. Updatable PSI (UPSI) extends this functionality, allowing the parties to compute PSI on a regular basis with sets that get updated over time. The goal is to support efficient PSI computations that scale with the size of the updates rather than the entire sets. In this talk, I will give an overview of recent developments in UPSI, including the main results, core techniques, ongoing efforts, and open problems.

A two-party fuzzy private set intersection (PSI) protocol between Alice and Bob with input sets allows Alice to learn nothing more than the points of Bob that are “close’’ to its points in some metric space. Fuzzy PSI is a valuable privacy tool in scenarios where PSI needs to be computed over imprecise or measurement-based data, such as GPS coordinates or healthcare data. Previous approaches to fuzzy PSI rely on asymmetric cryptographic primitives, generic two-party computation techniques like garbled circuits, or function secret sharing methods, all of which are computationally intensive and lead to poor concrete efficiency.

This talk introduces a new modular framework for semi-honest fuzzy PSI, primarily built on efficient symmetric key primitives. The core idea is to reduce the design of fuzzy PSI to a novel variant of oblivious transfer (OT), which we term distance-aware random OT (daOT). We propose efficient constructions for daOT based on standard OT techniques tailored for small domains, supporting distance metrics such as the Chebyshev norm, the Euclidean norm, and the Manhattan norm.

Multi-party private set union (mPSU) allows multiple parties to compute the union of their private input sets without revealing any additional information. Existing efficient mPSU protocols can be categorized into symmetric key encryption (SKE)-based and public key encryption (PKE)-based approaches. However, neither type of mPSU protocol scales efficiently to a large number of parties, as they fail to fully utilize available computational resources, leaving participants idle during various stages of the protocol execution.

This talk highlights the limitations of existing protocols and introduces a unified framework for designing efficient mPSU protocols. I then present an efficient Parallel mPSU for Large-Scale Entities (PULSE) that enables parallel computation, allowing all parties/entities to perform computations without idle time, leading to significant efficiency improvements, particularly as the number of parties increases. Our PULSE is based on PKE and secure even when up to 𝑛 − 1 semi-honest parties are corrupted. We implemented PULSE and compared it to state-of-the-art mPSU protocols under different settings, showing a speedup of 1.91 to 3.57× for 𝑛 = 8 parties for various set sizes.

This paper initiates a concrete-security treatment of two-party secure computation. The first step is to propose, as target, a simple, indistinguishability-based definition that we call InI. This could be considered a poor choice if it were weaker than standard simulation-based definitions, but it is not; we show that for functionalities satisfying a condition called invertibility, that we define and show is met by functionalities of practical interest like PSI and its variants, the two definitions are equivalent. Based on this, we move forward to study the concrete security of a canonical OPRF-based construction of PSI, giving a tight proof of InI security of the constructed PSI protocol based on the security of the OPRF. This leads us to the concrete security of OPRFs, where we show how different DH-style assumptions on the underlying group yield proofs of different degrees of tightness, including some that are tight, for the well-known and efficient 2H-DH OPRF, and thus for the corresponding DH PSI protocol. We then give a new PSI protocol, called salted-DH PSI, that is as efficient as DH-PSI, yet enjoys tighter proofs.

We show that in any PIR (Private Information Retrieval) protocol without pre-processing, a server must perform a nearly linear number of public-key operations (in the size of the database), regardless of the number of symmetric-key operations. We will discuss the implications of this result for the communication complexity of oblivious transfer (OT) extension.

Abstract not available.