Secure Sorting and Selection via Function Secret Sharing
Amit Agarwal, Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Mahimna Kelkar, Yiping Ma · 2024
We revisit the problem of concretely efficient secure computation of sorting and selection (e.g., maximum, median, or top-k) on secret-shared data, focusing on the case of security against a single semi-honest party. Previous solutions either have a high communication overhead or many rounds of interaction, even when allowing input-independent preprocessing.