Cloud-aided multi-party private set intersection using Chinese national cryptographic algorithms

Multi-party private set intersection (MPSI) allows multiple parties to discover shared elements without revealing any non-intersecting data. Previous cloud-assisted and Oblivious Pseudorandom Function (OPRF)-based MPSI protocols offer efficient matching, but often use foreign cryptographic algorithms and may reuse constant labels during evaluation and matching.

This paper introduces OPRF-MPSI, a cloud-assisted MPSI system that utilizes SM2 elliptic curve operations, SM3 hashing, and SM4 encapsulation. The protocol implements two distinct cloud-side layers, one with a SM2-based blinded OPRF layer and another with a client-re-randomized tag-hardening layer, each with distinct keys. Domain separation is applied between the tag and index derivation, based on the session identifier.

Pre-filtering is carried out using Bloom filters, but only on the finalized indexes after hardening. The cloud cannot efficiently extract plaintext elements from the intersection, limiting the leakage to metadata, candidate bucket positions, equality patterns among candidate indexes, and the overall intersection size. Experiments with various participant counts and set sizes show that OPRF-MPSI decreases the online running time by 48.69% compared to Kolesnikov et al., 38.21% compared to Zhao et al.-1, and 22.16% compared to Zhao et al.-2.

Communication overhead is reduced by 69.00% compared to Zhao et al.-1. The construction offers a favorable latency advantage while maintaining explicit communication trade-offs and compatibility with Chinese commercial cryptographic algorithms. This research was funded by the Heilongjiang Provincial Natural Science Foundation of China (Grant PL2024G010) and the National Natural Science Foundation of China (Grant 62172123).