Efficient Private Set Intersection by Utilizing Oblivious Transfer Extension

The private set intersection (PSI) allows two parties to know the intersection of their sets securely without revealing anything else. Many PSI protocols have been proposed, and many efficient schemes are based on oblivious pseudorandom functions (OPRF) built from oblivious transfer (OT). In this paper, we first propose a computationally friendly OPRF protocol by combining an OT extension (Crypto'03) with an oblivious key-value store (OKVS). By directly utilizing our OPRF protocol, we propose our PSI protocol. Compared with the most computationally friendly OT-based PSI protocol KKRT (CCS'16), our protocol can overcome the uncertainty issue of cuckoo hashing and runs faster 22.3% ∼ 41.2%. Compared with spot-low (Crypto'19) that has the lowest communication costs among the OT-based protocols, our protocol can run 69.5 × ∼1/4124.6 × faster than it with only 22% ∼ 23% more communication cost. CM (Crypto'20) aimed to balance computation and communication costs in their protocol such that it can run the fastest when the bandwidth is not high and not low. Our protocol outperforms CM in all settings with 5.8% ∼ 6.4% less communication costs. By utilizing our OPRF protocol, we also propose a more functional oblivious programmable pseudorandom function (OPPRF) protocol, allowing a party to securely obtain the payloads that correspond to common items. Our OPPRF protocol can be 1.7 × ∼1/42.4 × as fast as the state-of-the-art OPPRF protocol (Eurocrypt'21) in the LAN setting.