Paper 2022/1465

Private Collaborative Data Cleaning via Non-Equi PSI

Erik-Oliver Blass, Airbus
Florian Kerschbaum, University of Waterloo, Canada

We introduce and investigate the privacy-preserving version of collaborative data cleaning. With collaborative data cleaning, two parties want to reconcile their data sets to filter out badly classified, misclassified data items. In the privacy-preserving (private) version of data cleaning, the additional security goal is that parties should only learn their misclassified data items, but nothing else about the other party's data set. The problem of private data cleaning is essentially a variation of private set intersection (PSI), and one could employ recent circuit-PSI techniques to compute misclassifications with privacy. However, we design, analyze, and implement three new protocols tailored to the specifics of private data cleaning that significantly outperform a circuit-PSI-based approach. With the first protocol, we exploit the idea that a small additional leakage (the size of the intersection of data items) allows for runtime and communication improvements of more than one order of magnitude over circuit-PSI. The other two protocols convert the problem of finding a mismatch in data classifications into finding a match, and then follow the standard technique of using oblivious pseudo-random functions (OPRF) for computing PSI. Depending on the number of data classes, this leads to either total runtime or communication improvements of up to two orders of magnitude over circuit-PSI.

Available format(s)
Cryptographic protocols
Publication info
Contact author(s)
erik-oliver blass @ airbus com
florian kerschbaum @ uwaterloo ca
2022-10-26: approved
2022-10-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Erik-Oliver Blass and Florian Kerschbaum},
      title = {Private Collaborative Data Cleaning via Non-Equi PSI},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1465},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.