zbMATH — the first resource for mathematics

Secure computation of the \(k\)th-ranked element. (English) Zbl 1122.68422
Cachin, Christian (ed.) et al., Advances in cryptology – EUROCRYPT 2004. International conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2–6, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21935-8/pbk). Lecture Notes in Computer Science 3027, 40-55 (2004).
Summary: 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 a malicious adversary.
For the entire collection see [Zbl 1051.94003].

68P25 Data encryption (aspects in computer science)
94A62 Authentication, digital signatures and secret sharing
Full Text: DOI