Privacy set intersection from oblivious polynomial evaluation

Traditional private set intersection (PSI) protocols allow parties to directly compute the intersection of the private sets without revealing their individual set contents. However, they do not support extension computations based on the intersection data. The circuit-based PSI protocol enables parties to perform extension computations on the intersection without leaking the actual intersection elements, thereby constructing a general-purpose privacy-preserving set intersection scheme. In this paper, we first survey and analyze existing work, summarizing a unified framework for circuit-PSI, which consists of three key components: local dataset classification, oblivious encoding of classified data, and intersection membership detection and sharing. Notably, the latter two components account for over 90% of the total computational cost and 100% of the communication cost. Therefore, we propose an oblivious encoding scheme based on oblivious polynomial evaluation for symmetric datasets. By replacing computationally expensive interpolation polynomial systems with efficient first-degree polynomial evaluation, we reduce the computational complexity of oblivious encoding from mathcalOn²) to mathcalOn). Furthermore, we design a communication-efficient batch equality test protocol for intersection membership detection and sharing. We reformulate the batch equality test as an oblivious retrieval problem and introduce an oblivious index rotation strategy, allowing batch equality test results to be retrieved using a single index. This approach achieves the lowest online communication cost among state-of-the-art protocols. Leveraging these optimizations, our experimental results demonstrate that our private data matching for the compute protocol achieves a speedup of 2.3× over PSTY19 (EUROCRYPT 19), 1.16× over RS21 (EUROCRYPT 21), and 1.37× over CGS22 (PETs 22). Regarding communication efficiency, our protocol requires only 31% of the communication cost of PSTY19, 29% of RS21, and 52% of CGS22.