Secure Multi-Party Multi-Data Deduplication Sorting With Root-Polynomial Encoding

doi:10.1109/tetc.2026.3743344

Secure Multi-Party Multi-Data Deduplication Sorting With Root-Polynomial Encoding

2026-10-19

0

PRE

AI

DOI：10.1109/tetc.2026.3743344

Original

Original request for help

Save

Abstract

En 中文

Secure multi-party computation (SMC) has received significant attention recently. As one of the most common operators, sorting is essential in data mining and analysis. To achieve secure multi-party sorting (SMS), many SMS schemes have been proposed. However, most existing schemes neither support deduplication sorting nor achieve efficient communication and computation. To balance security, functionality, and efficiency, we propose an efficient secure multi-party multi-data deduplication sorting scheme, called SMDS. Specifically, the concrete functionality realized by SMDS is deduplicated ranking under set semantics: for each user value, it returns its position in the deduplicated union of all users' datasets, where equal values share the same position. Based on symmetric homomorphic encryption (SHE), we design a multi-party SHE scheme, called Multi-SHE, and combine it with a polynomial-based encoding (PBE) method to support privacy-preserving deduplicated counting and ranking computation over a bounded ordered domain in a non-colluding two-server model with an ideal communication pattern. We further formalize the security of SMDS under a static semi-honest model with explicit leakage and prove that it securely realizes the target functionality assuming the semantic security of Multi-SHE. Moreover, we conduct extensive comparison experiments to evaluate the performance of SMDS, and the results show that it achieves favorable efficiency. Specifically, in a dataset with 18,000 data values for 18 participants, where each participant holds a dataset of size 1,000, the computational cost of SMDS is 40.85 s, which is only 54.39% and 56.34% of that of two related schemes, respectively.

Keywords:

Deduplication sorting

privacy-preserving ranking

secure multi-party computation

symmetric homomorphic encryption

root-polynomial encoding

Secure Multi-Party Multi-Data Deduplication Sorting With Root-Polynomial Encoding

Abstract

Journal

Organization

Cited Papers