Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters
Gilad Asharov, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Ariel Nof, Benny Pinkas, Katsumi Takahashi, Junichi Tomida
2022Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security36 citationsDOI
Abstract
We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step.
Topics & Concepts
Computer sciencesortSortingProtocol (science)Data deduplicationSorting algorithmSet (abstract data type)Theoretical computer scienceComputer networkComputer securityDatabaseAlgorithmProgramming languageAlternative medicineMedicinePathologyCryptography and Data SecurityPrivacy-Preserving Technologies in DataCloud Data Security Solutions