Recently, the research team led by Professor Chen Yu from the School of Cyber Science and Technology at Shandong University has achieved significant breakthroughs in the field of Private Set Operations. Both research papers have been accepted by USENIX Security 2025, one of the top-tier conferences in the field of information security. Shandong University is the primary affiliation for both papers.
Private Set Operations (PSO) are a class of specialized, high-frequency secure multi-party computation protocols with broad applications in areas such as joint risk control, collaborative marketing, and coordinated regulation. Among them, Private Set Union (PSU) enables parties to jointly compute the union of their private sets without revealing their individual inputs. As a fundamental cryptographic primitive, PSU plays a key role in sensitive information sharing and privacy-preserving data aggregation, with important applications in areas such as threat intelligence sharing, blacklist aggregation, and private identity matching. The two accepted papers make important progress in improving PSU efficiency and scalability to multi-party settings.
The first paper, “Fast Enhanced Private Set Union in the Balanced and Unbalanced Scenarios”, is co-authored by postdoctoral researcher Dr. Tu Binbin as the first author and Professor Chen Yu as the corresponding author. This work addresses the inefficiencies of existing enhanced-security PSU protocols, which either suffer from super-linear complexity in balanced scenarios or lack efficient constructions for unbalanced scenarios. The authors propose the first enhanced-security PSU protocol with linear communication complexity for balanced settings and the first efficient construction for unbalanced setting, achieving sub-linear communication complexity with respect to the larger input size.
The second paper, “Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions”, is authored by doctoral student Dong Minglang as the first author and Professor Chen Yu as the corresponding author. This work focuses on PSU in the multi-party setting, also known as Multi-Party Private Set Union (MPSU). The authors propose the first MPSU protocol based on oblivious transfer (OT) and symmetric-key operations in the standard semi-honest model. This protocol is 3.9-10× faster than the prior SOTA MPSU protocol. Additionally, they propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol reduces communication overhead by 3.0-36.5× over the prior SOTA MPSU protocol.
Both papers are supported by the National Natural Science Foundation of China, the National Key Research and Development Program of China, Taishan Scholar Program of Shandong Province, Shandong Laboratories Project of Bureau of Science & Technology of Shandong Province, and Key Project of Quan Cheng Laboratory.
Established in 1990, USENIX Security is one of the “Big Four” international conferences in information security, alongside ACM CCS, IEEE S&P, and NDSS. Over the past decade, the average acceptance rate for the conference has been only 19%, highlighting its competitiveness and prestige.
By Tu Binbin and Dong Minglang
