Private Set Intersection Protocol with Perfect Hashing on OKVS: An Enhanced Approach for Privacy-Preserving Operations

This paper introduces a novel protocol for solving the Private Set Intersection (PSI) problem, leveraging the Oblivious Key-Value Stores (OKVS) data structure. OKVS enhances traditional Key-Value Stores (KVS) by adding privacy protection features. While OKVS has traditionally employed three methods—polynomial encoding-based, random matrix-based, and cuckoo hashing-based—it's now recognized that cuckoo hashing offers the most secure and efficient approach [1]. However, cuckoo hashing occasionally suffers from infinite loop issues despite efforts to minimize hash collisions. To address this, we propose a PSI protocol using perfect hashing instead of cuckoo hashing, resolving hash collision concerns. Our protocol maintains comparable time and space complexity to existing cuckoo hashing-based methods while ensuring improved performance.