Recent work (Falzon and Tang USENIX 2025) has shown that a protocol participant who behaves honestly but strategically chooses its inputs can break input privacy in the Private Join and Compute functionality. In this work, we expand our understanding of attacks in this setting by investigating a broader class of functionalities, namely: Private Set Union (PSU), PSU-Cardinality (PSU-CA), and Meta’s multi-key private matching (MKPM) functionality. We begin with a simple yet novel attack on PSU that fully reconstructs the intersection using only two protocol invocations and forms the conceptual foundation for our more complex attacks. We also show that any attack on PSI-Cardinality, such as that of Guo et al. (USENIX 2023), lifts to an attack on PSU-CA that recovers the intersection with only three additional queries. For the MKPM protocol, we distinguish its intended matching functionality from the protocol-specific leakage, give an attack against the intended functionality, and then show that exploiting the additional leakage enables even stronger attacks, including partial reconstruction of the other party’s records from a single protocol invocation. We conclude by discussing possible mitigations for deploying such systems. Our analysis demonstrates limitations of existing secure multi-party computation security definitions and highlights the real-world privacy risks associated with deploying these functionalities in practice.

The use of biometric-based security protocols is on the steep rise. As biometrics become more popular, we witness more attacks. For example, recent BrutePrint/InfinityGauntlet attacks showed how to brute-force fingerprints stored on an Android phone in about 40 minutes. The attacks are possible because biometrics, like passwords, do not have high entropy. But unlike passwords, brute-force attacks are much more damaging for biometrics, because one cannot easily change biometrics in case of compromise. In this work, we propose a novel provably secure Brute-Force Resistant Biometrics (BFRB) protocol for biometric-based authentication and key reconstruction that protects against brute-force attacks even when the server storing biometric-related data is compromised. Our protocol utilizes a verifiable partially oblivious pseudorandom function, an authenticated encryption scheme, a pseudorandom function, and a hash. We formally define security for a BFRB protocol and reduce the security of our protocol to the security of the building blocks. We implement the protocol and study its performance for the ND-0405 iris dataset.

Encrypted search focuses on protecting sensitive data in outsourced environments while enabling private queries. Although standard encrypted search algorithms are efficient, they often leak some information about the queries and data. One such leakage is the access pattern on the outsourced storage. Recent leakage-abuse attacks have exploited this seemingly harmless leakage to successfully recover both queries and data, shifting research priorities towards finding the right balance between privacy and performance. While some proposals leverage oblivious RAM or other oblivious data structures to hide the access pattern, they typically incur significant bandwidth costs.

Abstract We study the problem of privacy-preserving approximate kNN search in an outsourced environment — the client sends the encrypted data to an untrusted server and later can perform secure approximate kNN search and updates. We design a security model and propose a generic construction based on locality-sensitive hashing, symmetric encryption, and an oblivious map. The construction provides very strong security guarantees, not only hiding the information about the data, but also the access, query, and volume patterns. We implement, evaluate efficiency, and compare the performance of two concrete schemes based on an oblivious AVL tree and an oblivious BSkiplist.