Full text  Click to download. 
Citation  In Proc. of Eurocrypt 2004, Springer LNCS 3027 (2004), pp. 40  55.

Authors  Gagan Aggarwal
Nina Mishra Benny Pinkas 
Given two or more parties possessing large, confidential datasets, we consider the problem of securely computing the k'thranked 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 twoparty case, we show that the k'thranked 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 multiparty setting, we show that the k'thranked element can be computed in log M rounds, with O(s log M), overhead per round, where s is the number of parties. The multiparty protocol can be used in the twoparty case and can also be made secure against malicious adversary.