Efficient Collaborative Data Cleaning Using Private Set Intersection and Encoding for Unbalanced Datasets

Data cleaning improves quality and consistency by detecting, localizing, and repairing “dirty” data without compromising sensitive information. Collaborative Data Cleaning employs a distributed model to avoid single points of failure and trust issues in centralized systems, although it incurs additional communication overhead. Blass et al. (S&P’23) were the first to implement CDC via balanced Private Set Intersection (PSI). Unbalanced PSI (e.g., <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uPSI-CA</i>, USENIX’23) does not address the localization of intersections within datasets and thus cannot be directly applied to CDC. uPSI-based data cleaning remains largely unexplored. In this paper, we propose an efficient CDC scheme for unbalanced datasets, named <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uECDC</i>. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uECDC</i> employs oblivious key-value stores for slice matching, achieving: i) a reduction of 18% ~ 85% in offline phase runtime, and ii) a reduction of 8% ~ 43% in online phase runtime (under large-scale data settings on the server side), when compared to the slice-linking approach of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uPSI-CA</i>. Moreover, we encode server-side data for fast localization of intersection data in unbalanced settings. Under the semi-honest adversary model, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uECDC</i> is provably secure. Implementation in Python and C++ demonstrates that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uECDC</i> is practically feasible.