Secure computation of the k'th-ranked element

Abstract

Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the k'th-ranked element of the union of the datasets, e.g. the median of the values in the datasets. We investigate protocols with sublinear computation and communication costs. In the two-party case, we show that the k'th-ranked element can be computed in log(k) rounds, where the computation and communication costs of each round are O(log(M) ), where log(M) is the number of bits needed to describe each element of the input data. The protocol can be made secure against a malicious adversary, and can hide the sizes of the original datasets. In the multi-party setting, we show that the k'th-ranked element can be computed in log M rounds, with O(s log M), overhead per round, where s is the number of parties. The multi-party protocol can be used in the two-party case and can also be made secure against malicious adversary.

Back to publications
Back to previous page