Minimal Perfect Hashing-Based Multi-Party Private Set Intersection Protocol for Size-Imbalanced Datasets

Existing oblivious transfer (OT)-based private set intersection (PSI) protocols use cuckoo hashing and assume that participants hold similarly sized sets. In multi-institutional collaboration, set sizes differ, and OT costs follow the largest set although the intersection cannot exceed the smallest one. Cuckoo hashing also requires spare bins, a stash, and rehashing to avoid eviction loops. This study proposes perfect hashing k-out-of-N PSI (PKN-PSI), a multi-party PSI protocol that combines minimal perfect hashing with receiver designation by set size. The participants share their set sizes and designate the smallest set holder as the receiver. The receiver publishes a minimal perfect hash function (MPHF) over its set, and each sender evaluates each element once at a single oblivious pseudorandom function (OPRF) row. The senders mask the results with zero-shares and send them as an oblivious key-value store (OKVS), from which the receiver obtains the intersection. Security is proven by simulation in the semi-honest model with a non-colluding receiver, and the leakage of the published MPHF to each sender is stated explicitly. In experiments with real cryptographic operations, five parties, and a ten-fold size gap, PKN-PSI reduces symmetric key operations by 44.2%, transmitted volume by 82.6%, and the modeled WAN time by 57.2% compared with a cuckoo-hashing baseline. Size imbalance thus becomes a source of efficiency, as in multi-institutional medical record linkage.