Data-Intensive Distributed Systems LaboratoryCS Seminar
Date: March 4th, 2026
Time: 12:50pm
Room: SB111
Dr. Yanxue Jia
Assistant Professor
Department of Computer Science
Illinois Institute of Technology
Talk Title
Fuzzy Private Set Intersection for Real-World Datasets
Talk Abstract
Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their private sets without revealing any additional information. Fuzzy PSI, an approximate variant of PSI, allows the receiver to learn points of the sender that are "close" to its points. More formally, the receiver learns all y in the sender's set that satisfy dist(x, y) < delta for some element x in the receiver's set and threshold parameter delta. Recently, there has been significant progress on Fuzzy PSI, as it allows us to realize several important applications such as password matching, facial recognition, and contact tracing in a privacy-preserving manner. However, existing Fuzzy PSI constructions make strong assumptions on the input sets, such as receiver set disjointedness or projected disjointedness. In this work, we analyze those strong assumptions from a practical viewpoint and observe a gap between theory and practice, i.e., real-world data sets do not abide to those assumptions.
To bridge the gap, we first define a new relaxed and weaker assumption based on the low density of sets, demonstrate the assumption to be practical, and build a compiler that converts constructions under the strong assumption to those under the new, practical assumption. At the core of our transformation is a novel idea involving higher-dimensional lifting and coloring. Combining our transformation with current Fuzzy PSI protocols under the strong assumption yields efficient and practical Fuzzy PSI protocols. We also concretely analyze the run-time and overhead of our transformed protocols for parameters for illustrative applications, such as password matching.
Speaker Bio
Yanxue Jia is an assistant professor in the Department of Computer Science at Illinois Institute of Technology since 2025. Before joining Illinois Tech, she was a post-doctoral researcher at Purdue University, and she earned her Ph.D. in Computer Science from Shanghai Jiao Tong University in 2022. She is an applied cryptographer and her current research focuses on secure (multi-party) computation, blockchains, and provable security. She is dedicated to advancing cryptography to solve security and privacy issues in existing as well as emerging real-world applications. Her work has been published at top-tier conferences, such as USENIX Security, ACM CCS, IEEE S&P, and Asiacrypt. She has also served as a Program Committee member for conferences, such as USENIX Security, ACM CCS, FC, and ACNS.