Efficient One-Pass Private Set Intersection from Pairings with Offline Preprocessing
摘要
We present an efficient pairing-based private set intersection (PSI) protocol with offline preprocessing. Our protocol is one-pass as a receiver does not have to transmit any message to a sender for the entire PSI operation, implying that a sender can initiate a protocol execution anytime at will by sending a PSI message to the receiver. Moreover, the sender’s computation and communication costs are independent of the size of the receiver’s input set. We prove that our protocol is secure against semi-honest adversaries under the (standard) bilinear Diffie-Hellman assumption in the random oracle model. We also extend our semi-honest secure PSI protocol to achieve malicious security without compromising efficiency. Our experiments show that the receiver’s intersection retrieval runs 100–1000 times faster than that of Aranha et al.’s protocol (ACM CCS ’22), which is the state-of-the-art pairing-based PSI protocol, depending on the size of sets, and maintains a similar amount of computation and communication costs for the sender. Thanks to the much less computational burden for the receiver, our PSI protocols are expected to handle data sets of moderately large size well.