Abstract. In this presentation, we introduce an efficient and actively secure private set intersection (PSI) protocol for password checkup scenarios, where a server with one large set performs PSI with multiple clients, each holding a small set. First, we demonstrate the use of an oblivious verifiable unpredictable function (OVUF) to instantiate this PSI efficiently. The OVUF-based PSI protocol enhances one-time, reusable, and asynchronous linear-size server encoding. It allows multiple clients to perform low-cost interactions with the server, with complexity linear to the size of each client's set. Next, we present an efficient instantiation of a fully maliciously secure OVUF based on weak multiplication-to-addition (MtA) triples, which is of independent interest. The weak MtA triples leverage oblivious transfer (OT), reducing communication in OT messages to achieve optimal complexity for OVUF. Finally, we briefly discuss the protocol's performance in this setting, with the server set up to millions and clients set ranging from hundreds to thousands, demonstrating high efficiency compared to other state-of-the-art work.
Joint work with: Xiao Wang (Northwestern University), Jonathan Katz (Google and University of Maryland), Phillipp Schoppmann (Google), Mariana Raykova (Google)
WPEC 2024: NIST Workshop on Privacy-Enhancing Cryptography 2024. Virtual, 2024-Sep-24–26.
NIST Workshop on Privacy-Enhancing Cryptography 2024
Starts: September 24, 2024Virtual
Security and Privacy: cryptography