@inproceedings{agarwal2024secure,
author = {Agarwal, Amit and Boyle, Elette and Chandran, Nishanth and Gilboa, Niv and Gupta, Divya and Ishai, Yuval and Kelkar, Mahimna and Ma, Yiping},
title = {Secure Sorting and Selection via Function Secret Sharing},
booktitle = {31st Annual Conference on Computer and Communications Security (ACM CCS 2024)},
year = {2024},
month = {October},
abstract = {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.

We propose a suite of 2-party and 3-party offline-online protocols that exploit the efficient aggregation feature of function secret sharing to minimize the online communication and rounds. In particular, most of our protocols are optimal in terms of both online communication and online rounds up to small constant factors.

We compare the performance of our protocols with prior works for different input parameters (number of items, bit length of items, batch size) and system parameters (CPU cores, network) and obtain up to 14x improvement in online running time under some settings},
publisher = {ACM},
url = {http://approjects.co.za/?big=en-us/research/publication/secure-sorting-and-selection-via-function-secret-sharing/},
}