WPEC 2024 Talk 1b3: Structure-Aware Private Set Intersection from Function Secret Sharing

Abstract. Structure-Aware Private Set Intersection (sa-PSI) is a PSI variant where Alice has an input set \(S_A\) belonging to a publicly known family of structured sets (for example, a high-dimensional ball, union of balls) and Bob's input set \(S_B\) consists of an unstructured collection of elements. The main motivation for sa-PSI is to enable Alice (or Bob) to learn the intersection with protocol communication and computation cost that scales with a succinct description size of Alice's input \(S_A\), instead of her set cardinality \(|S_A|\). sa-PSI can be useful in applications like noisy/fuzzy biometric matching, privacy-preserving ride sharing among others. In this talk, I will present in detail a general framework for semi-honest sa-PSI using a cryptographic building block called Function Secret Sharing.

Joint work with: Benjamin Goff, Peihan Miao, Mike Rosulek and Jaspal Singh

[Slides]