Secure Computation of the kth-Ranked Element in a Star Network.
No ratings
Presented at FinancialCryptographyandDataSecurity 2020 by
We consider the problem of securely computing the kth-ranked element in a sequence of n private integers distributed among nparties. The kth-ranked element (e.g., minimum, maximum, median) isof particular interest in collaborative benchmarking and auctions. Previous secure protocols for the kth-ranked element require a communicationchannel between each pair of parties. A server model naturally fits withthe client-server architecture of Internet applications in which clientsare connected to the server and not to other clients. It simplifies securecomputation by reducing the number of rounds and improves its performance and scalability. In this paper, we propose different approaches forprivately computing the kth-ranked element in the server model, using either garbled circuits or threshold homomorphic encryption. Our schemeshave a constant number of rounds and can compute the kth-ranked element within seconds for up to 50 clients in a WAN.