Finding intersections across sensitive data is a core operation in many real-world data-driven applications, such as healthcare, anti-money laundering, financial fraud, or watchlist applications. These applications often require large-scale collaboration across thousands or more independent sources, such as hospitals, financial institutions, or identity bureaus, where all records must remain encrypted during storage and computation, and are typically outsourced to dedicated/cloud servers. Such a highly distributed, large-scale, and encrypted setting makes it very challenging to apply existing solutions, e.g., (multi-party) private set intersection (PSI) or private membership test (PMT).

Secure facial matching systems play a crucial role in privacy preserving biometric authentication, particularly in domains such as law enforcement, border control, and healthcare. Traditional facial matching systems require direct access to biometric data, raising significant privacy concerns. This paper presents HyDia, a novel protocol for scalable FHE-based facial matching with high computation and communication efficiencies, enabling secure one-to-many facial matching without exposing biometric data in plaintext. Our protocol adapts diagonalized matrix multiplication techniques to accommodate highly imbalanced matrix computations, enabling our novel non-rotational inner product algorithm that substantially reduces the homomorphic computation overhead compared to prior works. We further propose a hybrid approximation method for homomorphic thresholding, which achieves better approximation than the state-of-the-art approach (Chebyshev approximation) at the same multiplicative depths. More importantly, our design does not reveal exact similarity scores to the querier; instead, it provides only a threshold-based match decision or matching sources, strengthening privacy by withholding granular database information. We implement HyDia and competing approaches and provide both formal security proof and extensive experimental validation. Our results show that HyDia achieves practical query times at scale, significantly outperforming existing HE-based solutions in both computation and communication overhead. Notably, HyDia is the only viable FHE-based approach in common bandwidth settings (2Mbps & 1Gbps), outperforming the state-of-the-art approaches by 5.2x-227.4x in end-to-end latency under different settings. Finally, our experiments on real-face datasets show that HyDia incurs negligible accuracy loss, by achieving the same F1 score of 0.9968 as the corresponding plaintext facial matching baselines. This work advances the feasibility of privacy-preserving biometric identification, offering a scalable, bandwidth-efficient, and accurate solution for real-world deployments.

In many real-world scenarios, there are cases where a client wishes to check if a data element they hold is included in a set segmented across a large number of data holders. To protect user privacy, the client's query and the data holders' sets should remain encrypted throughout the whole process. Prior work on Private Set Intersection (PSI), Multi-Party PSI (MPSI), Private Membership Test (PMT), and Oblivious RAM (ORAM) falls short in this scenario in many ways. They either require data holders to possess the sets in plaintext, incur prohibitively high latency for aggregating results from a large number of data holders, leak the information about the party holding the intersection element, or induce a high false positive. This paper introduces the primitive of a Private Segmented Membership Test (PSMT). We give a basic construction of a protocol to solve PSMT using a threshold variant of approximate-arithmetic homomorphic encryption and show how to overcome existing challenges to construct a PSMT protocol without leaking information about the party holding the intersection element or false positives for a large number of data holders ensuring IND-CPA^D security. Our novel approach is superior to existing state-of-the-art approaches in scalability with regard to the number of supported data holders. This is enabled by a novel summation-based homomorphic membership check rather than a product-based one, as well as various novel ideas addressing technical challenges. Our PSMT protocol supports many more parties (up to 4096 in experiments) compared to prior related work that supports only around 100 parties efficiently. Our experimental evaluation shows that our method's aggregation of results from data holders can run in 92.5s for 1024 data holders and a set size of 2^25, and our method's overhead increases very slowly with the increasing number of senders. We also compare our PSMT protocol to other state-of-the-art PSI and MPSI protocols and discuss our improvements in usability with a better privacy model and a larger number of parties.